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