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