2 * Copyright (C) 2007 Oracle. All rights reserved.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
19 #include <linux/sched.h>
22 #include "print-tree.h"
23 #include "transaction.h"
25 #define BLOCK_GROUP_DATA EXTENT_WRITEBACK
26 #define BLOCK_GROUP_METADATA EXTENT_UPTODATE
27 #define BLOCK_GROUP_DIRTY EXTENT_DIRTY
29 static int finish_current_insert(struct btrfs_trans_handle
*trans
, struct
30 btrfs_root
*extent_root
);
31 static int del_pending_extents(struct btrfs_trans_handle
*trans
, struct
32 btrfs_root
*extent_root
);
34 static int cache_block_group(struct btrfs_root
*root
,
35 struct btrfs_block_group_cache
*block_group
)
37 struct btrfs_path
*path
;
40 struct extent_buffer
*leaf
;
41 struct extent_map_tree
*free_space_cache
;
48 root
= root
->fs_info
->extent_root
;
49 free_space_cache
= &root
->fs_info
->free_space_cache
;
51 if (block_group
->cached
)
54 path
= btrfs_alloc_path();
59 first_free
= block_group
->key
.objectid
;
60 key
.objectid
= block_group
->key
.objectid
;
63 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
64 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
69 if (ret
&& path
->slots
[0] > 0)
73 leaf
= path
->nodes
[0];
74 slot
= path
->slots
[0];
75 if (slot
>= btrfs_header_nritems(leaf
)) {
76 ret
= btrfs_next_leaf(root
, path
);
86 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
87 if (key
.objectid
< block_group
->key
.objectid
) {
88 if (key
.objectid
+ key
.offset
> first_free
)
89 first_free
= key
.objectid
+ key
.offset
;
93 if (key
.objectid
>= block_group
->key
.objectid
+
94 block_group
->key
.offset
) {
98 if (btrfs_key_type(&key
) == BTRFS_EXTENT_ITEM_KEY
) {
103 if (key
.objectid
> last
) {
104 hole_size
= key
.objectid
- last
;
105 set_extent_dirty(free_space_cache
, last
,
106 last
+ hole_size
- 1,
109 last
= key
.objectid
+ key
.offset
;
117 if (block_group
->key
.objectid
+
118 block_group
->key
.offset
> last
) {
119 hole_size
= block_group
->key
.objectid
+
120 block_group
->key
.offset
- last
;
121 set_extent_dirty(free_space_cache
, last
,
122 last
+ hole_size
- 1, GFP_NOFS
);
124 block_group
->cached
= 1;
126 btrfs_free_path(path
);
130 struct btrfs_block_group_cache
*btrfs_lookup_block_group(struct
134 struct extent_map_tree
*block_group_cache
;
135 struct btrfs_block_group_cache
*block_group
= NULL
;
141 block_group_cache
= &info
->block_group_cache
;
142 ret
= find_first_extent_bit(block_group_cache
,
143 bytenr
, &start
, &end
,
144 BLOCK_GROUP_DATA
| BLOCK_GROUP_METADATA
);
148 ret
= get_state_private(block_group_cache
, start
, &ptr
);
152 block_group
= (struct btrfs_block_group_cache
*)ptr
;
155 if (block_group
->key
.objectid
<= bytenr
&& bytenr
<=
156 block_group
->key
.objectid
+ block_group
->key
.offset
)
162 static u64
find_search_start(struct btrfs_root
*root
,
163 struct btrfs_block_group_cache
**cache_ret
,
164 u64 search_start
, int num
, int data
)
167 struct btrfs_block_group_cache
*cache
= *cache_ret
;
173 ret
= cache_block_group(root
, cache
);
176 last
= max(search_start
, cache
->key
.objectid
);
179 ret
= find_first_extent_bit(&root
->fs_info
->free_space_cache
,
180 last
, &start
, &end
, EXTENT_DIRTY
);
185 start
= max(last
, start
);
187 if (end
+ 1 - start
< num
)
189 if (start
+ num
>= cache
->key
.objectid
+ cache
->key
.offset
)
197 last
= cache
->key
.objectid
+ cache
->key
.offset
;
198 cache
= btrfs_lookup_block_group(root
->fs_info
, last
);
202 cache
= btrfs_find_block_group(root
, cache
, last
, data
, 0);
207 static u64
div_factor(u64 num
, int factor
)
214 struct btrfs_block_group_cache
*btrfs_find_block_group(struct btrfs_root
*root
,
215 struct btrfs_block_group_cache
216 *hint
, u64 search_start
,
219 struct btrfs_block_group_cache
*cache
;
220 struct extent_map_tree
*block_group_cache
;
221 struct btrfs_block_group_cache
*found_group
= NULL
;
222 struct btrfs_fs_info
*info
= root
->fs_info
;
236 block_group_cache
= &info
->block_group_cache
;
242 bit
= BLOCK_GROUP_DATA
;
244 bit
= BLOCK_GROUP_METADATA
;
247 struct btrfs_block_group_cache
*shint
;
248 shint
= btrfs_lookup_block_group(info
, search_start
);
249 if (shint
&& shint
->data
== data
) {
250 used
= btrfs_block_group_used(&shint
->item
);
251 if (used
< div_factor(shint
->key
.offset
, factor
)) {
256 if (hint
&& hint
->data
== data
) {
257 used
= btrfs_block_group_used(&hint
->item
);
258 if (used
< div_factor(hint
->key
.offset
, factor
)) {
261 last
= hint
->key
.objectid
+ hint
->key
.offset
;
265 hint_last
= max(hint
->key
.objectid
, search_start
);
267 hint_last
= search_start
;
273 ret
= find_first_extent_bit(block_group_cache
, last
,
278 ret
= get_state_private(block_group_cache
, start
, &ptr
);
282 cache
= (struct btrfs_block_group_cache
*)ptr
;
283 last
= cache
->key
.objectid
+ cache
->key
.offset
;
284 used
= btrfs_block_group_used(&cache
->item
);
287 free_check
= cache
->key
.offset
;
289 free_check
= div_factor(cache
->key
.offset
, factor
);
291 if (used
< free_check
) {
304 bit
= BLOCK_GROUP_DATA
| BLOCK_GROUP_METADATA
;
312 int btrfs_inc_extent_ref(struct btrfs_trans_handle
*trans
,
313 struct btrfs_root
*root
,
314 u64 bytenr
, u64 num_bytes
)
316 struct btrfs_path
*path
;
318 struct btrfs_key key
;
319 struct extent_buffer
*l
;
320 struct btrfs_extent_item
*item
;
323 WARN_ON(num_bytes
< root
->sectorsize
);
324 path
= btrfs_alloc_path();
328 key
.objectid
= bytenr
;
329 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
330 key
.offset
= num_bytes
;
331 ret
= btrfs_search_slot(trans
, root
->fs_info
->extent_root
, &key
, path
,
340 item
= btrfs_item_ptr(l
, path
->slots
[0], struct btrfs_extent_item
);
341 refs
= btrfs_extent_refs(l
, item
);
342 btrfs_set_extent_refs(l
, item
, refs
+ 1);
343 btrfs_mark_buffer_dirty(path
->nodes
[0]);
345 btrfs_release_path(root
->fs_info
->extent_root
, path
);
346 btrfs_free_path(path
);
347 finish_current_insert(trans
, root
->fs_info
->extent_root
);
348 del_pending_extents(trans
, root
->fs_info
->extent_root
);
352 int btrfs_extent_post_op(struct btrfs_trans_handle
*trans
,
353 struct btrfs_root
*root
)
355 finish_current_insert(trans
, root
->fs_info
->extent_root
);
356 del_pending_extents(trans
, root
->fs_info
->extent_root
);
360 static int lookup_extent_ref(struct btrfs_trans_handle
*trans
,
361 struct btrfs_root
*root
, u64 bytenr
,
362 u64 num_bytes
, u32
*refs
)
364 struct btrfs_path
*path
;
366 struct btrfs_key key
;
367 struct extent_buffer
*l
;
368 struct btrfs_extent_item
*item
;
370 WARN_ON(num_bytes
< root
->sectorsize
);
371 path
= btrfs_alloc_path();
372 key
.objectid
= bytenr
;
373 key
.offset
= num_bytes
;
374 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
375 ret
= btrfs_search_slot(trans
, root
->fs_info
->extent_root
, &key
, path
,
380 btrfs_print_leaf(root
, path
->nodes
[0]);
381 printk("failed to find block number %Lu\n", bytenr
);
385 item
= btrfs_item_ptr(l
, path
->slots
[0], struct btrfs_extent_item
);
386 *refs
= btrfs_extent_refs(l
, item
);
388 btrfs_free_path(path
);
392 int btrfs_inc_root_ref(struct btrfs_trans_handle
*trans
,
393 struct btrfs_root
*root
)
395 return btrfs_inc_extent_ref(trans
, root
, root
->node
->start
,
399 int btrfs_inc_ref(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
400 struct extent_buffer
*buf
)
404 struct btrfs_key key
;
405 struct btrfs_file_extent_item
*fi
;
415 level
= btrfs_header_level(buf
);
416 nritems
= btrfs_header_nritems(buf
);
417 for (i
= 0; i
< nritems
; i
++) {
420 btrfs_item_key_to_cpu(buf
, &key
, i
);
421 if (btrfs_key_type(&key
) != BTRFS_EXTENT_DATA_KEY
)
423 fi
= btrfs_item_ptr(buf
, i
,
424 struct btrfs_file_extent_item
);
425 if (btrfs_file_extent_type(buf
, fi
) ==
426 BTRFS_FILE_EXTENT_INLINE
)
428 disk_bytenr
= btrfs_file_extent_disk_bytenr(buf
, fi
);
429 if (disk_bytenr
== 0)
431 ret
= btrfs_inc_extent_ref(trans
, root
, disk_bytenr
,
432 btrfs_file_extent_disk_num_bytes(buf
, fi
));
438 bytenr
= btrfs_node_blockptr(buf
, i
);
439 ret
= btrfs_inc_extent_ref(trans
, root
, bytenr
,
440 btrfs_level_size(root
, level
- 1));
450 for (i
=0; i
< faili
; i
++) {
453 btrfs_item_key_to_cpu(buf
, &key
, i
);
454 if (btrfs_key_type(&key
) != BTRFS_EXTENT_DATA_KEY
)
456 fi
= btrfs_item_ptr(buf
, i
,
457 struct btrfs_file_extent_item
);
458 if (btrfs_file_extent_type(buf
, fi
) ==
459 BTRFS_FILE_EXTENT_INLINE
)
461 disk_bytenr
= btrfs_file_extent_disk_bytenr(buf
, fi
);
462 if (disk_bytenr
== 0)
464 err
= btrfs_free_extent(trans
, root
, disk_bytenr
,
465 btrfs_file_extent_disk_num_bytes(buf
,
469 bytenr
= btrfs_node_blockptr(buf
, i
);
470 err
= btrfs_free_extent(trans
, root
, bytenr
,
471 btrfs_level_size(root
, level
- 1), 0);
478 static int write_one_cache_group(struct btrfs_trans_handle
*trans
,
479 struct btrfs_root
*root
,
480 struct btrfs_path
*path
,
481 struct btrfs_block_group_cache
*cache
)
485 struct btrfs_root
*extent_root
= root
->fs_info
->extent_root
;
487 struct extent_buffer
*leaf
;
489 ret
= btrfs_search_slot(trans
, extent_root
, &cache
->key
, path
, 0, 1);
494 leaf
= path
->nodes
[0];
495 bi
= btrfs_item_ptr_offset(leaf
, path
->slots
[0]);
496 write_extent_buffer(leaf
, &cache
->item
, bi
, sizeof(cache
->item
));
497 btrfs_mark_buffer_dirty(leaf
);
498 btrfs_release_path(extent_root
, path
);
500 finish_current_insert(trans
, extent_root
);
501 pending_ret
= del_pending_extents(trans
, extent_root
);
510 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle
*trans
,
511 struct btrfs_root
*root
)
513 struct extent_map_tree
*block_group_cache
;
514 struct btrfs_block_group_cache
*cache
;
518 struct btrfs_path
*path
;
524 block_group_cache
= &root
->fs_info
->block_group_cache
;
525 path
= btrfs_alloc_path();
530 ret
= find_first_extent_bit(block_group_cache
, last
,
531 &start
, &end
, BLOCK_GROUP_DIRTY
);
536 ret
= get_state_private(block_group_cache
, start
, &ptr
);
540 cache
= (struct btrfs_block_group_cache
*)ptr
;
541 err
= write_one_cache_group(trans
, root
,
544 * if we fail to write the cache group, we want
545 * to keep it marked dirty in hopes that a later
552 clear_extent_bits(block_group_cache
, start
, end
,
553 BLOCK_GROUP_DIRTY
, GFP_NOFS
);
555 btrfs_free_path(path
);
559 static int update_block_group(struct btrfs_trans_handle
*trans
,
560 struct btrfs_root
*root
,
561 u64 bytenr
, u64 num_bytes
, int alloc
,
562 int mark_free
, int data
)
564 struct btrfs_block_group_cache
*cache
;
565 struct btrfs_fs_info
*info
= root
->fs_info
;
566 u64 total
= num_bytes
;
573 cache
= btrfs_lookup_block_group(info
, bytenr
);
577 byte_in_group
= bytenr
- cache
->key
.objectid
;
578 WARN_ON(byte_in_group
> cache
->key
.offset
);
579 start
= cache
->key
.objectid
;
580 end
= start
+ cache
->key
.offset
- 1;
581 set_extent_bits(&info
->block_group_cache
, start
, end
,
582 BLOCK_GROUP_DIRTY
, GFP_NOFS
);
584 old_val
= btrfs_block_group_used(&cache
->item
);
585 num_bytes
= min(total
, cache
->key
.offset
- byte_in_group
);
587 if (cache
->data
!= data
&&
588 old_val
< (cache
->key
.offset
>> 1)) {
594 bit_to_clear
= BLOCK_GROUP_DATA
;
595 bit_to_set
= BLOCK_GROUP_METADATA
;
597 BTRFS_BLOCK_GROUP_DATA
;
599 bit_to_clear
= BLOCK_GROUP_METADATA
;
600 bit_to_set
= BLOCK_GROUP_DATA
;
602 ~BTRFS_BLOCK_GROUP_DATA
;
604 clear_extent_bits(&info
->block_group_cache
,
605 start
, end
, bit_to_clear
,
607 set_extent_bits(&info
->block_group_cache
,
608 start
, end
, bit_to_set
,
611 old_val
+= num_bytes
;
613 old_val
-= num_bytes
;
615 set_extent_dirty(&info
->free_space_cache
,
616 bytenr
, bytenr
+ num_bytes
- 1,
620 btrfs_set_block_group_used(&cache
->item
, old_val
);
627 int btrfs_copy_pinned(struct btrfs_root
*root
, struct extent_map_tree
*copy
)
632 struct extent_map_tree
*pinned_extents
= &root
->fs_info
->pinned_extents
;
636 ret
= find_first_extent_bit(pinned_extents
, last
,
637 &start
, &end
, EXTENT_DIRTY
);
640 set_extent_dirty(copy
, start
, end
, GFP_NOFS
);
646 int btrfs_finish_extent_commit(struct btrfs_trans_handle
*trans
,
647 struct btrfs_root
*root
,
648 struct extent_map_tree
*unpin
)
653 struct extent_map_tree
*pinned_extents
= &root
->fs_info
->pinned_extents
;
654 struct extent_map_tree
*free_space_cache
;
656 free_space_cache
= &root
->fs_info
->free_space_cache
;
659 ret
= find_first_extent_bit(unpin
, 0, &start
, &end
,
664 clear_extent_dirty(pinned_extents
, start
, end
,
666 clear_extent_dirty(unpin
, start
, end
, GFP_NOFS
);
667 set_extent_dirty(free_space_cache
, start
, end
, GFP_NOFS
);
672 static int finish_current_insert(struct btrfs_trans_handle
*trans
, struct
673 btrfs_root
*extent_root
)
675 struct btrfs_key ins
;
676 struct btrfs_extent_item extent_item
;
681 struct btrfs_fs_info
*info
= extent_root
->fs_info
;
683 btrfs_set_stack_extent_refs(&extent_item
, 1);
684 btrfs_set_key_type(&ins
, BTRFS_EXTENT_ITEM_KEY
);
685 btrfs_set_stack_extent_owner(&extent_item
,
686 extent_root
->root_key
.objectid
);
689 ret
= find_first_extent_bit(&info
->extent_ins
, 0, &start
,
690 &end
, EXTENT_LOCKED
);
694 ins
.objectid
= start
;
695 ins
.offset
= end
+ 1 - start
;
696 err
= btrfs_insert_item(trans
, extent_root
, &ins
,
697 &extent_item
, sizeof(extent_item
));
698 clear_extent_bits(&info
->extent_ins
, start
, end
, EXTENT_LOCKED
,
704 static int pin_down_bytes(struct btrfs_root
*root
, u64 bytenr
, u32 num_bytes
,
708 struct extent_buffer
*buf
;
711 buf
= btrfs_find_tree_block(root
, bytenr
, num_bytes
);
713 if (btrfs_buffer_uptodate(buf
)) {
715 root
->fs_info
->running_transaction
->transid
;
716 if (btrfs_header_generation(buf
) == transid
) {
717 free_extent_buffer(buf
);
721 free_extent_buffer(buf
);
723 set_extent_dirty(&root
->fs_info
->pinned_extents
,
724 bytenr
, bytenr
+ num_bytes
- 1, GFP_NOFS
);
726 set_extent_bits(&root
->fs_info
->pending_del
,
727 bytenr
, bytenr
+ num_bytes
- 1,
728 EXTENT_LOCKED
, GFP_NOFS
);
735 * remove an extent from the root, returns 0 on success
737 static int __free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
738 *root
, u64 bytenr
, u64 num_bytes
, int pin
,
741 struct btrfs_path
*path
;
742 struct btrfs_key key
;
743 struct btrfs_fs_info
*info
= root
->fs_info
;
744 struct btrfs_root
*extent_root
= info
->extent_root
;
745 struct extent_buffer
*leaf
;
747 struct btrfs_extent_item
*ei
;
750 key
.objectid
= bytenr
;
751 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
752 key
.offset
= num_bytes
;
754 path
= btrfs_alloc_path();
758 ret
= btrfs_search_slot(trans
, extent_root
, &key
, path
, -1, 1);
763 leaf
= path
->nodes
[0];
764 ei
= btrfs_item_ptr(leaf
, path
->slots
[0],
765 struct btrfs_extent_item
);
766 refs
= btrfs_extent_refs(leaf
, ei
);
769 btrfs_set_extent_refs(leaf
, ei
, refs
);
770 btrfs_mark_buffer_dirty(leaf
);
777 ret
= pin_down_bytes(root
, bytenr
, num_bytes
, 0);
781 /* block accounting for super block */
782 super_used
= btrfs_super_bytes_used(&info
->super_copy
);
783 btrfs_set_super_bytes_used(&info
->super_copy
,
784 super_used
- num_bytes
);
786 /* block accounting for root item */
787 root_used
= btrfs_root_used(&root
->root_item
);
788 btrfs_set_root_used(&root
->root_item
,
789 root_used
- num_bytes
);
791 ret
= btrfs_del_item(trans
, extent_root
, path
);
795 ret
= update_block_group(trans
, root
, bytenr
, num_bytes
, 0,
799 btrfs_free_path(path
);
800 finish_current_insert(trans
, extent_root
);
805 * find all the blocks marked as pending in the radix tree and remove
806 * them from the extent map
808 static int del_pending_extents(struct btrfs_trans_handle
*trans
, struct
809 btrfs_root
*extent_root
)
815 struct extent_map_tree
*pending_del
;
816 struct extent_map_tree
*pinned_extents
;
818 pending_del
= &extent_root
->fs_info
->pending_del
;
819 pinned_extents
= &extent_root
->fs_info
->pinned_extents
;
822 ret
= find_first_extent_bit(pending_del
, 0, &start
, &end
,
827 set_extent_dirty(pinned_extents
, start
, end
, GFP_NOFS
);
828 clear_extent_bits(pending_del
, start
, end
, EXTENT_LOCKED
,
830 ret
= __free_extent(trans
, extent_root
,
831 start
, end
+ 1 - start
, 0, 0);
839 * remove an extent from the root, returns 0 on success
841 int btrfs_free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
842 *root
, u64 bytenr
, u64 num_bytes
, int pin
)
844 struct btrfs_root
*extent_root
= root
->fs_info
->extent_root
;
848 WARN_ON(num_bytes
< root
->sectorsize
);
849 if (root
== extent_root
) {
850 pin_down_bytes(root
, bytenr
, num_bytes
, 1);
853 ret
= __free_extent(trans
, root
, bytenr
, num_bytes
, pin
, pin
== 0);
854 pending_ret
= del_pending_extents(trans
, root
->fs_info
->extent_root
);
855 return ret
? ret
: pending_ret
;
859 * walks the btree of allocated extents and find a hole of a given size.
860 * The key ins is changed to record the hole:
861 * ins->objectid == block start
862 * ins->flags = BTRFS_EXTENT_ITEM_KEY
863 * ins->offset == number of blocks
864 * Any available blocks before search_start are skipped.
866 static int find_free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
867 *orig_root
, u64 num_bytes
, u64 empty_size
,
868 u64 search_start
, u64 search_end
, u64 hint_byte
,
869 struct btrfs_key
*ins
, u64 exclude_start
,
870 u64 exclude_nr
, int data
)
872 struct btrfs_path
*path
;
873 struct btrfs_key key
;
878 u64 orig_search_start
= search_start
;
880 struct extent_buffer
*l
;
881 struct btrfs_root
* root
= orig_root
->fs_info
->extent_root
;
882 struct btrfs_fs_info
*info
= root
->fs_info
;
883 u64 total_needed
= num_bytes
;
885 struct btrfs_block_group_cache
*block_group
;
889 WARN_ON(num_bytes
< root
->sectorsize
);
890 btrfs_set_key_type(ins
, BTRFS_EXTENT_ITEM_KEY
);
892 level
= btrfs_header_level(root
->node
);
894 if (search_end
== (u64
)-1)
895 search_end
= btrfs_super_total_bytes(&info
->super_copy
);
897 block_group
= btrfs_lookup_block_group(info
, hint_byte
);
898 block_group
= btrfs_find_block_group(root
, block_group
,
901 block_group
= btrfs_find_block_group(root
,
902 trans
->block_group
, 0,
906 total_needed
+= empty_size
;
907 path
= btrfs_alloc_path();
910 search_start
= find_search_start(root
, &block_group
,
911 search_start
, total_needed
, data
);
912 btrfs_init_path(path
);
913 ins
->objectid
= search_start
;
918 ret
= btrfs_search_slot(trans
, root
, ins
, path
, 0, 0);
922 if (path
->slots
[0] > 0) {
927 btrfs_item_key_to_cpu(l
, &key
, path
->slots
[0]);
930 * a rare case, go back one key if we hit a block group item
931 * instead of an extent item
933 if (btrfs_key_type(&key
) != BTRFS_EXTENT_ITEM_KEY
&&
934 key
.objectid
+ key
.offset
>= search_start
) {
935 ins
->objectid
= key
.objectid
;
936 ins
->offset
= key
.offset
- 1;
937 btrfs_release_path(root
, path
);
938 ret
= btrfs_search_slot(trans
, root
, ins
, path
, 0, 0);
942 if (path
->slots
[0] > 0) {
949 slot
= path
->slots
[0];
950 if (slot
>= btrfs_header_nritems(l
)) {
951 ret
= btrfs_next_leaf(root
, path
);
957 search_start
= max(search_start
,
958 block_group
->key
.objectid
);
960 ins
->objectid
= search_start
;
961 ins
->offset
= search_end
- search_start
;
965 ins
->objectid
= last_byte
> search_start
?
966 last_byte
: search_start
;
967 ins
->offset
= search_end
- ins
->objectid
;
968 BUG_ON(ins
->objectid
>= search_end
);
971 btrfs_item_key_to_cpu(l
, &key
, slot
);
973 if (key
.objectid
>= search_start
&& key
.objectid
> last_byte
&&
975 if (last_byte
< search_start
)
976 last_byte
= search_start
;
977 hole_size
= key
.objectid
- last_byte
;
978 if (hole_size
>= num_bytes
) {
979 ins
->objectid
= last_byte
;
980 ins
->offset
= hole_size
;
984 if (btrfs_key_type(&key
) != BTRFS_EXTENT_ITEM_KEY
) {
986 last_byte
= key
.objectid
;
994 last_byte
= key
.objectid
+ key
.offset
;
996 if (!full_scan
&& last_byte
>= block_group
->key
.objectid
+
997 block_group
->key
.offset
) {
998 btrfs_release_path(root
, path
);
999 search_start
= block_group
->key
.objectid
+
1000 block_group
->key
.offset
;
1008 /* we have to make sure we didn't find an extent that has already
1009 * been allocated by the map tree or the original allocation
1011 btrfs_release_path(root
, path
);
1012 BUG_ON(ins
->objectid
< search_start
);
1014 if (ins
->objectid
+ num_bytes
>= search_end
)
1017 if (!full_scan
&& ins
->objectid
+ num_bytes
>= block_group
->
1018 key
.objectid
+ block_group
->key
.offset
) {
1019 search_start
= block_group
->key
.objectid
+
1020 block_group
->key
.offset
;
1023 if (test_range_bit(&info
->extent_ins
, ins
->objectid
,
1024 ins
->objectid
+ num_bytes
-1, EXTENT_LOCKED
, 0)) {
1025 search_start
= ins
->objectid
+ num_bytes
;
1028 if (test_range_bit(&info
->pinned_extents
, ins
->objectid
,
1029 ins
->objectid
+ num_bytes
-1, EXTENT_DIRTY
, 0)) {
1030 search_start
= ins
->objectid
+ num_bytes
;
1033 if (exclude_nr
> 0 && (ins
->objectid
+ num_bytes
> exclude_start
&&
1034 ins
->objectid
< exclude_start
+ exclude_nr
)) {
1035 search_start
= exclude_start
+ exclude_nr
;
1039 block_group
= btrfs_lookup_block_group(info
, ins
->objectid
);
1041 trans
->block_group
= block_group
;
1043 ins
->offset
= num_bytes
;
1044 btrfs_free_path(path
);
1048 if (search_start
+ num_bytes
>= search_end
) {
1050 search_start
= orig_search_start
;
1057 total_needed
-= empty_size
;
1062 block_group
= btrfs_lookup_block_group(info
, search_start
);
1065 block_group
= btrfs_find_block_group(root
, block_group
,
1066 search_start
, data
, 0);
1070 btrfs_release_path(root
, path
);
1071 btrfs_free_path(path
);
1075 * finds a free extent and does all the dirty work required for allocation
1076 * returns the key for the extent through ins, and a tree buffer for
1077 * the first block of the extent through buf.
1079 * returns 0 if everything worked, non-zero otherwise.
1081 int btrfs_alloc_extent(struct btrfs_trans_handle
*trans
,
1082 struct btrfs_root
*root
, u64 owner
,
1083 u64 num_bytes
, u64 empty_size
, u64 hint_byte
,
1084 u64 search_end
, struct btrfs_key
*ins
, int data
)
1088 u64 super_used
, root_used
;
1089 u64 search_start
= 0;
1090 struct btrfs_fs_info
*info
= root
->fs_info
;
1091 struct btrfs_root
*extent_root
= info
->extent_root
;
1092 struct btrfs_extent_item extent_item
;
1094 btrfs_set_stack_extent_refs(&extent_item
, 1);
1095 btrfs_set_stack_extent_owner(&extent_item
, owner
);
1097 WARN_ON(num_bytes
< root
->sectorsize
);
1098 ret
= find_free_extent(trans
, root
, num_bytes
, empty_size
,
1099 search_start
, search_end
, hint_byte
, ins
,
1100 trans
->alloc_exclude_start
,
1101 trans
->alloc_exclude_nr
, data
);
1106 /* block accounting for super block */
1107 super_used
= btrfs_super_bytes_used(&info
->super_copy
);
1108 btrfs_set_super_bytes_used(&info
->super_copy
, super_used
+ num_bytes
);
1110 /* block accounting for root item */
1111 root_used
= btrfs_root_used(&root
->root_item
);
1112 btrfs_set_root_used(&root
->root_item
, root_used
+ num_bytes
);
1114 clear_extent_dirty(&root
->fs_info
->free_space_cache
,
1115 ins
->objectid
, ins
->objectid
+ ins
->offset
- 1,
1118 if (root
== extent_root
) {
1119 set_extent_bits(&root
->fs_info
->extent_ins
, ins
->objectid
,
1120 ins
->objectid
+ ins
->offset
- 1,
1121 EXTENT_LOCKED
, GFP_NOFS
);
1126 WARN_ON(trans
->alloc_exclude_nr
);
1127 trans
->alloc_exclude_start
= ins
->objectid
;
1128 trans
->alloc_exclude_nr
= ins
->offset
;
1129 ret
= btrfs_insert_item(trans
, extent_root
, ins
, &extent_item
,
1130 sizeof(extent_item
));
1132 trans
->alloc_exclude_start
= 0;
1133 trans
->alloc_exclude_nr
= 0;
1136 finish_current_insert(trans
, extent_root
);
1137 pending_ret
= del_pending_extents(trans
, extent_root
);
1147 ret
= update_block_group(trans
, root
, ins
->objectid
, ins
->offset
, 1, 0,
1154 * helper function to allocate a block for a given tree
1155 * returns the tree buffer or NULL.
1157 struct extent_buffer
*btrfs_alloc_free_block(struct btrfs_trans_handle
*trans
,
1158 struct btrfs_root
*root
,
1159 u32 blocksize
, u64 hint
,
1162 struct btrfs_key ins
;
1164 struct extent_buffer
*buf
;
1166 ret
= btrfs_alloc_extent(trans
, root
, root
->root_key
.objectid
,
1167 blocksize
, empty_size
, hint
,
1171 return ERR_PTR(ret
);
1173 buf
= btrfs_find_create_tree_block(root
, ins
.objectid
, blocksize
);
1175 btrfs_free_extent(trans
, root
, ins
.objectid
, blocksize
, 0);
1176 return ERR_PTR(-ENOMEM
);
1178 btrfs_set_buffer_uptodate(buf
);
1179 set_extent_dirty(&trans
->transaction
->dirty_pages
, buf
->start
,
1180 buf
->start
+ buf
->len
- 1, GFP_NOFS
);
1181 btrfs_set_buffer_defrag(buf
);
1182 trans
->blocks_used
++;
1186 static int drop_leaf_ref(struct btrfs_trans_handle
*trans
,
1187 struct btrfs_root
*root
, struct extent_buffer
*leaf
)
1189 struct btrfs_key key
;
1190 struct btrfs_file_extent_item
*fi
;
1195 BUG_ON(!btrfs_is_leaf(leaf
));
1196 nritems
= btrfs_header_nritems(leaf
);
1197 for (i
= 0; i
< nritems
; i
++) {
1200 btrfs_item_key_to_cpu(leaf
, &key
, i
);
1201 if (btrfs_key_type(&key
) != BTRFS_EXTENT_DATA_KEY
)
1203 fi
= btrfs_item_ptr(leaf
, i
, struct btrfs_file_extent_item
);
1204 if (btrfs_file_extent_type(leaf
, fi
) ==
1205 BTRFS_FILE_EXTENT_INLINE
)
1208 * FIXME make sure to insert a trans record that
1209 * repeats the snapshot del on crash
1211 disk_bytenr
= btrfs_file_extent_disk_bytenr(leaf
, fi
);
1212 if (disk_bytenr
== 0)
1214 ret
= btrfs_free_extent(trans
, root
, disk_bytenr
,
1215 btrfs_file_extent_disk_num_bytes(leaf
, fi
), 0);
1221 static void reada_walk_down(struct btrfs_root
*root
,
1222 struct extent_buffer
*node
)
1232 nritems
= btrfs_header_nritems(node
);
1233 level
= btrfs_header_level(node
);
1234 for (i
= 0; i
< nritems
; i
++) {
1235 bytenr
= btrfs_node_blockptr(node
, i
);
1236 blocksize
= btrfs_level_size(root
, level
- 1);
1237 ret
= lookup_extent_ref(NULL
, root
, bytenr
, blocksize
, &refs
);
1241 mutex_unlock(&root
->fs_info
->fs_mutex
);
1242 ret
= readahead_tree_block(root
, bytenr
, blocksize
);
1244 mutex_lock(&root
->fs_info
->fs_mutex
);
1251 * helper function for drop_snapshot, this walks down the tree dropping ref
1252 * counts as it goes.
1254 static int walk_down_tree(struct btrfs_trans_handle
*trans
, struct btrfs_root
1255 *root
, struct btrfs_path
*path
, int *level
)
1257 struct extent_buffer
*next
;
1258 struct extent_buffer
*cur
;
1264 WARN_ON(*level
< 0);
1265 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
1266 ret
= lookup_extent_ref(trans
, root
,
1267 path
->nodes
[*level
]->start
,
1268 path
->nodes
[*level
]->len
, &refs
);
1274 * walk down to the last node level and free all the leaves
1276 while(*level
>= 0) {
1277 WARN_ON(*level
< 0);
1278 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
1279 cur
= path
->nodes
[*level
];
1281 if (*level
> 0 && path
->slots
[*level
] == 0)
1282 reada_walk_down(root
, cur
);
1284 if (btrfs_header_level(cur
) != *level
)
1287 if (path
->slots
[*level
] >=
1288 btrfs_header_nritems(cur
))
1291 ret
= drop_leaf_ref(trans
, root
, cur
);
1295 bytenr
= btrfs_node_blockptr(cur
, path
->slots
[*level
]);
1296 blocksize
= btrfs_level_size(root
, *level
- 1);
1297 ret
= lookup_extent_ref(trans
, root
, bytenr
, blocksize
, &refs
);
1300 path
->slots
[*level
]++;
1301 ret
= btrfs_free_extent(trans
, root
, bytenr
,
1306 next
= btrfs_find_tree_block(root
, bytenr
, blocksize
);
1307 if (!next
|| !btrfs_buffer_uptodate(next
)) {
1308 free_extent_buffer(next
);
1309 mutex_unlock(&root
->fs_info
->fs_mutex
);
1310 next
= read_tree_block(root
, bytenr
, blocksize
);
1311 mutex_lock(&root
->fs_info
->fs_mutex
);
1313 /* we dropped the lock, check one more time */
1314 ret
= lookup_extent_ref(trans
, root
, bytenr
,
1318 path
->slots
[*level
]++;
1319 free_extent_buffer(next
);
1320 ret
= btrfs_free_extent(trans
, root
,
1321 bytenr
, blocksize
, 1);
1326 WARN_ON(*level
<= 0);
1327 if (path
->nodes
[*level
-1])
1328 free_extent_buffer(path
->nodes
[*level
-1]);
1329 path
->nodes
[*level
-1] = next
;
1330 *level
= btrfs_header_level(next
);
1331 path
->slots
[*level
] = 0;
1334 WARN_ON(*level
< 0);
1335 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
1336 ret
= btrfs_free_extent(trans
, root
, path
->nodes
[*level
]->start
,
1337 path
->nodes
[*level
]->len
, 1);
1338 free_extent_buffer(path
->nodes
[*level
]);
1339 path
->nodes
[*level
] = NULL
;
1346 * helper for dropping snapshots. This walks back up the tree in the path
1347 * to find the first node higher up where we haven't yet gone through
1350 static int walk_up_tree(struct btrfs_trans_handle
*trans
, struct btrfs_root
1351 *root
, struct btrfs_path
*path
, int *level
)
1356 struct btrfs_root_item
*root_item
= &root
->root_item
;
1358 for(i
= *level
; i
< BTRFS_MAX_LEVEL
- 1 && path
->nodes
[i
]; i
++) {
1359 slot
= path
->slots
[i
];
1360 if (slot
< btrfs_header_nritems(path
->nodes
[i
]) - 1) {
1361 struct extent_buffer
*node
;
1362 struct btrfs_disk_key disk_key
;
1363 node
= path
->nodes
[i
];
1366 WARN_ON(*level
== 0);
1367 btrfs_node_key(node
, &disk_key
, path
->slots
[i
]);
1368 memcpy(&root_item
->drop_progress
,
1369 &disk_key
, sizeof(disk_key
));
1370 root_item
->drop_level
= i
;
1373 ret
= btrfs_free_extent(trans
, root
,
1374 path
->nodes
[*level
]->start
,
1375 path
->nodes
[*level
]->len
, 1);
1377 free_extent_buffer(path
->nodes
[*level
]);
1378 path
->nodes
[*level
] = NULL
;
1386 * drop the reference count on the tree rooted at 'snap'. This traverses
1387 * the tree freeing any blocks that have a ref count of zero after being
1390 int btrfs_drop_snapshot(struct btrfs_trans_handle
*trans
, struct btrfs_root
1396 struct btrfs_path
*path
;
1399 struct btrfs_root_item
*root_item
= &root
->root_item
;
1401 path
= btrfs_alloc_path();
1404 level
= btrfs_header_level(root
->node
);
1406 if (btrfs_disk_key_objectid(&root_item
->drop_progress
) == 0) {
1407 path
->nodes
[level
] = root
->node
;
1408 extent_buffer_get(root
->node
);
1409 path
->slots
[level
] = 0;
1411 struct btrfs_key key
;
1412 struct btrfs_disk_key found_key
;
1413 struct extent_buffer
*node
;
1415 btrfs_disk_key_to_cpu(&key
, &root_item
->drop_progress
);
1416 level
= root_item
->drop_level
;
1417 path
->lowest_level
= level
;
1418 wret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
1423 node
= path
->nodes
[level
];
1424 btrfs_node_key(node
, &found_key
, path
->slots
[level
]);
1425 WARN_ON(memcmp(&found_key
, &root_item
->drop_progress
,
1426 sizeof(found_key
)));
1429 wret
= walk_down_tree(trans
, root
, path
, &level
);
1435 wret
= walk_up_tree(trans
, root
, path
, &level
);
1443 for (i
= 0; i
<= orig_level
; i
++) {
1444 if (path
->nodes
[i
]) {
1445 free_extent_buffer(path
->nodes
[i
]);
1446 path
->nodes
[i
] = NULL
;
1450 btrfs_free_path(path
);
1454 int btrfs_free_block_groups(struct btrfs_fs_info
*info
)
1461 ret
= find_first_extent_bit(&info
->block_group_cache
, 0,
1462 &start
, &end
, (unsigned int)-1);
1465 clear_extent_bits(&info
->block_group_cache
, start
,
1466 end
, (unsigned int)-1, GFP_NOFS
);
1469 ret
= find_first_extent_bit(&info
->free_space_cache
, 0,
1470 &start
, &end
, EXTENT_DIRTY
);
1473 clear_extent_dirty(&info
->free_space_cache
, start
,
1479 int btrfs_read_block_groups(struct btrfs_root
*root
)
1481 struct btrfs_path
*path
;
1485 struct btrfs_block_group_cache
*cache
;
1486 struct btrfs_fs_info
*info
= root
->fs_info
;
1487 struct extent_map_tree
*block_group_cache
;
1488 struct btrfs_key key
;
1489 struct btrfs_key found_key
;
1490 struct extent_buffer
*leaf
;
1492 block_group_cache
= &info
->block_group_cache
;
1494 root
= info
->extent_root
;
1496 key
.offset
= BTRFS_BLOCK_GROUP_SIZE
;
1497 btrfs_set_key_type(&key
, BTRFS_BLOCK_GROUP_ITEM_KEY
);
1499 path
= btrfs_alloc_path();
1504 ret
= btrfs_search_slot(NULL
, info
->extent_root
,
1510 leaf
= path
->nodes
[0];
1511 btrfs_item_key_to_cpu(leaf
, &found_key
, path
->slots
[0]);
1512 cache
= kmalloc(sizeof(*cache
), GFP_NOFS
);
1518 read_extent_buffer(leaf
, &cache
->item
,
1519 btrfs_item_ptr_offset(leaf
, path
->slots
[0]),
1520 sizeof(cache
->item
));
1521 memcpy(&cache
->key
, &found_key
, sizeof(found_key
));
1524 key
.objectid
= found_key
.objectid
+ found_key
.offset
;
1525 btrfs_release_path(root
, path
);
1527 if (cache
->item
.flags
& BTRFS_BLOCK_GROUP_DATA
) {
1528 bit
= BLOCK_GROUP_DATA
;
1531 bit
= BLOCK_GROUP_METADATA
;
1535 /* use EXTENT_LOCKED to prevent merging */
1536 set_extent_bits(block_group_cache
, found_key
.objectid
,
1537 found_key
.objectid
+ found_key
.offset
- 1,
1538 bit
| EXTENT_LOCKED
, GFP_NOFS
);
1539 set_state_private(block_group_cache
, found_key
.objectid
,
1543 btrfs_super_total_bytes(&info
->super_copy
))
1547 btrfs_free_path(path
);