1 #include <linux/module.h>
4 #include "print-tree.h"
5 #include "transaction.h"
7 static int find_free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
8 *orig_root
, u64 num_blocks
, u64 search_start
, u64
9 search_end
, struct btrfs_key
*ins
);
10 static int finish_current_insert(struct btrfs_trans_handle
*trans
, struct
11 btrfs_root
*extent_root
);
12 static int del_pending_extents(struct btrfs_trans_handle
*trans
, struct
13 btrfs_root
*extent_root
);
15 struct btrfs_block_group_cache
*btrfs_find_block_group(struct btrfs_root
*root
,
16 struct btrfs_block_group_cache
19 struct btrfs_block_group_cache
*cache
[8];
20 struct btrfs_block_group_cache
*found_group
= NULL
;
21 struct btrfs_fs_info
*info
= root
->fs_info
;
29 used
= btrfs_block_group_used(&hint
->item
);
30 if (used
< (hint
->key
.offset
* 2) / 3) {
33 radix_tree_tag_clear(&info
->block_group_radix
,
34 hint
->key
.objectid
+ hint
->key
.offset
- 1,
35 BTRFS_BLOCK_GROUP_AVAIL
);
36 last
= hint
->key
.objectid
+ hint
->key
.offset
;
43 ret
= radix_tree_gang_lookup_tag(&info
->block_group_radix
,
45 last
, ARRAY_SIZE(cache
),
46 BTRFS_BLOCK_GROUP_AVAIL
);
49 for (i
= 0; i
< ret
; i
++) {
50 used
= btrfs_block_group_used(&cache
[i
]->item
);
51 if (used
< (cache
[i
]->key
.offset
* 2) / 3) {
52 info
->block_group_cache
= cache
[i
];
53 found_group
= cache
[i
];
56 radix_tree_tag_clear(&info
->block_group_radix
,
57 cache
[i
]->key
.objectid
+
58 cache
[i
]->key
.offset
- 1,
59 BTRFS_BLOCK_GROUP_AVAIL
);
60 last
= cache
[i
]->key
.objectid
+
67 ret
= radix_tree_gang_lookup(&info
->block_group_radix
,
69 last
, ARRAY_SIZE(cache
));
72 for (i
= 0; i
< ret
; i
++) {
73 used
= btrfs_block_group_used(&cache
[i
]->item
);
74 if (used
< cache
[i
]->key
.offset
) {
75 info
->block_group_cache
= cache
[i
];
76 found_group
= cache
[i
];
79 radix_tree_tag_clear(&info
->block_group_radix
,
80 cache
[i
]->key
.objectid
+
81 cache
[i
]->key
.offset
- 1,
82 BTRFS_BLOCK_GROUP_AVAIL
);
83 last
= cache
[i
]->key
.objectid
+
87 info
->block_group_cache
= NULL
;
95 ret
= radix_tree_gang_lookup(&info
->block_group_radix
,
96 (void **)&found_group
, 0, 1);
102 int btrfs_inc_extent_ref(struct btrfs_trans_handle
*trans
,
103 struct btrfs_root
*root
,
104 u64 blocknr
, u64 num_blocks
)
106 struct btrfs_path
*path
;
108 struct btrfs_key key
;
109 struct btrfs_leaf
*l
;
110 struct btrfs_extent_item
*item
;
111 struct btrfs_key ins
;
114 find_free_extent(trans
, root
->fs_info
->extent_root
, 0, 0, (u64
)-1,
116 path
= btrfs_alloc_path();
118 btrfs_init_path(path
);
119 key
.objectid
= blocknr
;
121 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
122 key
.offset
= num_blocks
;
123 ret
= btrfs_search_slot(trans
, root
->fs_info
->extent_root
, &key
, path
,
126 printk("can't find block %Lu %Lu\n", blocknr
, num_blocks
);
130 l
= btrfs_buffer_leaf(path
->nodes
[0]);
131 item
= btrfs_item_ptr(l
, path
->slots
[0], struct btrfs_extent_item
);
132 refs
= btrfs_extent_refs(item
);
133 btrfs_set_extent_refs(item
, refs
+ 1);
134 btrfs_mark_buffer_dirty(path
->nodes
[0]);
136 btrfs_release_path(root
->fs_info
->extent_root
, path
);
137 btrfs_free_path(path
);
138 finish_current_insert(trans
, root
->fs_info
->extent_root
);
139 del_pending_extents(trans
, root
->fs_info
->extent_root
);
143 static int lookup_extent_ref(struct btrfs_trans_handle
*trans
,
144 struct btrfs_root
*root
, u64 blocknr
,
145 u64 num_blocks
, u32
*refs
)
147 struct btrfs_path
*path
;
149 struct btrfs_key key
;
150 struct btrfs_leaf
*l
;
151 struct btrfs_extent_item
*item
;
153 path
= btrfs_alloc_path();
154 btrfs_init_path(path
);
155 key
.objectid
= blocknr
;
156 key
.offset
= num_blocks
;
158 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
159 ret
= btrfs_search_slot(trans
, root
->fs_info
->extent_root
, &key
, path
,
163 l
= btrfs_buffer_leaf(path
->nodes
[0]);
164 item
= btrfs_item_ptr(l
, path
->slots
[0], struct btrfs_extent_item
);
165 *refs
= btrfs_extent_refs(item
);
166 btrfs_release_path(root
->fs_info
->extent_root
, path
);
167 btrfs_free_path(path
);
171 int btrfs_inc_root_ref(struct btrfs_trans_handle
*trans
,
172 struct btrfs_root
*root
)
174 return btrfs_inc_extent_ref(trans
, root
, bh_blocknr(root
->node
), 1);
177 int btrfs_inc_ref(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
178 struct buffer_head
*buf
)
181 struct btrfs_node
*buf_node
;
182 struct btrfs_leaf
*buf_leaf
;
183 struct btrfs_disk_key
*key
;
184 struct btrfs_file_extent_item
*fi
;
191 buf_node
= btrfs_buffer_node(buf
);
192 leaf
= btrfs_is_leaf(buf_node
);
193 buf_leaf
= btrfs_buffer_leaf(buf
);
194 for (i
= 0; i
< btrfs_header_nritems(&buf_node
->header
); i
++) {
196 key
= &buf_leaf
->items
[i
].key
;
197 if (btrfs_disk_key_type(key
) != BTRFS_EXTENT_DATA_KEY
)
199 fi
= btrfs_item_ptr(buf_leaf
, i
,
200 struct btrfs_file_extent_item
);
201 if (btrfs_file_extent_type(fi
) ==
202 BTRFS_FILE_EXTENT_INLINE
)
204 ret
= btrfs_inc_extent_ref(trans
, root
,
205 btrfs_file_extent_disk_blocknr(fi
),
206 btrfs_file_extent_disk_num_blocks(fi
));
209 blocknr
= btrfs_node_blockptr(buf_node
, i
);
210 ret
= btrfs_inc_extent_ref(trans
, root
, blocknr
, 1);
217 static int write_one_cache_group(struct btrfs_trans_handle
*trans
,
218 struct btrfs_root
*root
,
219 struct btrfs_path
*path
,
220 struct btrfs_block_group_cache
*cache
)
224 struct btrfs_root
*extent_root
= root
->fs_info
->extent_root
;
225 struct btrfs_block_group_item
*bi
;
226 struct btrfs_key ins
;
228 find_free_extent(trans
, extent_root
, 0, 0, (u64
)-1, &ins
);
229 ret
= btrfs_search_slot(trans
, extent_root
, &cache
->key
, path
, 0, 1);
231 bi
= btrfs_item_ptr(btrfs_buffer_leaf(path
->nodes
[0]), path
->slots
[0],
232 struct btrfs_block_group_item
);
233 memcpy(bi
, &cache
->item
, sizeof(*bi
));
234 mark_buffer_dirty(path
->nodes
[0]);
235 btrfs_release_path(extent_root
, path
);
237 finish_current_insert(trans
, extent_root
);
238 pending_ret
= del_pending_extents(trans
, extent_root
);
247 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle
*trans
,
248 struct btrfs_root
*root
)
250 struct btrfs_block_group_cache
*cache
[8];
254 struct radix_tree_root
*radix
= &root
->fs_info
->block_group_radix
;
256 struct btrfs_path
*path
;
258 path
= btrfs_alloc_path();
263 ret
= radix_tree_gang_lookup_tag(radix
, (void **)cache
,
264 0, ARRAY_SIZE(cache
),
265 BTRFS_BLOCK_GROUP_DIRTY
);
268 for (i
= 0; i
< ret
; i
++) {
269 radix_tree_tag_clear(radix
, cache
[i
]->key
.objectid
+
270 cache
[i
]->key
.offset
- 1,
271 BTRFS_BLOCK_GROUP_DIRTY
);
272 err
= write_one_cache_group(trans
, root
,
276 cache
[i
]->last_alloc
= cache
[i
]->first_free
;
279 btrfs_free_path(path
);
283 static int update_block_group(struct btrfs_trans_handle
*trans
,
284 struct btrfs_root
*root
,
285 u64 blocknr
, u64 num
, int alloc
)
287 struct btrfs_block_group_cache
*cache
;
288 struct btrfs_fs_info
*info
= root
->fs_info
;
294 ret
= radix_tree_gang_lookup(&info
->block_group_radix
,
295 (void **)&cache
, blocknr
, 1);
297 printk(KERN_CRIT
"blocknr %Lu lookup failed\n",
301 block_in_group
= blocknr
- cache
->key
.objectid
;
302 WARN_ON(block_in_group
> cache
->key
.offset
);
303 radix_tree_tag_set(&info
->block_group_radix
,
304 cache
->key
.objectid
+ cache
->key
.offset
- 1,
305 BTRFS_BLOCK_GROUP_DIRTY
);
307 old_val
= btrfs_block_group_used(&cache
->item
);
308 num
= min(total
, cache
->key
.offset
- block_in_group
);
313 if (blocknr
> cache
->last_alloc
)
314 cache
->last_alloc
= blocknr
;
317 if (blocknr
< cache
->first_free
)
318 cache
->first_free
= blocknr
;
320 btrfs_set_block_group_used(&cache
->item
, old_val
);
325 static int try_remove_page(struct address_space
*mapping
, unsigned long index
)
328 ret
= invalidate_mapping_pages(mapping
, index
, index
);
332 int btrfs_finish_extent_commit(struct btrfs_trans_handle
*trans
, struct
335 unsigned long gang
[8];
336 struct inode
*btree_inode
= root
->fs_info
->btree_inode
;
340 struct radix_tree_root
*pinned_radix
= &root
->fs_info
->pinned_radix
;
343 ret
= find_first_radix_bit(pinned_radix
, gang
,
349 for (i
= 0; i
< ret
; i
++) {
350 clear_radix_bit(pinned_radix
, gang
[i
]);
351 try_remove_page(btree_inode
->i_mapping
,
352 gang
[i
] << (PAGE_CACHE_SHIFT
-
353 btree_inode
->i_blkbits
));
359 static int finish_current_insert(struct btrfs_trans_handle
*trans
, struct
360 btrfs_root
*extent_root
)
362 struct btrfs_key ins
;
363 struct btrfs_extent_item extent_item
;
366 u64 super_blocks_used
;
367 struct btrfs_fs_info
*info
= extent_root
->fs_info
;
369 btrfs_set_extent_refs(&extent_item
, 1);
372 btrfs_set_key_type(&ins
, BTRFS_EXTENT_ITEM_KEY
);
373 btrfs_set_extent_owner(&extent_item
, extent_root
->root_key
.objectid
);
375 for (i
= 0; i
< extent_root
->fs_info
->extent_tree_insert_nr
; i
++) {
376 ins
.objectid
= extent_root
->fs_info
->extent_tree_insert
[i
];
377 super_blocks_used
= btrfs_super_blocks_used(info
->disk_super
);
378 btrfs_set_super_blocks_used(info
->disk_super
,
379 super_blocks_used
+ 1);
380 ret
= btrfs_insert_item(trans
, extent_root
, &ins
, &extent_item
,
381 sizeof(extent_item
));
384 extent_root
->fs_info
->extent_tree_insert_nr
= 0;
385 extent_root
->fs_info
->extent_tree_prealloc_nr
= 0;
389 static int pin_down_block(struct btrfs_root
*root
, u64 blocknr
, int pending
)
392 struct btrfs_header
*header
;
393 struct buffer_head
*bh
;
396 bh
= btrfs_find_tree_block(root
, blocknr
);
398 if (buffer_uptodate(bh
)) {
400 root
->fs_info
->running_transaction
->transid
;
401 header
= btrfs_buffer_header(bh
);
402 if (btrfs_header_generation(header
) ==
404 btrfs_block_release(root
, bh
);
408 btrfs_block_release(root
, bh
);
410 err
= set_radix_bit(&root
->fs_info
->pinned_radix
, blocknr
);
412 err
= set_radix_bit(&root
->fs_info
->pending_del_radix
, blocknr
);
419 * remove an extent from the root, returns 0 on success
421 static int __free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
422 *root
, u64 blocknr
, u64 num_blocks
, int pin
)
424 struct btrfs_path
*path
;
425 struct btrfs_key key
;
426 struct btrfs_fs_info
*info
= root
->fs_info
;
427 struct btrfs_root
*extent_root
= info
->extent_root
;
429 struct btrfs_extent_item
*ei
;
430 struct btrfs_key ins
;
433 key
.objectid
= blocknr
;
435 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
436 key
.offset
= num_blocks
;
438 find_free_extent(trans
, root
, 0, 0, (u64
)-1, &ins
);
439 path
= btrfs_alloc_path();
441 btrfs_init_path(path
);
443 ret
= btrfs_search_slot(trans
, extent_root
, &key
, path
, -1, 1);
445 printk("failed to find %Lu\n", key
.objectid
);
446 btrfs_print_tree(extent_root
, extent_root
->node
);
447 printk("failed to find %Lu\n", key
.objectid
);
450 ei
= btrfs_item_ptr(btrfs_buffer_leaf(path
->nodes
[0]), path
->slots
[0],
451 struct btrfs_extent_item
);
452 BUG_ON(ei
->refs
== 0);
453 refs
= btrfs_extent_refs(ei
) - 1;
454 btrfs_set_extent_refs(ei
, refs
);
455 btrfs_mark_buffer_dirty(path
->nodes
[0]);
457 u64 super_blocks_used
;
460 ret
= pin_down_block(root
, blocknr
, 0);
464 super_blocks_used
= btrfs_super_blocks_used(info
->disk_super
);
465 btrfs_set_super_blocks_used(info
->disk_super
,
466 super_blocks_used
- num_blocks
);
467 ret
= btrfs_del_item(trans
, extent_root
, path
);
470 ret
= update_block_group(trans
, root
, blocknr
, num_blocks
, 0);
473 btrfs_release_path(extent_root
, path
);
474 btrfs_free_path(path
);
475 finish_current_insert(trans
, extent_root
);
480 * find all the blocks marked as pending in the radix tree and remove
481 * them from the extent map
483 static int del_pending_extents(struct btrfs_trans_handle
*trans
, struct
484 btrfs_root
*extent_root
)
489 unsigned long gang
[4];
491 struct radix_tree_root
*pending_radix
;
492 struct radix_tree_root
*pinned_radix
;
494 pending_radix
= &extent_root
->fs_info
->pending_del_radix
;
495 pinned_radix
= &extent_root
->fs_info
->pinned_radix
;
498 ret
= find_first_radix_bit(pending_radix
, gang
,
502 for (i
= 0; i
< ret
; i
++) {
503 wret
= set_radix_bit(pinned_radix
, gang
[i
]);
505 wret
= clear_radix_bit(pending_radix
, gang
[i
]);
507 wret
= __free_extent(trans
, extent_root
,
517 * remove an extent from the root, returns 0 on success
519 int btrfs_free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
520 *root
, u64 blocknr
, u64 num_blocks
, int pin
)
522 struct btrfs_root
*extent_root
= root
->fs_info
->extent_root
;
526 if (root
== extent_root
) {
527 pin_down_block(root
, blocknr
, 1);
530 ret
= __free_extent(trans
, root
, blocknr
, num_blocks
, pin
);
531 pending_ret
= del_pending_extents(trans
, root
->fs_info
->extent_root
);
532 return ret
? ret
: pending_ret
;
536 * walks the btree of allocated extents and find a hole of a given size.
537 * The key ins is changed to record the hole:
538 * ins->objectid == block start
539 * ins->flags = BTRFS_EXTENT_ITEM_KEY
540 * ins->offset == number of blocks
541 * Any available blocks before search_start are skipped.
543 static int find_free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
544 *orig_root
, u64 num_blocks
, u64 search_start
, u64
545 search_end
, struct btrfs_key
*ins
)
547 struct btrfs_path
*path
;
548 struct btrfs_key key
;
555 struct btrfs_leaf
*l
;
556 struct btrfs_root
* root
= orig_root
->fs_info
->extent_root
;
557 struct btrfs_fs_info
*info
= root
->fs_info
;
558 int total_needed
= num_blocks
;
560 int fill_prealloc
= 0;
562 int update_block_group
= 0;
563 struct btrfs_block_group_cache
*hint_block_group
;
565 path
= btrfs_alloc_path();
567 btrfs_set_key_type(ins
, BTRFS_EXTENT_ITEM_KEY
);
569 level
= btrfs_header_level(btrfs_buffer_header(root
->node
));
570 /* find search start here */
571 if (0 && search_start
&& num_blocks
) {
573 ret
= radix_tree_gang_lookup(&info
->block_group_radix
,
574 (void **)&hint_block_group
,
577 used
= btrfs_block_group_used(&hint_block_group
->item
);
578 if (used
> (hint_block_group
->key
.offset
* 9) / 10)
580 else if (search_start
< hint_block_group
->last_alloc
)
581 search_start
= hint_block_group
->last_alloc
;
586 if (num_blocks
== 0) {
589 total_needed
= (min(level
+ 1, BTRFS_MAX_LEVEL
) + 2) * 3;
591 if (1 || !search_start
) {
592 trans
->block_group
= btrfs_find_block_group(root
,
595 if (trans
->block_group
->last_alloc
> search_start
)
596 search_start
= trans
->block_group
->last_alloc
;
597 update_block_group
= 1;
600 btrfs_init_path(path
);
601 ins
->objectid
= search_start
;
604 ret
= btrfs_search_slot(trans
, root
, ins
, path
, 0, 0);
608 if (path
->slots
[0] > 0)
612 l
= btrfs_buffer_leaf(path
->nodes
[0]);
613 slot
= path
->slots
[0];
614 if (slot
>= btrfs_header_nritems(&l
->header
)) {
616 info
->extent_tree_prealloc_nr
= 0;
619 ret
= btrfs_next_leaf(root
, path
);
625 ins
->objectid
= search_start
;
626 ins
->offset
= (u64
)-1 - search_start
;
630 ins
->objectid
= last_block
> search_start
?
631 last_block
: search_start
;
632 ins
->offset
= (u64
)-1 - ins
->objectid
;
635 btrfs_disk_key_to_cpu(&key
, &l
->items
[slot
].key
);
636 if (btrfs_key_type(&key
) != BTRFS_EXTENT_ITEM_KEY
)
638 if (key
.objectid
>= search_start
) {
640 if (last_block
< search_start
)
641 last_block
= search_start
;
642 hole_size
= key
.objectid
- last_block
;
643 if (hole_size
>= num_blocks
) {
644 ins
->objectid
= last_block
;
645 ins
->offset
= hole_size
;
651 last_block
= key
.objectid
+ key
.offset
;
657 /* we have to make sure we didn't find an extent that has already
658 * been allocated by the map tree or the original allocation
660 btrfs_release_path(root
, path
);
661 BUG_ON(ins
->objectid
< search_start
);
662 if (ins
->objectid
>= btrfs_super_total_blocks(info
->disk_super
)) {
663 if (search_start
== 0)
668 for (test_block
= ins
->objectid
;
669 test_block
< ins
->objectid
+ num_blocks
; test_block
++) {
670 if (test_radix_bit(&info
->pinned_radix
, test_block
)) {
671 search_start
= test_block
+ 1;
675 if (!fill_prealloc
&& info
->extent_tree_insert_nr
) {
677 info
->extent_tree_insert
[info
->extent_tree_insert_nr
- 1];
678 if (ins
->objectid
+ num_blocks
>
679 info
->extent_tree_insert
[0] &&
680 ins
->objectid
<= last
) {
681 search_start
= last
+ 1;
686 if (!fill_prealloc
&& info
->extent_tree_prealloc_nr
) {
688 info
->extent_tree_prealloc
[info
->extent_tree_prealloc_nr
- 1];
689 if (ins
->objectid
+ num_blocks
> first
&&
690 ins
->objectid
<= info
->extent_tree_prealloc
[0]) {
691 search_start
= info
->extent_tree_prealloc
[0] + 1;
698 test_block
= ins
->objectid
;
699 while(test_block
< ins
->objectid
+ ins
->offset
&&
700 total_found
< total_needed
) {
701 nr
= total_needed
- total_found
- 1;
703 info
->extent_tree_prealloc
[nr
] = test_block
;
707 if (total_found
< total_needed
) {
708 search_start
= test_block
;
711 info
->extent_tree_prealloc_nr
= total_found
;
713 if (update_block_group
) {
714 ret
= radix_tree_gang_lookup(&info
->block_group_radix
,
715 (void **)&trans
->block_group
,
718 trans
->block_group
->last_alloc
= ins
->objectid
;
721 ins
->offset
= num_blocks
;
722 btrfs_free_path(path
);
725 btrfs_release_path(root
, path
);
726 btrfs_free_path(path
);
730 * finds a free extent and does all the dirty work required for allocation
731 * returns the key for the extent through ins, and a tree buffer for
732 * the first block of the extent through buf.
734 * returns 0 if everything worked, non-zero otherwise.
736 int btrfs_alloc_extent(struct btrfs_trans_handle
*trans
,
737 struct btrfs_root
*root
, u64 owner
,
738 u64 num_blocks
, u64 search_start
,
739 u64 search_end
, struct btrfs_key
*ins
)
743 u64 super_blocks_used
;
744 struct btrfs_fs_info
*info
= root
->fs_info
;
745 struct btrfs_root
*extent_root
= info
->extent_root
;
746 struct btrfs_extent_item extent_item
;
747 struct btrfs_key prealloc_key
;
749 btrfs_set_extent_refs(&extent_item
, 1);
750 btrfs_set_extent_owner(&extent_item
, owner
);
752 if (root
== extent_root
) {
754 BUG_ON(info
->extent_tree_prealloc_nr
== 0);
755 BUG_ON(num_blocks
!= 1);
757 info
->extent_tree_prealloc_nr
--;
758 nr
= info
->extent_tree_prealloc_nr
;
759 ins
->objectid
= info
->extent_tree_prealloc
[nr
];
760 info
->extent_tree_insert
[info
->extent_tree_insert_nr
++] =
762 ret
= update_block_group(trans
, root
,
763 ins
->objectid
, ins
->offset
, 1);
767 /* do the real allocation */
768 ret
= find_free_extent(trans
, root
, num_blocks
, search_start
,
773 /* then do prealloc for the extent tree */
774 ret
= find_free_extent(trans
, root
, 0, ins
->objectid
+ ins
->offset
,
775 search_end
, &prealloc_key
);
779 super_blocks_used
= btrfs_super_blocks_used(info
->disk_super
);
780 btrfs_set_super_blocks_used(info
->disk_super
, super_blocks_used
+
782 ret
= btrfs_insert_item(trans
, extent_root
, ins
, &extent_item
,
783 sizeof(extent_item
));
785 finish_current_insert(trans
, extent_root
);
786 pending_ret
= del_pending_extents(trans
, extent_root
);
791 ret
= update_block_group(trans
, root
, ins
->objectid
, ins
->offset
, 1);
796 * helper function to allocate a block for a given tree
797 * returns the tree buffer or NULL.
799 struct buffer_head
*btrfs_alloc_free_block(struct btrfs_trans_handle
*trans
,
800 struct btrfs_root
*root
, u64 hint
)
802 struct btrfs_key ins
;
804 struct buffer_head
*buf
;
806 ret
= btrfs_alloc_extent(trans
, root
, root
->root_key
.objectid
,
807 1, hint
, (unsigned long)-1, &ins
);
813 buf
= btrfs_find_create_tree_block(root
, ins
.objectid
);
814 set_buffer_uptodate(buf
);
815 set_radix_bit(&trans
->transaction
->dirty_pages
, buf
->b_page
->index
);
819 static int drop_leaf_ref(struct btrfs_trans_handle
*trans
,
820 struct btrfs_root
*root
, struct buffer_head
*cur
)
822 struct btrfs_disk_key
*key
;
823 struct btrfs_leaf
*leaf
;
824 struct btrfs_file_extent_item
*fi
;
829 BUG_ON(!btrfs_is_leaf(btrfs_buffer_node(cur
)));
830 leaf
= btrfs_buffer_leaf(cur
);
831 nritems
= btrfs_header_nritems(&leaf
->header
);
832 for (i
= 0; i
< nritems
; i
++) {
833 key
= &leaf
->items
[i
].key
;
834 if (btrfs_disk_key_type(key
) != BTRFS_EXTENT_DATA_KEY
)
836 fi
= btrfs_item_ptr(leaf
, i
, struct btrfs_file_extent_item
);
837 if (btrfs_file_extent_type(fi
) == BTRFS_FILE_EXTENT_INLINE
)
840 * FIXME make sure to insert a trans record that
841 * repeats the snapshot del on crash
843 ret
= btrfs_free_extent(trans
, root
,
844 btrfs_file_extent_disk_blocknr(fi
),
845 btrfs_file_extent_disk_num_blocks(fi
),
853 * helper function for drop_snapshot, this walks down the tree dropping ref
856 static int walk_down_tree(struct btrfs_trans_handle
*trans
, struct btrfs_root
857 *root
, struct btrfs_path
*path
, int *level
)
859 struct buffer_head
*next
;
860 struct buffer_head
*cur
;
866 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
867 ret
= lookup_extent_ref(trans
, root
, bh_blocknr(path
->nodes
[*level
]),
873 * walk down to the last node level and free all the leaves
877 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
878 cur
= path
->nodes
[*level
];
879 if (btrfs_header_level(btrfs_buffer_header(cur
)) != *level
)
881 if (path
->slots
[*level
] >=
882 btrfs_header_nritems(btrfs_buffer_header(cur
)))
885 ret
= drop_leaf_ref(trans
, root
, cur
);
889 blocknr
= btrfs_node_blockptr(btrfs_buffer_node(cur
),
890 path
->slots
[*level
]);
891 ret
= lookup_extent_ref(trans
, root
, blocknr
, 1, &refs
);
894 path
->slots
[*level
]++;
895 ret
= btrfs_free_extent(trans
, root
, blocknr
, 1, 1);
899 next
= read_tree_block(root
, blocknr
);
900 WARN_ON(*level
<= 0);
901 if (path
->nodes
[*level
-1])
902 btrfs_block_release(root
, path
->nodes
[*level
-1]);
903 path
->nodes
[*level
-1] = next
;
904 *level
= btrfs_header_level(btrfs_buffer_header(next
));
905 path
->slots
[*level
] = 0;
909 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
910 ret
= btrfs_free_extent(trans
, root
,
911 bh_blocknr(path
->nodes
[*level
]), 1, 1);
912 btrfs_block_release(root
, path
->nodes
[*level
]);
913 path
->nodes
[*level
] = NULL
;
920 * helper for dropping snapshots. This walks back up the tree in the path
921 * to find the first node higher up where we haven't yet gone through
924 static int walk_up_tree(struct btrfs_trans_handle
*trans
, struct btrfs_root
925 *root
, struct btrfs_path
*path
, int *level
)
930 for(i
= *level
; i
< BTRFS_MAX_LEVEL
- 1 && path
->nodes
[i
]; i
++) {
931 slot
= path
->slots
[i
];
932 if (slot
< btrfs_header_nritems(
933 btrfs_buffer_header(path
->nodes
[i
])) - 1) {
938 ret
= btrfs_free_extent(trans
, root
,
939 bh_blocknr(path
->nodes
[*level
]),
942 btrfs_block_release(root
, path
->nodes
[*level
]);
943 path
->nodes
[*level
] = NULL
;
951 * drop the reference count on the tree rooted at 'snap'. This traverses
952 * the tree freeing any blocks that have a ref count of zero after being
955 int btrfs_drop_snapshot(struct btrfs_trans_handle
*trans
, struct btrfs_root
956 *root
, struct buffer_head
*snap
)
961 struct btrfs_path
*path
;
965 path
= btrfs_alloc_path();
967 btrfs_init_path(path
);
969 level
= btrfs_header_level(btrfs_buffer_header(snap
));
971 path
->nodes
[level
] = snap
;
972 path
->slots
[level
] = 0;
974 wret
= walk_down_tree(trans
, root
, path
, &level
);
980 wret
= walk_up_tree(trans
, root
, path
, &level
);
986 for (i
= 0; i
<= orig_level
; i
++) {
987 if (path
->nodes
[i
]) {
988 btrfs_block_release(root
, path
->nodes
[i
]);
991 btrfs_free_path(path
);
995 int btrfs_free_block_groups(struct btrfs_fs_info
*info
)
998 struct btrfs_block_group_cache
*cache
[8];
1002 ret
= radix_tree_gang_lookup(&info
->block_group_radix
,
1007 for (i
= 0; i
< ret
; i
++) {
1008 radix_tree_delete(&info
->block_group_radix
,
1009 cache
[i
]->key
.objectid
+
1010 cache
[i
]->key
.offset
- 1);
1017 int btrfs_read_block_groups(struct btrfs_root
*root
)
1019 struct btrfs_path
*path
;
1022 struct btrfs_block_group_item
*bi
;
1023 struct btrfs_block_group_cache
*cache
;
1024 struct btrfs_key key
;
1025 struct btrfs_key found_key
;
1026 struct btrfs_leaf
*leaf
;
1027 u64 group_size_blocks
= BTRFS_BLOCK_GROUP_SIZE
/ root
->blocksize
;
1030 root
= root
->fs_info
->extent_root
;
1032 key
.offset
= group_size_blocks
;
1034 btrfs_set_key_type(&key
, BTRFS_BLOCK_GROUP_ITEM_KEY
);
1036 path
= btrfs_alloc_path();
1041 ret
= btrfs_search_slot(NULL
, root
->fs_info
->extent_root
,
1047 leaf
= btrfs_buffer_leaf(path
->nodes
[0]);
1048 btrfs_disk_key_to_cpu(&found_key
,
1049 &leaf
->items
[path
->slots
[0]].key
);
1050 cache
= kmalloc(sizeof(*cache
), GFP_NOFS
);
1055 bi
= btrfs_item_ptr(leaf
, path
->slots
[0],
1056 struct btrfs_block_group_item
);
1057 memcpy(&cache
->item
, bi
, sizeof(*bi
));
1058 memcpy(&cache
->key
, &found_key
, sizeof(found_key
));
1059 cache
->last_alloc
= cache
->key
.objectid
;
1060 cache
->first_free
= cache
->key
.objectid
;
1061 key
.objectid
= found_key
.objectid
+ found_key
.offset
;
1062 btrfs_release_path(root
, path
);
1063 ret
= radix_tree_insert(&root
->fs_info
->block_group_radix
,
1064 found_key
.objectid
+
1065 found_key
.offset
- 1,
1068 used
= btrfs_block_group_used(bi
);
1069 if (used
< (key
.offset
* 2) / 3) {
1070 radix_tree_tag_set(&root
->fs_info
->block_group_radix
,
1071 found_key
.objectid
+
1072 found_key
.offset
- 1,
1073 BTRFS_BLOCK_GROUP_AVAIL
);
1076 btrfs_super_total_blocks(root
->fs_info
->disk_super
))
1080 btrfs_free_path(path
);