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 static int finish_current_insert(struct btrfs_trans_handle
*trans
, struct
26 btrfs_root
*extent_root
);
27 static int del_pending_extents(struct btrfs_trans_handle
*trans
, struct
28 btrfs_root
*extent_root
);
30 static int cache_block_group(struct btrfs_root
*root
,
31 struct btrfs_block_group_cache
*block_group
)
33 struct btrfs_path
*path
;
36 struct btrfs_leaf
*leaf
;
37 struct radix_tree_root
*extent_radix
;
44 root
= root
->fs_info
->extent_root
;
45 extent_radix
= &root
->fs_info
->extent_map_radix
;
47 if (block_group
->cached
)
49 if (block_group
->data
)
51 path
= btrfs_alloc_path();
55 key
.objectid
= block_group
->key
.objectid
;
58 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
59 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
62 if (ret
&& path
->slots
[0] > 0)
65 leaf
= btrfs_buffer_leaf(path
->nodes
[0]);
66 slot
= path
->slots
[0];
67 if (slot
>= btrfs_header_nritems(&leaf
->header
)) {
68 ret
= btrfs_next_leaf(root
, path
);
75 hole_size
= block_group
->key
.objectid
+
76 block_group
->key
.offset
- last
;
78 last
= block_group
->key
.objectid
;
79 hole_size
= block_group
->key
.offset
;
81 for (i
= 0; i
< hole_size
; i
++) {
82 set_radix_bit(extent_radix
,
88 btrfs_disk_key_to_cpu(&key
, &leaf
->items
[slot
].key
);
89 if (key
.objectid
>= block_group
->key
.objectid
+
90 block_group
->key
.offset
) {
92 hole_size
= block_group
->key
.objectid
+
93 block_group
->key
.offset
- last
;
95 last
= block_group
->key
.objectid
;
96 hole_size
= block_group
->key
.offset
;
98 for (i
= 0; i
< hole_size
; i
++) {
99 set_radix_bit(extent_radix
, last
+ i
);
103 if (btrfs_key_type(&key
) == BTRFS_EXTENT_ITEM_KEY
) {
105 last
= key
.objectid
+ key
.offset
;
108 hole_size
= key
.objectid
- last
;
109 for (i
= 0; i
< hole_size
; i
++) {
110 set_radix_bit(extent_radix
, last
+ i
);
112 last
= key
.objectid
+ key
.offset
;
118 block_group
->cached
= 1;
120 btrfs_free_path(path
);
124 struct btrfs_block_group_cache
*btrfs_lookup_block_group(struct
128 struct btrfs_block_group_cache
*block_group
;
131 ret
= radix_tree_gang_lookup(&info
->block_group_radix
,
132 (void **)&block_group
,
135 if (block_group
->key
.objectid
<= blocknr
&& blocknr
<=
136 block_group
->key
.objectid
+ block_group
->key
.offset
)
139 ret
= radix_tree_gang_lookup(&info
->block_group_data_radix
,
140 (void **)&block_group
,
143 if (block_group
->key
.objectid
<= blocknr
&& blocknr
<=
144 block_group
->key
.objectid
+ block_group
->key
.offset
)
150 static u64
leaf_range(struct btrfs_root
*root
)
152 u64 size
= BTRFS_LEAF_DATA_SIZE(root
);
153 do_div(size
, sizeof(struct btrfs_extent_item
) +
154 sizeof(struct btrfs_item
));
158 static u64
find_search_start(struct btrfs_root
*root
,
159 struct btrfs_block_group_cache
**cache_ret
,
160 u64 search_start
, int num
)
162 unsigned long gang
[8];
164 struct btrfs_block_group_cache
*cache
= *cache_ret
;
165 u64 last
= max(search_start
, cache
->key
.objectid
);
170 ret
= cache_block_group(root
, cache
);
174 ret
= find_first_radix_bit(&root
->fs_info
->extent_map_radix
,
175 gang
, last
, ARRAY_SIZE(gang
));
178 last
= gang
[ret
-1] + 1;
180 if (ret
!= ARRAY_SIZE(gang
)) {
183 if (gang
[ret
-1] - gang
[0] > leaf_range(root
)) {
187 if (gang
[0] >= cache
->key
.objectid
+ cache
->key
.offset
) {
193 return max(cache
->last_alloc
, search_start
);
196 cache
= btrfs_lookup_block_group(root
->fs_info
,
197 last
+ cache
->key
.offset
- 1);
199 return max((*cache_ret
)->last_alloc
, search_start
);
201 cache
= btrfs_find_block_group(root
, cache
,
202 last
+ cache
->key
.offset
- 1, 0, 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
[8];
220 struct btrfs_block_group_cache
*found_group
= NULL
;
221 struct btrfs_fs_info
*info
= root
->fs_info
;
222 struct radix_tree_root
*radix
;
223 struct radix_tree_root
*swap_radix
;
237 radix
= &info
->block_group_data_radix
;
238 swap_radix
= &info
->block_group_radix
;
240 radix
= &info
->block_group_radix
;
241 swap_radix
= &info
->block_group_data_radix
;
245 struct btrfs_block_group_cache
*shint
;
246 shint
= btrfs_lookup_block_group(info
, search_start
);
247 if (shint
&& shint
->data
== data
) {
248 used
= btrfs_block_group_used(&shint
->item
);
249 if (used
+ shint
->pinned
<
250 div_factor(shint
->key
.offset
, factor
)) {
255 if (hint
&& hint
->data
== data
) {
256 used
= btrfs_block_group_used(&hint
->item
);
257 if (used
+ hint
->pinned
<
258 div_factor(hint
->key
.offset
, factor
)) {
261 if (used
>= div_factor(hint
->key
.offset
, 8)) {
262 radix_tree_tag_clear(radix
,
264 hint
->key
.offset
- 1,
265 BTRFS_BLOCK_GROUP_AVAIL
);
267 last
= hint
->key
.offset
* 3;
268 if (hint
->key
.objectid
>= last
)
269 last
= max(search_start
+ hint
->key
.offset
- 1,
270 hint
->key
.objectid
- last
);
272 last
= hint
->key
.objectid
+ hint
->key
.offset
;
276 hint_last
= max(hint
->key
.objectid
, search_start
);
278 hint_last
= search_start
;
283 ret
= radix_tree_gang_lookup_tag(radix
, (void **)cache
,
284 last
, ARRAY_SIZE(cache
),
285 BTRFS_BLOCK_GROUP_AVAIL
);
288 for (i
= 0; i
< ret
; i
++) {
289 last
= cache
[i
]->key
.objectid
+
290 cache
[i
]->key
.offset
;
291 used
= btrfs_block_group_used(&cache
[i
]->item
);
292 if (used
+ cache
[i
]->pinned
<
293 div_factor(cache
[i
]->key
.offset
, factor
)) {
294 found_group
= cache
[i
];
297 if (used
>= div_factor(cache
[i
]->key
.offset
, 8)) {
298 radix_tree_tag_clear(radix
,
299 cache
[i
]->key
.objectid
+
300 cache
[i
]->key
.offset
- 1,
301 BTRFS_BLOCK_GROUP_AVAIL
);
309 ret
= radix_tree_gang_lookup(radix
, (void **)cache
,
310 last
, ARRAY_SIZE(cache
));
313 for (i
= 0; i
< ret
; i
++) {
314 last
= cache
[i
]->key
.objectid
+
315 cache
[i
]->key
.offset
;
316 used
= btrfs_block_group_used(&cache
[i
]->item
);
317 if (used
+ cache
[i
]->pinned
< cache
[i
]->key
.offset
) {
318 found_group
= cache
[i
];
321 if (used
>= cache
[i
]->key
.offset
) {
322 radix_tree_tag_clear(radix
,
323 cache
[i
]->key
.objectid
+
324 cache
[i
]->key
.offset
- 1,
325 BTRFS_BLOCK_GROUP_AVAIL
);
336 struct radix_tree_root
*tmp
= radix
;
344 ret
= radix_tree_gang_lookup(radix
,
345 (void **)&found_group
, 0, 1);
347 ret
= radix_tree_gang_lookup(swap_radix
,
348 (void **)&found_group
,
357 int btrfs_inc_extent_ref(struct btrfs_trans_handle
*trans
,
358 struct btrfs_root
*root
,
359 u64 blocknr
, u64 num_blocks
)
361 struct btrfs_path
*path
;
363 struct btrfs_key key
;
364 struct btrfs_leaf
*l
;
365 struct btrfs_extent_item
*item
;
368 path
= btrfs_alloc_path();
372 key
.objectid
= blocknr
;
374 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
375 key
.offset
= num_blocks
;
376 ret
= btrfs_search_slot(trans
, root
->fs_info
->extent_root
, &key
, path
,
384 l
= btrfs_buffer_leaf(path
->nodes
[0]);
385 item
= btrfs_item_ptr(l
, path
->slots
[0], struct btrfs_extent_item
);
386 refs
= btrfs_extent_refs(item
);
387 btrfs_set_extent_refs(item
, refs
+ 1);
388 btrfs_mark_buffer_dirty(path
->nodes
[0]);
390 btrfs_release_path(root
->fs_info
->extent_root
, path
);
391 btrfs_free_path(path
);
392 finish_current_insert(trans
, root
->fs_info
->extent_root
);
393 del_pending_extents(trans
, root
->fs_info
->extent_root
);
397 int btrfs_extent_post_op(struct btrfs_trans_handle
*trans
,
398 struct btrfs_root
*root
)
400 finish_current_insert(trans
, root
->fs_info
->extent_root
);
401 del_pending_extents(trans
, root
->fs_info
->extent_root
);
405 static int lookup_extent_ref(struct btrfs_trans_handle
*trans
,
406 struct btrfs_root
*root
, u64 blocknr
,
407 u64 num_blocks
, u32
*refs
)
409 struct btrfs_path
*path
;
411 struct btrfs_key key
;
412 struct btrfs_leaf
*l
;
413 struct btrfs_extent_item
*item
;
415 path
= btrfs_alloc_path();
416 key
.objectid
= blocknr
;
417 key
.offset
= num_blocks
;
419 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
420 ret
= btrfs_search_slot(trans
, root
->fs_info
->extent_root
, &key
, path
,
426 l
= btrfs_buffer_leaf(path
->nodes
[0]);
427 item
= btrfs_item_ptr(l
, path
->slots
[0], struct btrfs_extent_item
);
428 *refs
= btrfs_extent_refs(item
);
430 btrfs_free_path(path
);
434 int btrfs_inc_root_ref(struct btrfs_trans_handle
*trans
,
435 struct btrfs_root
*root
)
437 return btrfs_inc_extent_ref(trans
, root
, bh_blocknr(root
->node
), 1);
440 int btrfs_inc_ref(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
441 struct buffer_head
*buf
)
444 struct btrfs_node
*buf_node
;
445 struct btrfs_leaf
*buf_leaf
;
446 struct btrfs_disk_key
*key
;
447 struct btrfs_file_extent_item
*fi
;
456 buf_node
= btrfs_buffer_node(buf
);
457 leaf
= btrfs_is_leaf(buf_node
);
458 buf_leaf
= btrfs_buffer_leaf(buf
);
459 for (i
= 0; i
< btrfs_header_nritems(&buf_node
->header
); i
++) {
462 key
= &buf_leaf
->items
[i
].key
;
463 if (btrfs_disk_key_type(key
) != BTRFS_EXTENT_DATA_KEY
)
465 fi
= btrfs_item_ptr(buf_leaf
, i
,
466 struct btrfs_file_extent_item
);
467 if (btrfs_file_extent_type(fi
) ==
468 BTRFS_FILE_EXTENT_INLINE
)
470 disk_blocknr
= btrfs_file_extent_disk_blocknr(fi
);
471 if (disk_blocknr
== 0)
473 ret
= btrfs_inc_extent_ref(trans
, root
, disk_blocknr
,
474 btrfs_file_extent_disk_num_blocks(fi
));
480 blocknr
= btrfs_node_blockptr(buf_node
, i
);
481 ret
= btrfs_inc_extent_ref(trans
, root
, blocknr
, 1);
491 for (i
=0; i
< faili
; i
++) {
494 key
= &buf_leaf
->items
[i
].key
;
495 if (btrfs_disk_key_type(key
) != BTRFS_EXTENT_DATA_KEY
)
497 fi
= btrfs_item_ptr(buf_leaf
, i
,
498 struct btrfs_file_extent_item
);
499 if (btrfs_file_extent_type(fi
) ==
500 BTRFS_FILE_EXTENT_INLINE
)
502 disk_blocknr
= btrfs_file_extent_disk_blocknr(fi
);
503 if (disk_blocknr
== 0)
505 err
= btrfs_free_extent(trans
, root
, disk_blocknr
,
506 btrfs_file_extent_disk_num_blocks(fi
), 0);
509 blocknr
= btrfs_node_blockptr(buf_node
, i
);
510 err
= btrfs_free_extent(trans
, root
, blocknr
, 1, 0);
517 static int write_one_cache_group(struct btrfs_trans_handle
*trans
,
518 struct btrfs_root
*root
,
519 struct btrfs_path
*path
,
520 struct btrfs_block_group_cache
*cache
)
524 struct btrfs_root
*extent_root
= root
->fs_info
->extent_root
;
525 struct btrfs_block_group_item
*bi
;
527 ret
= btrfs_search_slot(trans
, extent_root
, &cache
->key
, path
, 0, 1);
531 bi
= btrfs_item_ptr(btrfs_buffer_leaf(path
->nodes
[0]), path
->slots
[0],
532 struct btrfs_block_group_item
);
533 memcpy(bi
, &cache
->item
, sizeof(*bi
));
534 btrfs_mark_buffer_dirty(path
->nodes
[0]);
535 btrfs_release_path(extent_root
, path
);
537 finish_current_insert(trans
, extent_root
);
538 pending_ret
= del_pending_extents(trans
, extent_root
);
544 cache
->last_alloc
= cache
->first_free
;
549 static int write_dirty_block_radix(struct btrfs_trans_handle
*trans
,
550 struct btrfs_root
*root
,
551 struct radix_tree_root
*radix
)
553 struct btrfs_block_group_cache
*cache
[8];
558 struct btrfs_path
*path
;
559 unsigned long off
= 0;
561 path
= btrfs_alloc_path();
566 ret
= radix_tree_gang_lookup_tag(radix
, (void **)cache
,
567 off
, ARRAY_SIZE(cache
),
568 BTRFS_BLOCK_GROUP_DIRTY
);
571 for (i
= 0; i
< ret
; i
++) {
572 err
= write_one_cache_group(trans
, root
,
575 * if we fail to write the cache group, we want
576 * to keep it marked dirty in hopes that a later
581 off
= cache
[i
]->key
.objectid
+
582 cache
[i
]->key
.offset
;
586 radix_tree_tag_clear(radix
, cache
[i
]->key
.objectid
+
587 cache
[i
]->key
.offset
- 1,
588 BTRFS_BLOCK_GROUP_DIRTY
);
591 btrfs_free_path(path
);
595 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle
*trans
,
596 struct btrfs_root
*root
)
600 ret
= write_dirty_block_radix(trans
, root
,
601 &root
->fs_info
->block_group_radix
);
602 ret2
= write_dirty_block_radix(trans
, root
,
603 &root
->fs_info
->block_group_data_radix
);
611 static int update_block_group(struct btrfs_trans_handle
*trans
,
612 struct btrfs_root
*root
,
613 u64 blocknr
, u64 num
, int alloc
, int mark_free
,
616 struct btrfs_block_group_cache
*cache
;
617 struct btrfs_fs_info
*info
= root
->fs_info
;
625 cache
= btrfs_lookup_block_group(info
, blocknr
);
629 block_in_group
= blocknr
- cache
->key
.objectid
;
630 WARN_ON(block_in_group
> cache
->key
.offset
);
631 radix_tree_tag_set(cache
->radix
, cache
->key
.objectid
+
632 cache
->key
.offset
- 1,
633 BTRFS_BLOCK_GROUP_DIRTY
);
635 old_val
= btrfs_block_group_used(&cache
->item
);
636 num
= min(total
, cache
->key
.offset
- block_in_group
);
638 if (blocknr
> cache
->last_alloc
)
639 cache
->last_alloc
= blocknr
;
641 for (i
= 0; i
< num
; i
++) {
642 clear_radix_bit(&info
->extent_map_radix
,
646 if (cache
->data
!= data
&&
647 old_val
< (cache
->key
.offset
>> 1)) {
649 radix_tree_delete(cache
->radix
,
650 cache
->key
.objectid
+
651 cache
->key
.offset
- 1);
655 &info
->block_group_data_radix
;
657 BTRFS_BLOCK_GROUP_DATA
;
659 cache
->radix
= &info
->block_group_radix
;
661 ~BTRFS_BLOCK_GROUP_DATA
;
663 ret
= radix_tree_insert(cache
->radix
,
664 cache
->key
.objectid
+
665 cache
->key
.offset
- 1,
671 if (blocknr
< cache
->first_free
)
672 cache
->first_free
= blocknr
;
673 if (!cache
->data
&& mark_free
) {
674 for (i
= 0; i
< num
; i
++) {
675 set_radix_bit(&info
->extent_map_radix
,
679 if (old_val
< (cache
->key
.offset
>> 1) &&
680 old_val
+ num
>= (cache
->key
.offset
>> 1)) {
681 radix_tree_tag_set(cache
->radix
,
682 cache
->key
.objectid
+
683 cache
->key
.offset
- 1,
684 BTRFS_BLOCK_GROUP_AVAIL
);
687 btrfs_set_block_group_used(&cache
->item
, old_val
);
694 int btrfs_copy_pinned(struct btrfs_root
*root
, struct radix_tree_root
*copy
)
696 unsigned long gang
[8];
698 struct radix_tree_root
*pinned_radix
= &root
->fs_info
->pinned_radix
;
703 ret
= find_first_radix_bit(pinned_radix
, gang
, last
,
707 for (i
= 0 ; i
< ret
; i
++) {
708 set_radix_bit(copy
, gang
[i
]);
712 ret
= find_first_radix_bit(&root
->fs_info
->extent_ins_radix
, gang
, 0,
718 int btrfs_finish_extent_commit(struct btrfs_trans_handle
*trans
,
719 struct btrfs_root
*root
,
720 struct radix_tree_root
*unpin_radix
)
722 unsigned long gang
[8];
723 struct btrfs_block_group_cache
*block_group
;
727 struct radix_tree_root
*pinned_radix
= &root
->fs_info
->pinned_radix
;
728 struct radix_tree_root
*extent_radix
= &root
->fs_info
->extent_map_radix
;
731 ret
= find_first_radix_bit(unpin_radix
, gang
, 0,
737 for (i
= 0; i
< ret
; i
++) {
738 clear_radix_bit(pinned_radix
, gang
[i
]);
739 clear_radix_bit(unpin_radix
, gang
[i
]);
740 block_group
= btrfs_lookup_block_group(root
->fs_info
,
743 WARN_ON(block_group
->pinned
== 0);
744 block_group
->pinned
--;
745 if (gang
[i
] < block_group
->last_alloc
)
746 block_group
->last_alloc
= gang
[i
];
747 if (!block_group
->data
)
748 set_radix_bit(extent_radix
, gang
[i
]);
755 static int finish_current_insert(struct btrfs_trans_handle
*trans
, struct
756 btrfs_root
*extent_root
)
758 struct btrfs_key ins
;
759 struct btrfs_extent_item extent_item
;
763 unsigned long gang
[8];
764 struct btrfs_fs_info
*info
= extent_root
->fs_info
;
766 btrfs_set_extent_refs(&extent_item
, 1);
769 btrfs_set_key_type(&ins
, BTRFS_EXTENT_ITEM_KEY
);
770 btrfs_set_extent_owner(&extent_item
, extent_root
->root_key
.objectid
);
773 ret
= find_first_radix_bit(&info
->extent_ins_radix
, gang
, 0,
778 for (i
= 0; i
< ret
; i
++) {
779 ins
.objectid
= gang
[i
];
780 err
= btrfs_insert_item(trans
, extent_root
, &ins
,
782 sizeof(extent_item
));
783 clear_radix_bit(&info
->extent_ins_radix
, gang
[i
]);
790 static int pin_down_block(struct btrfs_root
*root
, u64 blocknr
, int pending
)
793 struct btrfs_header
*header
;
794 struct buffer_head
*bh
;
797 bh
= btrfs_find_tree_block(root
, blocknr
);
799 if (buffer_uptodate(bh
)) {
801 root
->fs_info
->running_transaction
->transid
;
802 header
= btrfs_buffer_header(bh
);
803 if (btrfs_header_generation(header
) ==
805 btrfs_block_release(root
, bh
);
809 btrfs_block_release(root
, bh
);
811 err
= set_radix_bit(&root
->fs_info
->pinned_radix
, blocknr
);
813 struct btrfs_block_group_cache
*cache
;
814 cache
= btrfs_lookup_block_group(root
->fs_info
,
820 err
= set_radix_bit(&root
->fs_info
->pending_del_radix
, blocknr
);
827 * remove an extent from the root, returns 0 on success
829 static int __free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
830 *root
, u64 blocknr
, u64 num_blocks
, int pin
,
833 struct btrfs_path
*path
;
834 struct btrfs_key key
;
835 struct btrfs_fs_info
*info
= root
->fs_info
;
836 struct btrfs_root
*extent_root
= info
->extent_root
;
838 struct btrfs_extent_item
*ei
;
841 key
.objectid
= blocknr
;
843 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
844 key
.offset
= num_blocks
;
846 path
= btrfs_alloc_path();
850 ret
= btrfs_search_slot(trans
, extent_root
, &key
, path
, -1, 1);
854 ei
= btrfs_item_ptr(btrfs_buffer_leaf(path
->nodes
[0]), path
->slots
[0],
855 struct btrfs_extent_item
);
856 BUG_ON(ei
->refs
== 0);
857 refs
= btrfs_extent_refs(ei
) - 1;
858 btrfs_set_extent_refs(ei
, refs
);
859 btrfs_mark_buffer_dirty(path
->nodes
[0]);
861 u64 super_blocks_used
, root_blocks_used
;
864 ret
= pin_down_block(root
, blocknr
, 0);
868 /* block accounting for super block */
869 super_blocks_used
= btrfs_super_blocks_used(&info
->super_copy
);
870 btrfs_set_super_blocks_used(&info
->super_copy
,
871 super_blocks_used
- num_blocks
);
873 /* block accounting for root item */
874 root_blocks_used
= btrfs_root_blocks_used(&root
->root_item
);
875 btrfs_set_root_blocks_used(&root
->root_item
,
876 root_blocks_used
- num_blocks
);
878 ret
= btrfs_del_item(trans
, extent_root
, path
);
882 ret
= update_block_group(trans
, root
, blocknr
, num_blocks
, 0,
886 btrfs_free_path(path
);
887 finish_current_insert(trans
, extent_root
);
892 * find all the blocks marked as pending in the radix tree and remove
893 * them from the extent map
895 static int del_pending_extents(struct btrfs_trans_handle
*trans
, struct
896 btrfs_root
*extent_root
)
901 unsigned long gang
[4];
903 struct radix_tree_root
*pending_radix
;
904 struct radix_tree_root
*pinned_radix
;
905 struct btrfs_block_group_cache
*cache
;
907 pending_radix
= &extent_root
->fs_info
->pending_del_radix
;
908 pinned_radix
= &extent_root
->fs_info
->pinned_radix
;
911 ret
= find_first_radix_bit(pending_radix
, gang
, 0,
915 for (i
= 0; i
< ret
; i
++) {
916 wret
= set_radix_bit(pinned_radix
, gang
[i
]);
919 btrfs_lookup_block_group(extent_root
->fs_info
,
925 printk(KERN_CRIT
"set_radix_bit, err %d\n",
929 wret
= clear_radix_bit(pending_radix
, gang
[i
]);
931 wret
= __free_extent(trans
, extent_root
,
941 * remove an extent from the root, returns 0 on success
943 int btrfs_free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
944 *root
, u64 blocknr
, u64 num_blocks
, int pin
)
946 struct btrfs_root
*extent_root
= root
->fs_info
->extent_root
;
950 if (root
== extent_root
) {
951 pin_down_block(root
, blocknr
, 1);
954 ret
= __free_extent(trans
, root
, blocknr
, num_blocks
, pin
, pin
== 0);
955 pending_ret
= del_pending_extents(trans
, root
->fs_info
->extent_root
);
956 return ret
? ret
: pending_ret
;
960 * walks the btree of allocated extents and find a hole of a given size.
961 * The key ins is changed to record the hole:
962 * ins->objectid == block start
963 * ins->flags = BTRFS_EXTENT_ITEM_KEY
964 * ins->offset == number of blocks
965 * Any available blocks before search_start are skipped.
967 static int find_free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
968 *orig_root
, u64 num_blocks
, u64 empty_size
,
969 u64 search_start
, u64 search_end
, u64 hint_block
,
970 struct btrfs_key
*ins
, u64 exclude_start
,
971 u64 exclude_nr
, int data
)
973 struct btrfs_path
*path
;
974 struct btrfs_key key
;
980 u64 orig_search_start
= search_start
;
982 struct btrfs_leaf
*l
;
983 struct btrfs_root
* root
= orig_root
->fs_info
->extent_root
;
984 struct btrfs_fs_info
*info
= root
->fs_info
;
985 int total_needed
= num_blocks
;
987 struct btrfs_block_group_cache
*block_group
;
991 WARN_ON(num_blocks
< 1);
993 btrfs_set_key_type(ins
, BTRFS_EXTENT_ITEM_KEY
);
995 level
= btrfs_header_level(btrfs_buffer_header(root
->node
));
996 if (search_end
== (u64
)-1)
997 search_end
= btrfs_super_total_blocks(&info
->super_copy
);
999 block_group
= btrfs_lookup_block_group(info
, hint_block
);
1000 block_group
= btrfs_find_block_group(root
, block_group
,
1001 hint_block
, data
, 1);
1003 block_group
= btrfs_find_block_group(root
,
1004 trans
->block_group
, 0,
1008 total_needed
+= empty_size
;
1009 path
= btrfs_alloc_path();
1012 if (!block_group
->data
)
1013 search_start
= find_search_start(root
, &block_group
,
1014 search_start
, total_needed
);
1015 else if (!full_scan
)
1016 search_start
= max(block_group
->last_alloc
, search_start
);
1018 btrfs_init_path(path
);
1019 ins
->objectid
= search_start
;
1024 ret
= btrfs_search_slot(trans
, root
, ins
, path
, 0, 0);
1028 if (path
->slots
[0] > 0) {
1032 l
= btrfs_buffer_leaf(path
->nodes
[0]);
1033 btrfs_disk_key_to_cpu(&key
, &l
->items
[path
->slots
[0]].key
);
1035 * a rare case, go back one key if we hit a block group item
1036 * instead of an extent item
1038 if (btrfs_key_type(&key
) != BTRFS_EXTENT_ITEM_KEY
&&
1039 key
.objectid
+ key
.offset
>= search_start
) {
1040 ins
->objectid
= key
.objectid
;
1041 ins
->offset
= key
.offset
- 1;
1042 btrfs_release_path(root
, path
);
1043 ret
= btrfs_search_slot(trans
, root
, ins
, path
, 0, 0);
1047 if (path
->slots
[0] > 0) {
1053 l
= btrfs_buffer_leaf(path
->nodes
[0]);
1054 slot
= path
->slots
[0];
1055 if (slot
>= btrfs_header_nritems(&l
->header
)) {
1056 ret
= btrfs_next_leaf(root
, path
);
1062 ins
->objectid
= search_start
;
1063 ins
->offset
= search_end
- search_start
;
1067 ins
->objectid
= last_block
> search_start
?
1068 last_block
: search_start
;
1069 ins
->offset
= search_end
- ins
->objectid
;
1073 btrfs_disk_key_to_cpu(&key
, &l
->items
[slot
].key
);
1074 if (key
.objectid
>= search_start
&& key
.objectid
> last_block
&&
1076 if (last_block
< search_start
)
1077 last_block
= search_start
;
1078 hole_size
= key
.objectid
- last_block
;
1079 if (hole_size
>= num_blocks
) {
1080 ins
->objectid
= last_block
;
1081 ins
->offset
= hole_size
;
1086 if (btrfs_key_type(&key
) != BTRFS_EXTENT_ITEM_KEY
)
1090 last_block
= key
.objectid
+ key
.offset
;
1091 if (!full_scan
&& last_block
>= block_group
->key
.objectid
+
1092 block_group
->key
.offset
) {
1093 btrfs_release_path(root
, path
);
1094 search_start
= block_group
->key
.objectid
+
1095 block_group
->key
.offset
* 2;
1103 /* we have to make sure we didn't find an extent that has already
1104 * been allocated by the map tree or the original allocation
1106 btrfs_release_path(root
, path
);
1107 BUG_ON(ins
->objectid
< search_start
);
1109 if (ins
->objectid
+ num_blocks
>= search_end
) {
1114 search_start
= orig_search_start
;
1117 total_needed
-= empty_size
;
1123 for (test_block
= ins
->objectid
;
1124 test_block
< ins
->objectid
+ num_blocks
; test_block
++) {
1125 if (test_radix_bit(&info
->pinned_radix
, test_block
) ||
1126 test_radix_bit(&info
->extent_ins_radix
, test_block
)) {
1127 search_start
= test_block
+ 1;
1131 if (exclude_nr
> 0 && (ins
->objectid
+ num_blocks
> exclude_start
&&
1132 ins
->objectid
< exclude_start
+ exclude_nr
)) {
1133 search_start
= exclude_start
+ exclude_nr
;
1137 block_group
= btrfs_lookup_block_group(info
, ins
->objectid
);
1139 trans
->block_group
= block_group
;
1141 ins
->offset
= num_blocks
;
1142 btrfs_free_path(path
);
1146 if (search_start
+ num_blocks
>= search_end
) {
1147 search_start
= orig_search_start
;
1154 total_needed
-= empty_size
;
1159 block_group
= btrfs_lookup_block_group(info
, search_start
);
1162 block_group
= btrfs_find_block_group(root
, block_group
,
1163 search_start
, data
, 0);
1167 btrfs_release_path(root
, path
);
1168 btrfs_free_path(path
);
1172 * finds a free extent and does all the dirty work required for allocation
1173 * returns the key for the extent through ins, and a tree buffer for
1174 * the first block of the extent through buf.
1176 * returns 0 if everything worked, non-zero otherwise.
1178 int btrfs_alloc_extent(struct btrfs_trans_handle
*trans
,
1179 struct btrfs_root
*root
, u64 owner
,
1180 u64 num_blocks
, u64 empty_size
, u64 hint_block
,
1181 u64 search_end
, struct btrfs_key
*ins
, int data
)
1185 u64 super_blocks_used
, root_blocks_used
;
1186 u64 search_start
= 0;
1187 struct btrfs_fs_info
*info
= root
->fs_info
;
1188 struct btrfs_root
*extent_root
= info
->extent_root
;
1189 struct btrfs_extent_item extent_item
;
1191 btrfs_set_extent_refs(&extent_item
, 1);
1192 btrfs_set_extent_owner(&extent_item
, owner
);
1194 WARN_ON(num_blocks
< 1);
1195 ret
= find_free_extent(trans
, root
, num_blocks
, empty_size
,
1196 search_start
, search_end
, hint_block
, ins
,
1197 trans
->alloc_exclude_start
,
1198 trans
->alloc_exclude_nr
, data
);
1203 /* block accounting for super block */
1204 super_blocks_used
= btrfs_super_blocks_used(&info
->super_copy
);
1205 btrfs_set_super_blocks_used(&info
->super_copy
, super_blocks_used
+
1208 /* block accounting for root item */
1209 root_blocks_used
= btrfs_root_blocks_used(&root
->root_item
);
1210 btrfs_set_root_blocks_used(&root
->root_item
, root_blocks_used
+
1213 if (root
== extent_root
) {
1214 BUG_ON(num_blocks
!= 1);
1215 set_radix_bit(&root
->fs_info
->extent_ins_radix
, ins
->objectid
);
1219 WARN_ON(trans
->alloc_exclude_nr
);
1220 trans
->alloc_exclude_start
= ins
->objectid
;
1221 trans
->alloc_exclude_nr
= ins
->offset
;
1222 ret
= btrfs_insert_item(trans
, extent_root
, ins
, &extent_item
,
1223 sizeof(extent_item
));
1225 trans
->alloc_exclude_start
= 0;
1226 trans
->alloc_exclude_nr
= 0;
1229 finish_current_insert(trans
, extent_root
);
1230 pending_ret
= del_pending_extents(trans
, extent_root
);
1239 ret
= update_block_group(trans
, root
, ins
->objectid
, ins
->offset
, 1, 0,
1246 * helper function to allocate a block for a given tree
1247 * returns the tree buffer or NULL.
1249 struct buffer_head
*btrfs_alloc_free_block(struct btrfs_trans_handle
*trans
,
1250 struct btrfs_root
*root
, u64 hint
,
1253 struct btrfs_key ins
;
1255 struct buffer_head
*buf
;
1257 ret
= btrfs_alloc_extent(trans
, root
, root
->root_key
.objectid
,
1258 1, empty_size
, hint
, (u64
)-1, &ins
, 0);
1261 return ERR_PTR(ret
);
1263 buf
= btrfs_find_create_tree_block(root
, ins
.objectid
);
1265 btrfs_free_extent(trans
, root
, ins
.objectid
, 1, 0);
1266 return ERR_PTR(-ENOMEM
);
1268 WARN_ON(buffer_dirty(buf
));
1269 set_buffer_uptodate(buf
);
1270 set_buffer_checked(buf
);
1271 set_buffer_defrag(buf
);
1272 set_radix_bit(&trans
->transaction
->dirty_pages
, buf
->b_page
->index
);
1276 static int drop_leaf_ref(struct btrfs_trans_handle
*trans
,
1277 struct btrfs_root
*root
, struct buffer_head
*cur
)
1279 struct btrfs_disk_key
*key
;
1280 struct btrfs_leaf
*leaf
;
1281 struct btrfs_file_extent_item
*fi
;
1286 BUG_ON(!btrfs_is_leaf(btrfs_buffer_node(cur
)));
1287 leaf
= btrfs_buffer_leaf(cur
);
1288 nritems
= btrfs_header_nritems(&leaf
->header
);
1289 for (i
= 0; i
< nritems
; i
++) {
1291 key
= &leaf
->items
[i
].key
;
1292 if (btrfs_disk_key_type(key
) != BTRFS_EXTENT_DATA_KEY
)
1294 fi
= btrfs_item_ptr(leaf
, i
, struct btrfs_file_extent_item
);
1295 if (btrfs_file_extent_type(fi
) == BTRFS_FILE_EXTENT_INLINE
)
1298 * FIXME make sure to insert a trans record that
1299 * repeats the snapshot del on crash
1301 disk_blocknr
= btrfs_file_extent_disk_blocknr(fi
);
1302 if (disk_blocknr
== 0)
1304 ret
= btrfs_free_extent(trans
, root
, disk_blocknr
,
1305 btrfs_file_extent_disk_num_blocks(fi
),
1312 static void reada_walk_down(struct btrfs_root
*root
,
1313 struct btrfs_node
*node
)
1321 nritems
= btrfs_header_nritems(&node
->header
);
1322 for (i
= 0; i
< nritems
; i
++) {
1323 blocknr
= btrfs_node_blockptr(node
, i
);
1324 ret
= lookup_extent_ref(NULL
, root
, blocknr
, 1, &refs
);
1328 mutex_unlock(&root
->fs_info
->fs_mutex
);
1329 ret
= readahead_tree_block(root
, blocknr
);
1331 mutex_lock(&root
->fs_info
->fs_mutex
);
1338 * helper function for drop_snapshot, this walks down the tree dropping ref
1339 * counts as it goes.
1341 static int walk_down_tree(struct btrfs_trans_handle
*trans
, struct btrfs_root
1342 *root
, struct btrfs_path
*path
, int *level
)
1344 struct buffer_head
*next
;
1345 struct buffer_head
*cur
;
1350 WARN_ON(*level
< 0);
1351 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
1352 ret
= lookup_extent_ref(trans
, root
, bh_blocknr(path
->nodes
[*level
]),
1359 * walk down to the last node level and free all the leaves
1361 while(*level
>= 0) {
1362 WARN_ON(*level
< 0);
1363 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
1364 cur
= path
->nodes
[*level
];
1366 if (*level
> 0 && path
->slots
[*level
] == 0)
1367 reada_walk_down(root
, btrfs_buffer_node(cur
));
1369 if (btrfs_header_level(btrfs_buffer_header(cur
)) != *level
)
1372 if (path
->slots
[*level
] >=
1373 btrfs_header_nritems(btrfs_buffer_header(cur
)))
1376 ret
= drop_leaf_ref(trans
, root
, cur
);
1380 blocknr
= btrfs_node_blockptr(btrfs_buffer_node(cur
),
1381 path
->slots
[*level
]);
1382 ret
= lookup_extent_ref(trans
, root
, blocknr
, 1, &refs
);
1385 path
->slots
[*level
]++;
1386 ret
= btrfs_free_extent(trans
, root
, blocknr
, 1, 1);
1390 next
= btrfs_find_tree_block(root
, blocknr
);
1391 if (!next
|| !buffer_uptodate(next
)) {
1393 mutex_unlock(&root
->fs_info
->fs_mutex
);
1394 next
= read_tree_block(root
, blocknr
);
1395 mutex_lock(&root
->fs_info
->fs_mutex
);
1397 /* we dropped the lock, check one more time */
1398 ret
= lookup_extent_ref(trans
, root
, blocknr
, 1, &refs
);
1401 path
->slots
[*level
]++;
1403 ret
= btrfs_free_extent(trans
, root
,
1409 WARN_ON(*level
<= 0);
1410 if (path
->nodes
[*level
-1])
1411 btrfs_block_release(root
, path
->nodes
[*level
-1]);
1412 path
->nodes
[*level
-1] = next
;
1413 *level
= btrfs_header_level(btrfs_buffer_header(next
));
1414 path
->slots
[*level
] = 0;
1417 WARN_ON(*level
< 0);
1418 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
1419 ret
= btrfs_free_extent(trans
, root
,
1420 bh_blocknr(path
->nodes
[*level
]), 1, 1);
1421 btrfs_block_release(root
, path
->nodes
[*level
]);
1422 path
->nodes
[*level
] = NULL
;
1429 * helper for dropping snapshots. This walks back up the tree in the path
1430 * to find the first node higher up where we haven't yet gone through
1433 static int walk_up_tree(struct btrfs_trans_handle
*trans
, struct btrfs_root
1434 *root
, struct btrfs_path
*path
, int *level
)
1439 struct btrfs_root_item
*root_item
= &root
->root_item
;
1441 for(i
= *level
; i
< BTRFS_MAX_LEVEL
- 1 && path
->nodes
[i
]; i
++) {
1442 slot
= path
->slots
[i
];
1443 if (slot
< btrfs_header_nritems(
1444 btrfs_buffer_header(path
->nodes
[i
])) - 1) {
1445 struct btrfs_node
*node
;
1446 node
= btrfs_buffer_node(path
->nodes
[i
]);
1449 WARN_ON(*level
== 0);
1450 memcpy(&root_item
->drop_progress
,
1451 &node
->ptrs
[path
->slots
[i
]].key
,
1452 sizeof(root_item
->drop_progress
));
1453 root_item
->drop_level
= i
;
1456 ret
= btrfs_free_extent(trans
, root
,
1457 bh_blocknr(path
->nodes
[*level
]),
1460 btrfs_block_release(root
, path
->nodes
[*level
]);
1461 path
->nodes
[*level
] = NULL
;
1469 * drop the reference count on the tree rooted at 'snap'. This traverses
1470 * the tree freeing any blocks that have a ref count of zero after being
1473 int btrfs_drop_snapshot(struct btrfs_trans_handle
*trans
, struct btrfs_root
1479 struct btrfs_path
*path
;
1482 struct btrfs_root_item
*root_item
= &root
->root_item
;
1484 path
= btrfs_alloc_path();
1487 level
= btrfs_header_level(btrfs_buffer_header(root
->node
));
1489 if (btrfs_disk_key_objectid(&root_item
->drop_progress
) == 0) {
1490 path
->nodes
[level
] = root
->node
;
1491 path
->slots
[level
] = 0;
1493 struct btrfs_key key
;
1494 struct btrfs_disk_key
*found_key
;
1495 struct btrfs_node
*node
;
1497 btrfs_disk_key_to_cpu(&key
, &root_item
->drop_progress
);
1498 level
= root_item
->drop_level
;
1499 path
->lowest_level
= level
;
1500 wret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
1505 node
= btrfs_buffer_node(path
->nodes
[level
]);
1506 found_key
= &node
->ptrs
[path
->slots
[level
]].key
;
1507 WARN_ON(memcmp(found_key
, &root_item
->drop_progress
,
1508 sizeof(*found_key
)));
1511 wret
= walk_down_tree(trans
, root
, path
, &level
);
1517 wret
= walk_up_tree(trans
, root
, path
, &level
);
1526 for (i
= 0; i
<= orig_level
; i
++) {
1527 if (path
->nodes
[i
]) {
1528 btrfs_block_release(root
, path
->nodes
[i
]);
1533 btrfs_free_path(path
);
1537 static int free_block_group_radix(struct radix_tree_root
*radix
)
1540 struct btrfs_block_group_cache
*cache
[8];
1544 ret
= radix_tree_gang_lookup(radix
, (void **)cache
, 0,
1548 for (i
= 0; i
< ret
; i
++) {
1549 radix_tree_delete(radix
, cache
[i
]->key
.objectid
+
1550 cache
[i
]->key
.offset
- 1);
1557 int btrfs_free_block_groups(struct btrfs_fs_info
*info
)
1561 unsigned long gang
[16];
1564 ret
= free_block_group_radix(&info
->block_group_radix
);
1565 ret2
= free_block_group_radix(&info
->block_group_data_radix
);
1572 ret
= find_first_radix_bit(&info
->extent_map_radix
,
1573 gang
, 0, ARRAY_SIZE(gang
));
1576 for (i
= 0; i
< ret
; i
++) {
1577 clear_radix_bit(&info
->extent_map_radix
, gang
[i
]);
1583 int btrfs_read_block_groups(struct btrfs_root
*root
)
1585 struct btrfs_path
*path
;
1588 struct btrfs_block_group_item
*bi
;
1589 struct btrfs_block_group_cache
*cache
;
1590 struct btrfs_fs_info
*info
= root
->fs_info
;
1591 struct radix_tree_root
*radix
;
1592 struct btrfs_key key
;
1593 struct btrfs_key found_key
;
1594 struct btrfs_leaf
*leaf
;
1595 u64 group_size_blocks
;
1598 group_size_blocks
= BTRFS_BLOCK_GROUP_SIZE
>>
1599 root
->fs_info
->sb
->s_blocksize_bits
;
1600 root
= info
->extent_root
;
1602 key
.offset
= group_size_blocks
;
1604 btrfs_set_key_type(&key
, BTRFS_BLOCK_GROUP_ITEM_KEY
);
1606 path
= btrfs_alloc_path();
1611 ret
= btrfs_search_slot(NULL
, info
->extent_root
,
1617 leaf
= btrfs_buffer_leaf(path
->nodes
[0]);
1618 btrfs_disk_key_to_cpu(&found_key
,
1619 &leaf
->items
[path
->slots
[0]].key
);
1620 cache
= kmalloc(sizeof(*cache
), GFP_NOFS
);
1626 bi
= btrfs_item_ptr(leaf
, path
->slots
[0],
1627 struct btrfs_block_group_item
);
1628 if (bi
->flags
& BTRFS_BLOCK_GROUP_DATA
) {
1629 radix
= &info
->block_group_data_radix
;
1632 radix
= &info
->block_group_radix
;
1636 memcpy(&cache
->item
, bi
, sizeof(*bi
));
1637 memcpy(&cache
->key
, &found_key
, sizeof(found_key
));
1638 cache
->last_alloc
= cache
->key
.objectid
;
1639 cache
->first_free
= cache
->key
.objectid
;
1643 cache
->radix
= radix
;
1645 key
.objectid
= found_key
.objectid
+ found_key
.offset
;
1646 btrfs_release_path(root
, path
);
1647 ret
= radix_tree_insert(radix
, found_key
.objectid
+
1648 found_key
.offset
- 1,
1651 used
= btrfs_block_group_used(bi
);
1652 if (used
< div_factor(key
.offset
, 8)) {
1653 radix_tree_tag_set(radix
, found_key
.objectid
+
1654 found_key
.offset
- 1,
1655 BTRFS_BLOCK_GROUP_AVAIL
);
1658 btrfs_super_total_blocks(&info
->super_copy
))
1662 btrfs_free_path(path
);