]>
Commit | Line | Data |
---|---|---|
2e635a27 CM |
1 | #include <linux/module.h> |
2 | #include <linux/radix-tree.h> | |
fec577fb CM |
3 | #include "ctree.h" |
4 | #include "disk-io.h" | |
5 | #include "print-tree.h" | |
e089f05c | 6 | #include "transaction.h" |
fec577fb | 7 | |
e089f05c CM |
8 | static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root |
9 | *orig_root, u64 num_blocks, u64 search_start, u64 | |
10 | search_end, struct btrfs_key *ins); | |
11 | static int finish_current_insert(struct btrfs_trans_handle *trans, struct | |
12 | btrfs_root *extent_root); | |
e20d96d6 CM |
13 | static int del_pending_extents(struct btrfs_trans_handle *trans, struct |
14 | btrfs_root *extent_root); | |
fec577fb CM |
15 | /* |
16 | * pending extents are blocks that we're trying to allocate in the extent | |
17 | * map while trying to grow the map because of other allocations. To avoid | |
18 | * recursing, they are tagged in the radix tree and cleaned up after | |
19 | * other allocations are done. The pending tag is also used in the same | |
20 | * manner for deletes. | |
21 | */ | |
037e6390 | 22 | #define CTREE_EXTENT_PENDING_DEL 0 |
e20d96d6 | 23 | #define CTREE_EXTENT_PINNED 1 |
fec577fb | 24 | |
e089f05c CM |
25 | static int inc_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root |
26 | *root, u64 blocknr) | |
02217ed2 | 27 | { |
234b63a0 | 28 | struct btrfs_path path; |
02217ed2 | 29 | int ret; |
e2fa7227 | 30 | struct btrfs_key key; |
234b63a0 CM |
31 | struct btrfs_leaf *l; |
32 | struct btrfs_extent_item *item; | |
e2fa7227 | 33 | struct btrfs_key ins; |
cf27e1ee | 34 | u32 refs; |
037e6390 | 35 | |
9f5fae2f CM |
36 | find_free_extent(trans, root->fs_info->extent_root, 0, 0, (u64)-1, |
37 | &ins); | |
234b63a0 | 38 | btrfs_init_path(&path); |
02217ed2 CM |
39 | key.objectid = blocknr; |
40 | key.flags = 0; | |
62e2749e | 41 | btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY); |
02217ed2 | 42 | key.offset = 1; |
9f5fae2f CM |
43 | ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, &path, |
44 | 0, 1); | |
a28ec197 CM |
45 | if (ret != 0) |
46 | BUG(); | |
02217ed2 | 47 | BUG_ON(ret != 0); |
e20d96d6 | 48 | l = btrfs_buffer_leaf(path.nodes[0]); |
4beb1b8b | 49 | item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item); |
cf27e1ee CM |
50 | refs = btrfs_extent_refs(item); |
51 | btrfs_set_extent_refs(item, refs + 1); | |
d5719762 | 52 | mark_buffer_dirty(path.nodes[0]); |
a28ec197 | 53 | |
9f5fae2f CM |
54 | btrfs_release_path(root->fs_info->extent_root, &path); |
55 | finish_current_insert(trans, root->fs_info->extent_root); | |
e20d96d6 | 56 | del_pending_extents(trans, root->fs_info->extent_root); |
02217ed2 CM |
57 | return 0; |
58 | } | |
59 | ||
e089f05c CM |
60 | static int lookup_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root |
61 | *root, u64 blocknr, u32 *refs) | |
a28ec197 | 62 | { |
234b63a0 | 63 | struct btrfs_path path; |
a28ec197 | 64 | int ret; |
e2fa7227 | 65 | struct btrfs_key key; |
234b63a0 CM |
66 | struct btrfs_leaf *l; |
67 | struct btrfs_extent_item *item; | |
68 | btrfs_init_path(&path); | |
a28ec197 | 69 | key.objectid = blocknr; |
a28ec197 | 70 | key.offset = 1; |
62e2749e CM |
71 | key.flags = 0; |
72 | btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY); | |
9f5fae2f CM |
73 | ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, &path, |
74 | 0, 0); | |
a28ec197 CM |
75 | if (ret != 0) |
76 | BUG(); | |
e20d96d6 | 77 | l = btrfs_buffer_leaf(path.nodes[0]); |
4beb1b8b | 78 | item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item); |
cf27e1ee | 79 | *refs = btrfs_extent_refs(item); |
9f5fae2f | 80 | btrfs_release_path(root->fs_info->extent_root, &path); |
a28ec197 CM |
81 | return 0; |
82 | } | |
83 | ||
e089f05c | 84 | int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root, |
e20d96d6 | 85 | struct buffer_head *buf) |
02217ed2 CM |
86 | { |
87 | u64 blocknr; | |
e20d96d6 | 88 | struct btrfs_node *buf_node; |
02217ed2 | 89 | int i; |
a28ec197 | 90 | |
3768f368 | 91 | if (!root->ref_cows) |
a28ec197 | 92 | return 0; |
e20d96d6 CM |
93 | buf_node = btrfs_buffer_node(buf); |
94 | if (btrfs_is_leaf(buf_node)) | |
a28ec197 CM |
95 | return 0; |
96 | ||
e20d96d6 CM |
97 | for (i = 0; i < btrfs_header_nritems(&buf_node->header); i++) { |
98 | blocknr = btrfs_node_blockptr(buf_node, i); | |
e089f05c | 99 | inc_block_ref(trans, root, blocknr); |
02217ed2 CM |
100 | } |
101 | return 0; | |
102 | } | |
103 | ||
e089f05c CM |
104 | int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct |
105 | btrfs_root *root) | |
a28ec197 | 106 | { |
d5719762 | 107 | struct buffer_head *gang[8]; |
88fd146c | 108 | u64 first = 0; |
a28ec197 CM |
109 | int ret; |
110 | int i; | |
111 | ||
112 | while(1) { | |
e20d96d6 | 113 | ret = radix_tree_gang_lookup_tag(&root->fs_info->pinned_radix, |
9f5fae2f | 114 | (void **)gang, 0, |
e20d96d6 CM |
115 | ARRAY_SIZE(gang), |
116 | CTREE_EXTENT_PINNED); | |
a28ec197 CM |
117 | if (!ret) |
118 | break; | |
88fd146c | 119 | if (!first) |
d5719762 | 120 | first = gang[0]->b_blocknr; |
0579da42 | 121 | for (i = 0; i < ret; i++) { |
9f5fae2f | 122 | radix_tree_delete(&root->fs_info->pinned_radix, |
d5719762 CM |
123 | gang[i]->b_blocknr); |
124 | brelse(gang[i]); | |
0579da42 | 125 | } |
a28ec197 | 126 | } |
d5719762 CM |
127 | if (root->fs_info->last_insert.objectid > first) |
128 | root->fs_info->last_insert.objectid = first; | |
9f5fae2f | 129 | root->fs_info->last_insert.offset = 0; |
a28ec197 CM |
130 | return 0; |
131 | } | |
132 | ||
e089f05c CM |
133 | static int finish_current_insert(struct btrfs_trans_handle *trans, struct |
134 | btrfs_root *extent_root) | |
037e6390 | 135 | { |
e2fa7227 | 136 | struct btrfs_key ins; |
234b63a0 | 137 | struct btrfs_extent_item extent_item; |
037e6390 CM |
138 | int i; |
139 | int ret; | |
1261ec42 CM |
140 | u64 super_blocks_used; |
141 | struct btrfs_fs_info *info = extent_root->fs_info; | |
037e6390 | 142 | |
cf27e1ee CM |
143 | btrfs_set_extent_refs(&extent_item, 1); |
144 | btrfs_set_extent_owner(&extent_item, | |
e20d96d6 | 145 | btrfs_header_parentid(btrfs_buffer_header(extent_root->node))); |
037e6390 CM |
146 | ins.offset = 1; |
147 | ins.flags = 0; | |
62e2749e | 148 | btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY); |
037e6390 | 149 | |
9f5fae2f CM |
150 | for (i = 0; i < extent_root->fs_info->current_insert.flags; i++) { |
151 | ins.objectid = extent_root->fs_info->current_insert.objectid + | |
152 | i; | |
1261ec42 CM |
153 | super_blocks_used = btrfs_super_blocks_used(info->disk_super); |
154 | btrfs_set_super_blocks_used(info->disk_super, | |
155 | super_blocks_used + 1); | |
e089f05c CM |
156 | ret = btrfs_insert_item(trans, extent_root, &ins, &extent_item, |
157 | sizeof(extent_item)); | |
037e6390 CM |
158 | BUG_ON(ret); |
159 | } | |
9f5fae2f | 160 | extent_root->fs_info->current_insert.offset = 0; |
037e6390 CM |
161 | return 0; |
162 | } | |
163 | ||
e20d96d6 CM |
164 | static int pin_down_block(struct btrfs_root *root, u64 blocknr, int tag) |
165 | { | |
166 | int err; | |
d5719762 CM |
167 | struct buffer_head *bh = sb_getblk(root->fs_info->sb, blocknr); |
168 | BUG_ON(!bh); | |
e20d96d6 | 169 | err = radix_tree_insert(&root->fs_info->pinned_radix, |
d5719762 | 170 | blocknr, bh); |
e20d96d6 CM |
171 | BUG_ON(err); |
172 | if (err) | |
173 | return err; | |
174 | radix_tree_tag_set(&root->fs_info->pinned_radix, blocknr, | |
175 | tag); | |
176 | return 0; | |
177 | } | |
178 | ||
fec577fb | 179 | /* |
a28ec197 | 180 | * remove an extent from the root, returns 0 on success |
fec577fb | 181 | */ |
e089f05c | 182 | static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root |
e20d96d6 | 183 | *root, u64 blocknr, u64 num_blocks) |
a28ec197 | 184 | { |
234b63a0 | 185 | struct btrfs_path path; |
e2fa7227 | 186 | struct btrfs_key key; |
1261ec42 CM |
187 | struct btrfs_fs_info *info = root->fs_info; |
188 | struct btrfs_root *extent_root = info->extent_root; | |
a28ec197 | 189 | int ret; |
234b63a0 | 190 | struct btrfs_extent_item *ei; |
e2fa7227 | 191 | struct btrfs_key ins; |
cf27e1ee | 192 | u32 refs; |
037e6390 | 193 | |
a28ec197 CM |
194 | key.objectid = blocknr; |
195 | key.flags = 0; | |
62e2749e | 196 | btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY); |
a28ec197 CM |
197 | key.offset = num_blocks; |
198 | ||
e089f05c | 199 | find_free_extent(trans, root, 0, 0, (u64)-1, &ins); |
234b63a0 | 200 | btrfs_init_path(&path); |
e089f05c | 201 | ret = btrfs_search_slot(trans, extent_root, &key, &path, -1, 1); |
a28ec197 | 202 | if (ret) { |
2e635a27 | 203 | printk("failed to find %Lu\n", key.objectid); |
234b63a0 | 204 | btrfs_print_tree(extent_root, extent_root->node); |
2e635a27 | 205 | printk("failed to find %Lu\n", key.objectid); |
a28ec197 CM |
206 | BUG(); |
207 | } | |
e20d96d6 | 208 | ei = btrfs_item_ptr(btrfs_buffer_leaf(path.nodes[0]), path.slots[0], |
123abc88 | 209 | struct btrfs_extent_item); |
a28ec197 | 210 | BUG_ON(ei->refs == 0); |
cf27e1ee CM |
211 | refs = btrfs_extent_refs(ei) - 1; |
212 | btrfs_set_extent_refs(ei, refs); | |
213 | if (refs == 0) { | |
1261ec42 | 214 | u64 super_blocks_used; |
1261ec42 CM |
215 | super_blocks_used = btrfs_super_blocks_used(info->disk_super); |
216 | btrfs_set_super_blocks_used(info->disk_super, | |
217 | super_blocks_used - num_blocks); | |
e089f05c | 218 | ret = btrfs_del_item(trans, extent_root, &path); |
e20d96d6 | 219 | if (extent_root->fs_info->last_insert.objectid > |
9f5fae2f CM |
220 | blocknr) |
221 | extent_root->fs_info->last_insert.objectid = blocknr; | |
a28ec197 CM |
222 | if (ret) |
223 | BUG(); | |
224 | } | |
d5719762 | 225 | mark_buffer_dirty(path.nodes[0]); |
234b63a0 | 226 | btrfs_release_path(extent_root, &path); |
e089f05c | 227 | finish_current_insert(trans, extent_root); |
a28ec197 CM |
228 | return ret; |
229 | } | |
230 | ||
a28ec197 CM |
231 | /* |
232 | * find all the blocks marked as pending in the radix tree and remove | |
233 | * them from the extent map | |
234 | */ | |
e089f05c CM |
235 | static int del_pending_extents(struct btrfs_trans_handle *trans, struct |
236 | btrfs_root *extent_root) | |
a28ec197 CM |
237 | { |
238 | int ret; | |
e20d96d6 CM |
239 | int wret; |
240 | int err = 0; | |
d5719762 | 241 | struct buffer_head *gang[4]; |
a28ec197 | 242 | int i; |
e20d96d6 | 243 | struct radix_tree_root *radix = &extent_root->fs_info->pinned_radix; |
a28ec197 CM |
244 | |
245 | while(1) { | |
9f5fae2f | 246 | ret = radix_tree_gang_lookup_tag( |
e20d96d6 | 247 | &extent_root->fs_info->pinned_radix, |
9f5fae2f CM |
248 | (void **)gang, 0, |
249 | ARRAY_SIZE(gang), | |
250 | CTREE_EXTENT_PENDING_DEL); | |
a28ec197 CM |
251 | if (!ret) |
252 | break; | |
253 | for (i = 0; i < ret; i++) { | |
d5719762 CM |
254 | radix_tree_tag_set(radix, gang[i]->b_blocknr, |
255 | CTREE_EXTENT_PINNED); | |
256 | radix_tree_tag_clear(radix, gang[i]->b_blocknr, | |
9f5fae2f | 257 | CTREE_EXTENT_PENDING_DEL); |
d5719762 CM |
258 | wret = __free_extent(trans, extent_root, |
259 | gang[i]->b_blocknr, 1); | |
e20d96d6 CM |
260 | if (wret) |
261 | err = wret; | |
fec577fb CM |
262 | } |
263 | } | |
e20d96d6 | 264 | return err; |
fec577fb CM |
265 | } |
266 | ||
267 | /* | |
268 | * remove an extent from the root, returns 0 on success | |
269 | */ | |
e089f05c CM |
270 | int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root |
271 | *root, u64 blocknr, u64 num_blocks, int pin) | |
fec577fb | 272 | { |
9f5fae2f | 273 | struct btrfs_root *extent_root = root->fs_info->extent_root; |
e20d96d6 | 274 | struct buffer_head *t; |
fec577fb CM |
275 | int pending_ret; |
276 | int ret; | |
a28ec197 | 277 | |
fec577fb | 278 | if (root == extent_root) { |
a28ec197 | 279 | t = find_tree_block(root, blocknr); |
e20d96d6 | 280 | pin_down_block(root, blocknr, CTREE_EXTENT_PENDING_DEL); |
fec577fb CM |
281 | return 0; |
282 | } | |
e20d96d6 CM |
283 | if (pin) { |
284 | ret = pin_down_block(root, blocknr, CTREE_EXTENT_PINNED); | |
285 | BUG_ON(ret); | |
286 | } | |
287 | ret = __free_extent(trans, root, blocknr, num_blocks); | |
288 | pending_ret = del_pending_extents(trans, root->fs_info->extent_root); | |
fec577fb CM |
289 | return ret ? ret : pending_ret; |
290 | } | |
291 | ||
292 | /* | |
293 | * walks the btree of allocated extents and find a hole of a given size. | |
294 | * The key ins is changed to record the hole: | |
295 | * ins->objectid == block start | |
62e2749e | 296 | * ins->flags = BTRFS_EXTENT_ITEM_KEY |
fec577fb CM |
297 | * ins->offset == number of blocks |
298 | * Any available blocks before search_start are skipped. | |
299 | */ | |
e089f05c CM |
300 | static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root |
301 | *orig_root, u64 num_blocks, u64 search_start, u64 | |
302 | search_end, struct btrfs_key *ins) | |
fec577fb | 303 | { |
234b63a0 | 304 | struct btrfs_path path; |
e2fa7227 | 305 | struct btrfs_key key; |
fec577fb CM |
306 | int ret; |
307 | u64 hole_size = 0; | |
308 | int slot = 0; | |
e20d96d6 | 309 | u64 last_block = 0; |
037e6390 | 310 | u64 test_block; |
fec577fb | 311 | int start_found; |
234b63a0 | 312 | struct btrfs_leaf *l; |
9f5fae2f | 313 | struct btrfs_root * root = orig_root->fs_info->extent_root; |
0579da42 | 314 | int total_needed = num_blocks; |
e20d96d6 | 315 | int level; |
fec577fb | 316 | |
e20d96d6 CM |
317 | level = btrfs_header_level(btrfs_buffer_header(root->node)); |
318 | total_needed += (level + 1) * 3; | |
9f5fae2f CM |
319 | if (root->fs_info->last_insert.objectid > search_start) |
320 | search_start = root->fs_info->last_insert.objectid; | |
62e2749e CM |
321 | |
322 | ins->flags = 0; | |
323 | btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY); | |
324 | ||
fec577fb | 325 | check_failed: |
234b63a0 | 326 | btrfs_init_path(&path); |
fec577fb CM |
327 | ins->objectid = search_start; |
328 | ins->offset = 0; | |
fec577fb | 329 | start_found = 0; |
e089f05c | 330 | ret = btrfs_search_slot(trans, root, ins, &path, 0, 0); |
0f70abe2 CM |
331 | if (ret < 0) |
332 | goto error; | |
aa5d6bed | 333 | |
0579da42 CM |
334 | if (path.slots[0] > 0) |
335 | path.slots[0]--; | |
336 | ||
fec577fb | 337 | while (1) { |
e20d96d6 | 338 | l = btrfs_buffer_leaf(path.nodes[0]); |
fec577fb | 339 | slot = path.slots[0]; |
7518a238 | 340 | if (slot >= btrfs_header_nritems(&l->header)) { |
234b63a0 | 341 | ret = btrfs_next_leaf(root, &path); |
fec577fb CM |
342 | if (ret == 0) |
343 | continue; | |
0f70abe2 CM |
344 | if (ret < 0) |
345 | goto error; | |
fec577fb CM |
346 | if (!start_found) { |
347 | ins->objectid = search_start; | |
037e6390 | 348 | ins->offset = (u64)-1; |
fec577fb CM |
349 | start_found = 1; |
350 | goto check_pending; | |
351 | } | |
352 | ins->objectid = last_block > search_start ? | |
353 | last_block : search_start; | |
037e6390 | 354 | ins->offset = (u64)-1; |
fec577fb CM |
355 | goto check_pending; |
356 | } | |
e2fa7227 CM |
357 | btrfs_disk_key_to_cpu(&key, &l->items[slot].key); |
358 | if (key.objectid >= search_start) { | |
fec577fb | 359 | if (start_found) { |
0579da42 CM |
360 | if (last_block < search_start) |
361 | last_block = search_start; | |
e2fa7227 | 362 | hole_size = key.objectid - last_block; |
037e6390 | 363 | if (hole_size > total_needed) { |
fec577fb | 364 | ins->objectid = last_block; |
037e6390 | 365 | ins->offset = hole_size; |
fec577fb CM |
366 | goto check_pending; |
367 | } | |
0579da42 | 368 | } |
fec577fb | 369 | } |
0579da42 | 370 | start_found = 1; |
e2fa7227 | 371 | last_block = key.objectid + key.offset; |
fec577fb CM |
372 | path.slots[0]++; |
373 | } | |
374 | // FIXME -ENOSPC | |
375 | check_pending: | |
376 | /* we have to make sure we didn't find an extent that has already | |
377 | * been allocated by the map tree or the original allocation | |
378 | */ | |
234b63a0 | 379 | btrfs_release_path(root, &path); |
fec577fb | 380 | BUG_ON(ins->objectid < search_start); |
037e6390 CM |
381 | for (test_block = ins->objectid; |
382 | test_block < ins->objectid + total_needed; test_block++) { | |
9f5fae2f CM |
383 | if (radix_tree_lookup(&root->fs_info->pinned_radix, |
384 | test_block)) { | |
037e6390 | 385 | search_start = test_block + 1; |
fec577fb CM |
386 | goto check_failed; |
387 | } | |
388 | } | |
9f5fae2f CM |
389 | BUG_ON(root->fs_info->current_insert.offset); |
390 | root->fs_info->current_insert.offset = total_needed - num_blocks; | |
391 | root->fs_info->current_insert.objectid = ins->objectid + num_blocks; | |
392 | root->fs_info->current_insert.flags = 0; | |
393 | root->fs_info->last_insert.objectid = ins->objectid; | |
037e6390 | 394 | ins->offset = num_blocks; |
fec577fb | 395 | return 0; |
0f70abe2 | 396 | error: |
234b63a0 | 397 | btrfs_release_path(root, &path); |
0f70abe2 | 398 | return ret; |
fec577fb CM |
399 | } |
400 | ||
fec577fb CM |
401 | /* |
402 | * finds a free extent and does all the dirty work required for allocation | |
403 | * returns the key for the extent through ins, and a tree buffer for | |
404 | * the first block of the extent through buf. | |
405 | * | |
406 | * returns 0 if everything worked, non-zero otherwise. | |
407 | */ | |
e089f05c CM |
408 | static int alloc_extent(struct btrfs_trans_handle *trans, struct btrfs_root |
409 | *root, u64 num_blocks, u64 search_start, u64 | |
410 | search_end, u64 owner, struct btrfs_key *ins) | |
fec577fb CM |
411 | { |
412 | int ret; | |
413 | int pending_ret; | |
1261ec42 CM |
414 | u64 super_blocks_used; |
415 | struct btrfs_fs_info *info = root->fs_info; | |
416 | struct btrfs_root *extent_root = info->extent_root; | |
234b63a0 | 417 | struct btrfs_extent_item extent_item; |
037e6390 | 418 | |
cf27e1ee CM |
419 | btrfs_set_extent_refs(&extent_item, 1); |
420 | btrfs_set_extent_owner(&extent_item, owner); | |
fec577fb | 421 | |
037e6390 | 422 | if (root == extent_root) { |
9f5fae2f | 423 | BUG_ON(extent_root->fs_info->current_insert.offset == 0); |
037e6390 | 424 | BUG_ON(num_blocks != 1); |
9f5fae2f CM |
425 | BUG_ON(extent_root->fs_info->current_insert.flags == |
426 | extent_root->fs_info->current_insert.offset); | |
037e6390 | 427 | ins->offset = 1; |
9f5fae2f CM |
428 | ins->objectid = extent_root->fs_info->current_insert.objectid + |
429 | extent_root->fs_info->current_insert.flags++; | |
fec577fb CM |
430 | return 0; |
431 | } | |
e089f05c | 432 | ret = find_free_extent(trans, root, num_blocks, search_start, |
037e6390 CM |
433 | search_end, ins); |
434 | if (ret) | |
435 | return ret; | |
fec577fb | 436 | |
1261ec42 CM |
437 | super_blocks_used = btrfs_super_blocks_used(info->disk_super); |
438 | btrfs_set_super_blocks_used(info->disk_super, super_blocks_used + | |
439 | num_blocks); | |
e089f05c CM |
440 | ret = btrfs_insert_item(trans, extent_root, ins, &extent_item, |
441 | sizeof(extent_item)); | |
037e6390 | 442 | |
e089f05c | 443 | finish_current_insert(trans, extent_root); |
e20d96d6 | 444 | pending_ret = del_pending_extents(trans, extent_root); |
037e6390 CM |
445 | if (ret) |
446 | return ret; | |
447 | if (pending_ret) | |
448 | return pending_ret; | |
449 | return 0; | |
fec577fb CM |
450 | } |
451 | ||
452 | /* | |
453 | * helper function to allocate a block for a given tree | |
454 | * returns the tree buffer or NULL. | |
455 | */ | |
e20d96d6 | 456 | struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans, |
e089f05c | 457 | struct btrfs_root *root) |
fec577fb | 458 | { |
e2fa7227 | 459 | struct btrfs_key ins; |
fec577fb | 460 | int ret; |
e20d96d6 | 461 | struct buffer_head *buf; |
fec577fb | 462 | |
e089f05c | 463 | ret = alloc_extent(trans, root, 1, 0, (unsigned long)-1, |
e20d96d6 | 464 | btrfs_header_parentid(btrfs_buffer_header(root->node)), &ins); |
fec577fb CM |
465 | if (ret) { |
466 | BUG(); | |
467 | return NULL; | |
468 | } | |
037e6390 | 469 | buf = find_tree_block(root, ins.objectid); |
e089f05c | 470 | dirty_tree_block(trans, root, buf); |
fec577fb CM |
471 | return buf; |
472 | } | |
a28ec197 | 473 | |
9aca1d51 CM |
474 | /* |
475 | * helper function for drop_snapshot, this walks down the tree dropping ref | |
476 | * counts as it goes. | |
477 | */ | |
e089f05c CM |
478 | static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root |
479 | *root, struct btrfs_path *path, int *level) | |
20524f02 | 480 | { |
e20d96d6 CM |
481 | struct buffer_head *next; |
482 | struct buffer_head *cur; | |
20524f02 CM |
483 | u64 blocknr; |
484 | int ret; | |
485 | u32 refs; | |
486 | ||
e20d96d6 | 487 | ret = lookup_block_ref(trans, root, path->nodes[*level]->b_blocknr, |
e089f05c | 488 | &refs); |
20524f02 CM |
489 | BUG_ON(ret); |
490 | if (refs > 1) | |
491 | goto out; | |
9aca1d51 CM |
492 | /* |
493 | * walk down to the last node level and free all the leaves | |
494 | */ | |
20524f02 CM |
495 | while(*level > 0) { |
496 | cur = path->nodes[*level]; | |
7518a238 | 497 | if (path->slots[*level] >= |
e20d96d6 | 498 | btrfs_header_nritems(btrfs_buffer_header(cur))) |
20524f02 | 499 | break; |
e20d96d6 CM |
500 | blocknr = btrfs_node_blockptr(btrfs_buffer_node(cur), |
501 | path->slots[*level]); | |
e089f05c | 502 | ret = lookup_block_ref(trans, root, blocknr, &refs); |
20524f02 CM |
503 | if (refs != 1 || *level == 1) { |
504 | path->slots[*level]++; | |
e089f05c | 505 | ret = btrfs_free_extent(trans, root, blocknr, 1, 1); |
20524f02 CM |
506 | BUG_ON(ret); |
507 | continue; | |
508 | } | |
509 | BUG_ON(ret); | |
510 | next = read_tree_block(root, blocknr); | |
83e15a28 | 511 | if (path->nodes[*level-1]) |
234b63a0 | 512 | btrfs_block_release(root, path->nodes[*level-1]); |
20524f02 | 513 | path->nodes[*level-1] = next; |
e20d96d6 | 514 | *level = btrfs_header_level(btrfs_buffer_header(next)); |
20524f02 CM |
515 | path->slots[*level] = 0; |
516 | } | |
517 | out: | |
e20d96d6 CM |
518 | ret = btrfs_free_extent(trans, root, path->nodes[*level]->b_blocknr, |
519 | 1, 1); | |
234b63a0 | 520 | btrfs_block_release(root, path->nodes[*level]); |
20524f02 CM |
521 | path->nodes[*level] = NULL; |
522 | *level += 1; | |
523 | BUG_ON(ret); | |
524 | return 0; | |
525 | } | |
526 | ||
9aca1d51 CM |
527 | /* |
528 | * helper for dropping snapshots. This walks back up the tree in the path | |
529 | * to find the first node higher up where we haven't yet gone through | |
530 | * all the slots | |
531 | */ | |
e089f05c CM |
532 | static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root |
533 | *root, struct btrfs_path *path, int *level) | |
20524f02 CM |
534 | { |
535 | int i; | |
536 | int slot; | |
537 | int ret; | |
234b63a0 | 538 | for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) { |
20524f02 | 539 | slot = path->slots[i]; |
e20d96d6 CM |
540 | if (slot < btrfs_header_nritems( |
541 | btrfs_buffer_header(path->nodes[i])) - 1) { | |
20524f02 CM |
542 | path->slots[i]++; |
543 | *level = i; | |
544 | return 0; | |
545 | } else { | |
e089f05c | 546 | ret = btrfs_free_extent(trans, root, |
e20d96d6 | 547 | path->nodes[*level]->b_blocknr, |
e089f05c | 548 | 1, 1); |
234b63a0 | 549 | btrfs_block_release(root, path->nodes[*level]); |
83e15a28 | 550 | path->nodes[*level] = NULL; |
20524f02 CM |
551 | *level = i + 1; |
552 | BUG_ON(ret); | |
553 | } | |
554 | } | |
555 | return 1; | |
556 | } | |
557 | ||
9aca1d51 CM |
558 | /* |
559 | * drop the reference count on the tree rooted at 'snap'. This traverses | |
560 | * the tree freeing any blocks that have a ref count of zero after being | |
561 | * decremented. | |
562 | */ | |
e089f05c | 563 | int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root |
e20d96d6 | 564 | *root, struct buffer_head *snap) |
20524f02 | 565 | { |
3768f368 | 566 | int ret = 0; |
9aca1d51 | 567 | int wret; |
20524f02 | 568 | int level; |
234b63a0 | 569 | struct btrfs_path path; |
20524f02 CM |
570 | int i; |
571 | int orig_level; | |
572 | ||
234b63a0 | 573 | btrfs_init_path(&path); |
20524f02 | 574 | |
e20d96d6 | 575 | level = btrfs_header_level(btrfs_buffer_header(snap)); |
20524f02 CM |
576 | orig_level = level; |
577 | path.nodes[level] = snap; | |
578 | path.slots[level] = 0; | |
579 | while(1) { | |
e089f05c | 580 | wret = walk_down_tree(trans, root, &path, &level); |
9aca1d51 | 581 | if (wret > 0) |
20524f02 | 582 | break; |
9aca1d51 CM |
583 | if (wret < 0) |
584 | ret = wret; | |
585 | ||
e089f05c | 586 | wret = walk_up_tree(trans, root, &path, &level); |
9aca1d51 | 587 | if (wret > 0) |
20524f02 | 588 | break; |
9aca1d51 CM |
589 | if (wret < 0) |
590 | ret = wret; | |
20524f02 | 591 | } |
83e15a28 CM |
592 | for (i = 0; i <= orig_level; i++) { |
593 | if (path.nodes[i]) { | |
234b63a0 | 594 | btrfs_block_release(root, path.nodes[i]); |
83e15a28 | 595 | } |
20524f02 | 596 | } |
9aca1d51 | 597 | return ret; |
20524f02 | 598 | } |