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 extent_buffer *leaf;
37 struct extent_map_tree *free_space_cache;
44 root = root->fs_info->extent_root;
45 free_space_cache = &root->fs_info->free_space_cache;
47 if (block_group->cached)
50 path = btrfs_alloc_path();
55 first_free = block_group->key.objectid;
56 key.objectid = block_group->key.objectid;
59 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
60 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
65 if (ret && path->slots[0] > 0)
69 leaf = path->nodes[0];
70 slot = path->slots[0];
71 if (slot >= btrfs_header_nritems(leaf)) {
72 ret = btrfs_next_leaf(root, path);
82 btrfs_item_key_to_cpu(leaf, &key, slot);
83 if (key.objectid < block_group->key.objectid) {
84 if (key.objectid + key.offset > first_free)
85 first_free = key.objectid + key.offset;
89 if (key.objectid >= block_group->key.objectid +
90 block_group->key.offset) {
94 if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
99 if (key.objectid > last) {
100 hole_size = key.objectid - last;
101 set_extent_dirty(free_space_cache, last,
102 last + hole_size - 1,
105 last = key.objectid + key.offset;
113 if (block_group->key.objectid +
114 block_group->key.offset > last) {
115 hole_size = block_group->key.objectid +
116 block_group->key.offset - last;
117 set_extent_dirty(free_space_cache, last,
118 last + hole_size - 1, GFP_NOFS);
120 block_group->cached = 1;
122 btrfs_free_path(path);
126 struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
130 struct btrfs_block_group_cache *block_group;
133 ret = radix_tree_gang_lookup(&info->block_group_radix,
134 (void **)&block_group,
137 if (block_group->key.objectid <= blocknr && blocknr <=
138 block_group->key.objectid + block_group->key.offset)
141 ret = radix_tree_gang_lookup(&info->block_group_data_radix,
142 (void **)&block_group,
145 if (block_group->key.objectid <= blocknr && blocknr <=
146 block_group->key.objectid + block_group->key.offset)
152 static u64 find_search_start(struct btrfs_root *root,
153 struct btrfs_block_group_cache **cache_ret,
154 u64 search_start, int num, int data)
157 struct btrfs_block_group_cache *cache = *cache_ret;
158 u64 last = max(search_start, cache->key.objectid);
163 ret = cache_block_group(root, cache);
167 ret = find_first_extent_bit(&root->fs_info->free_space_cache,
168 last, &start, &end, EXTENT_DIRTY);
172 start = max(last, start);
174 if (end + 1 - start < num)
176 if (start + num > cache->key.objectid + cache->key.offset)
181 return max(cache->last_alloc, search_start);
184 cache = btrfs_lookup_block_group(root->fs_info,
185 last + cache->key.offset - 1);
187 return max((*cache_ret)->last_alloc, search_start);
189 cache = btrfs_find_block_group(root, cache,
190 last + cache->key.offset - 1, data, 0);
195 static u64 div_factor(u64 num, int factor)
202 struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
203 struct btrfs_block_group_cache
204 *hint, u64 search_start,
207 struct btrfs_block_group_cache *cache[8];
208 struct btrfs_block_group_cache *found_group = NULL;
209 struct btrfs_fs_info *info = root->fs_info;
210 struct radix_tree_root *radix;
211 struct radix_tree_root *swap_radix;
225 radix = &info->block_group_data_radix;
226 swap_radix = &info->block_group_radix;
228 radix = &info->block_group_radix;
229 swap_radix = &info->block_group_data_radix;
233 struct btrfs_block_group_cache *shint;
234 shint = btrfs_lookup_block_group(info, search_start);
235 if (shint && shint->data == data) {
236 used = btrfs_block_group_used(&shint->item);
237 if (used + shint->pinned <
238 div_factor(shint->key.offset, factor)) {
243 if (hint && hint->data == data) {
244 used = btrfs_block_group_used(&hint->item);
245 if (used + hint->pinned <
246 div_factor(hint->key.offset, factor)) {
249 if (used >= div_factor(hint->key.offset, 8)) {
250 radix_tree_tag_clear(radix,
252 hint->key.offset - 1,
253 BTRFS_BLOCK_GROUP_AVAIL);
255 last = hint->key.offset * 3;
256 if (hint->key.objectid >= last)
257 last = max(search_start + hint->key.offset - 1,
258 hint->key.objectid - last);
260 last = hint->key.objectid + hint->key.offset;
264 hint_last = max(hint->key.objectid, search_start);
266 hint_last = search_start;
271 ret = radix_tree_gang_lookup_tag(radix, (void **)cache,
272 last, ARRAY_SIZE(cache),
273 BTRFS_BLOCK_GROUP_AVAIL);
276 for (i = 0; i < ret; i++) {
277 last = cache[i]->key.objectid +
278 cache[i]->key.offset;
279 used = btrfs_block_group_used(&cache[i]->item);
280 if (used + cache[i]->pinned <
281 div_factor(cache[i]->key.offset, factor)) {
282 found_group = cache[i];
285 if (used >= div_factor(cache[i]->key.offset, 8)) {
286 radix_tree_tag_clear(radix,
287 cache[i]->key.objectid +
288 cache[i]->key.offset - 1,
289 BTRFS_BLOCK_GROUP_AVAIL);
297 ret = radix_tree_gang_lookup(radix, (void **)cache,
298 last, ARRAY_SIZE(cache));
301 for (i = 0; i < ret; i++) {
302 last = cache[i]->key.objectid +
303 cache[i]->key.offset;
304 used = btrfs_block_group_used(&cache[i]->item);
305 if (used + cache[i]->pinned < cache[i]->key.offset) {
306 found_group = cache[i];
309 if (used >= cache[i]->key.offset) {
310 radix_tree_tag_clear(radix,
311 cache[i]->key.objectid +
312 cache[i]->key.offset - 1,
313 BTRFS_BLOCK_GROUP_AVAIL);
324 struct radix_tree_root *tmp = radix;
332 ret = radix_tree_gang_lookup(radix,
333 (void **)&found_group, 0, 1);
335 ret = radix_tree_gang_lookup(swap_radix,
336 (void **)&found_group,
345 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
346 struct btrfs_root *root,
347 u64 blocknr, u64 num_blocks)
349 struct btrfs_path *path;
351 struct btrfs_key key;
352 struct extent_buffer *l;
353 struct btrfs_extent_item *item;
356 path = btrfs_alloc_path();
360 key.objectid = blocknr;
361 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
362 key.offset = num_blocks;
363 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
372 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
373 refs = btrfs_extent_refs(l, item);
374 btrfs_set_extent_refs(l, item, refs + 1);
375 btrfs_mark_buffer_dirty(path->nodes[0]);
377 btrfs_release_path(root->fs_info->extent_root, path);
378 btrfs_free_path(path);
379 finish_current_insert(trans, root->fs_info->extent_root);
380 del_pending_extents(trans, root->fs_info->extent_root);
384 int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
385 struct btrfs_root *root)
387 finish_current_insert(trans, root->fs_info->extent_root);
388 del_pending_extents(trans, root->fs_info->extent_root);
392 static int lookup_extent_ref(struct btrfs_trans_handle *trans,
393 struct btrfs_root *root, u64 blocknr,
394 u64 num_blocks, u32 *refs)
396 struct btrfs_path *path;
398 struct btrfs_key key;
399 struct extent_buffer *l;
400 struct btrfs_extent_item *item;
402 path = btrfs_alloc_path();
403 key.objectid = blocknr;
404 key.offset = num_blocks;
405 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
406 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
411 btrfs_print_leaf(root, path->nodes[0]);
412 printk("failed to find block number %Lu\n", blocknr);
416 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
417 *refs = btrfs_extent_refs(l, item);
419 btrfs_free_path(path);
423 int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
424 struct btrfs_root *root)
426 return btrfs_inc_extent_ref(trans, root,
427 extent_buffer_blocknr(root->node), 1);
430 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
431 struct extent_buffer *buf)
435 struct btrfs_key key;
436 struct btrfs_file_extent_item *fi;
446 leaf = btrfs_is_leaf(buf);
447 nritems = btrfs_header_nritems(buf);
448 for (i = 0; i < nritems; i++) {
451 btrfs_item_key_to_cpu(buf, &key, i);
452 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
454 fi = btrfs_item_ptr(buf, i,
455 struct btrfs_file_extent_item);
456 if (btrfs_file_extent_type(buf, fi) ==
457 BTRFS_FILE_EXTENT_INLINE)
459 disk_blocknr = btrfs_file_extent_disk_blocknr(buf, fi);
460 if (disk_blocknr == 0)
462 ret = btrfs_inc_extent_ref(trans, root, disk_blocknr,
463 btrfs_file_extent_disk_num_blocks(buf, fi));
469 blocknr = btrfs_node_blockptr(buf, i);
470 ret = btrfs_inc_extent_ref(trans, root, blocknr, 1);
480 for (i =0; i < faili; i++) {
483 btrfs_item_key_to_cpu(buf, &key, i);
484 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
486 fi = btrfs_item_ptr(buf, i,
487 struct btrfs_file_extent_item);
488 if (btrfs_file_extent_type(buf, fi) ==
489 BTRFS_FILE_EXTENT_INLINE)
491 disk_blocknr = btrfs_file_extent_disk_blocknr(buf, fi);
492 if (disk_blocknr == 0)
494 err = btrfs_free_extent(trans, root, disk_blocknr,
495 btrfs_file_extent_disk_num_blocks(buf,
499 blocknr = btrfs_node_blockptr(buf, i);
500 err = btrfs_free_extent(trans, root, blocknr, 1, 0);
507 static int write_one_cache_group(struct btrfs_trans_handle *trans,
508 struct btrfs_root *root,
509 struct btrfs_path *path,
510 struct btrfs_block_group_cache *cache)
514 struct btrfs_root *extent_root = root->fs_info->extent_root;
516 struct extent_buffer *leaf;
518 ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
523 leaf = path->nodes[0];
524 bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
525 write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
526 btrfs_mark_buffer_dirty(leaf);
527 btrfs_release_path(extent_root, path);
529 finish_current_insert(trans, extent_root);
530 pending_ret = del_pending_extents(trans, extent_root);
536 cache->last_alloc = cache->first_free;
541 static int write_dirty_block_radix(struct btrfs_trans_handle *trans,
542 struct btrfs_root *root,
543 struct radix_tree_root *radix)
545 struct btrfs_block_group_cache *cache[8];
550 struct btrfs_path *path;
551 unsigned long off = 0;
553 path = btrfs_alloc_path();
558 ret = radix_tree_gang_lookup_tag(radix, (void **)cache,
559 off, ARRAY_SIZE(cache),
560 BTRFS_BLOCK_GROUP_DIRTY);
563 for (i = 0; i < ret; i++) {
564 err = write_one_cache_group(trans, root,
567 * if we fail to write the cache group, we want
568 * to keep it marked dirty in hopes that a later
573 off = cache[i]->key.objectid +
574 cache[i]->key.offset;
578 radix_tree_tag_clear(radix, cache[i]->key.objectid +
579 cache[i]->key.offset - 1,
580 BTRFS_BLOCK_GROUP_DIRTY);
583 btrfs_free_path(path);
587 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
588 struct btrfs_root *root)
592 ret = write_dirty_block_radix(trans, root,
593 &root->fs_info->block_group_radix);
594 ret2 = write_dirty_block_radix(trans, root,
595 &root->fs_info->block_group_data_radix);
603 static int update_block_group(struct btrfs_trans_handle *trans,
604 struct btrfs_root *root,
605 u64 blocknr, u64 num, int alloc, int mark_free,
608 struct btrfs_block_group_cache *cache;
609 struct btrfs_fs_info *info = root->fs_info;
616 cache = btrfs_lookup_block_group(info, blocknr);
620 block_in_group = blocknr - cache->key.objectid;
621 WARN_ON(block_in_group > cache->key.offset);
622 radix_tree_tag_set(cache->radix, cache->key.objectid +
623 cache->key.offset - 1,
624 BTRFS_BLOCK_GROUP_DIRTY);
626 old_val = btrfs_block_group_used(&cache->item);
627 num = min(total, cache->key.offset - block_in_group);
629 if (blocknr > cache->last_alloc)
630 cache->last_alloc = blocknr;
631 if (cache->data != data &&
632 old_val < (cache->key.offset >> 1)) {
634 radix_tree_delete(cache->radix,
635 cache->key.objectid +
636 cache->key.offset - 1);
640 &info->block_group_data_radix;
642 BTRFS_BLOCK_GROUP_DATA;
644 cache->radix = &info->block_group_radix;
646 ~BTRFS_BLOCK_GROUP_DATA;
648 ret = radix_tree_insert(cache->radix,
649 cache->key.objectid +
650 cache->key.offset - 1,
656 if (blocknr < cache->first_free)
657 cache->first_free = blocknr;
659 set_extent_dirty(&info->free_space_cache,
660 blocknr, blocknr + num - 1,
663 if (old_val < (cache->key.offset >> 1) &&
664 old_val + num >= (cache->key.offset >> 1)) {
665 radix_tree_tag_set(cache->radix,
666 cache->key.objectid +
667 cache->key.offset - 1,
668 BTRFS_BLOCK_GROUP_AVAIL);
671 btrfs_set_block_group_used(&cache->item, old_val);
678 int btrfs_copy_pinned(struct btrfs_root *root, struct radix_tree_root *copy)
680 unsigned long gang[8];
682 struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix;
687 ret = find_first_radix_bit(pinned_radix, gang, last,
691 for (i = 0 ; i < ret; i++) {
692 set_radix_bit(copy, gang[i]);
696 ret = find_first_radix_bit(&root->fs_info->extent_ins_radix, gang, 0,
702 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
703 struct btrfs_root *root,
704 struct radix_tree_root *unpin_radix)
706 unsigned long gang[8];
707 struct btrfs_block_group_cache *block_group;
711 struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix;
712 struct extent_map_tree *free_space_cache;
714 free_space_cache = &root->fs_info->free_space_cache;
717 ret = find_first_radix_bit(unpin_radix, gang, 0,
723 for (i = 0; i < ret; i++) {
724 clear_radix_bit(pinned_radix, gang[i]);
725 clear_radix_bit(unpin_radix, gang[i]);
726 block_group = btrfs_lookup_block_group(root->fs_info,
729 WARN_ON(block_group->pinned == 0);
730 block_group->pinned--;
731 if (gang[i] < block_group->last_alloc)
732 block_group->last_alloc = gang[i];
733 if (!block_group->data) {
734 set_extent_dirty(free_space_cache,
744 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
745 btrfs_root *extent_root)
747 struct btrfs_key ins;
748 struct btrfs_extent_item extent_item;
752 unsigned long gang[8];
753 struct btrfs_fs_info *info = extent_root->fs_info;
755 btrfs_set_stack_extent_refs(&extent_item, 1);
757 btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
758 btrfs_set_stack_extent_owner(&extent_item,
759 extent_root->root_key.objectid);
762 ret = find_first_radix_bit(&info->extent_ins_radix, gang, 0,
767 for (i = 0; i < ret; i++) {
768 ins.objectid = gang[i];
769 err = btrfs_insert_item(trans, extent_root, &ins,
771 sizeof(extent_item));
772 clear_radix_bit(&info->extent_ins_radix, gang[i]);
779 static int pin_down_block(struct btrfs_root *root, u64 blocknr, int pending)
782 struct extent_buffer *buf;
785 buf = btrfs_find_tree_block(root, blocknr);
787 if (btrfs_buffer_uptodate(buf)) {
789 root->fs_info->running_transaction->transid;
790 if (btrfs_header_generation(buf) == transid) {
791 free_extent_buffer(buf);
795 free_extent_buffer(buf);
797 err = set_radix_bit(&root->fs_info->pinned_radix, blocknr);
799 struct btrfs_block_group_cache *cache;
800 cache = btrfs_lookup_block_group(root->fs_info,
806 err = set_radix_bit(&root->fs_info->pending_del_radix, blocknr);
813 * remove an extent from the root, returns 0 on success
815 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
816 *root, u64 blocknr, u64 num_blocks, int pin,
819 struct btrfs_path *path;
820 struct btrfs_key key;
821 struct btrfs_fs_info *info = root->fs_info;
822 struct btrfs_root *extent_root = info->extent_root;
823 struct extent_buffer *leaf;
825 struct btrfs_extent_item *ei;
828 key.objectid = blocknr;
829 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
830 key.offset = num_blocks;
832 path = btrfs_alloc_path();
836 ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
841 leaf = path->nodes[0];
842 ei = btrfs_item_ptr(leaf, path->slots[0],
843 struct btrfs_extent_item);
844 refs = btrfs_extent_refs(leaf, ei);
847 btrfs_set_extent_refs(leaf, ei, refs);
848 btrfs_mark_buffer_dirty(leaf);
851 u64 super_blocks_used, root_blocks_used;
854 ret = pin_down_block(root, blocknr, 0);
858 /* block accounting for super block */
859 super_blocks_used = btrfs_super_blocks_used(&info->super_copy);
860 btrfs_set_super_blocks_used(&info->super_copy,
861 super_blocks_used - num_blocks);
863 /* block accounting for root item */
864 root_blocks_used = btrfs_root_used(&root->root_item);
865 btrfs_set_root_used(&root->root_item,
866 root_blocks_used - num_blocks);
868 ret = btrfs_del_item(trans, extent_root, path);
872 ret = update_block_group(trans, root, blocknr, num_blocks, 0,
876 btrfs_free_path(path);
877 finish_current_insert(trans, extent_root);
882 * find all the blocks marked as pending in the radix tree and remove
883 * them from the extent map
885 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
886 btrfs_root *extent_root)
891 unsigned long gang[4];
893 struct radix_tree_root *pending_radix;
894 struct radix_tree_root *pinned_radix;
895 struct btrfs_block_group_cache *cache;
897 pending_radix = &extent_root->fs_info->pending_del_radix;
898 pinned_radix = &extent_root->fs_info->pinned_radix;
901 ret = find_first_radix_bit(pending_radix, gang, 0,
905 for (i = 0; i < ret; i++) {
906 wret = set_radix_bit(pinned_radix, gang[i]);
909 btrfs_lookup_block_group(extent_root->fs_info,
915 printk(KERN_CRIT "set_radix_bit, err %d\n",
919 wret = clear_radix_bit(pending_radix, gang[i]);
921 wret = __free_extent(trans, extent_root,
931 * remove an extent from the root, returns 0 on success
933 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
934 *root, u64 blocknr, u64 num_blocks, int pin)
936 struct btrfs_root *extent_root = root->fs_info->extent_root;
940 if (root == extent_root) {
941 pin_down_block(root, blocknr, 1);
944 ret = __free_extent(trans, root, blocknr, num_blocks, pin, pin == 0);
945 pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
946 return ret ? ret : pending_ret;
950 * walks the btree of allocated extents and find a hole of a given size.
951 * The key ins is changed to record the hole:
952 * ins->objectid == block start
953 * ins->flags = BTRFS_EXTENT_ITEM_KEY
954 * ins->offset == number of blocks
955 * Any available blocks before search_start are skipped.
957 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
958 *orig_root, u64 num_blocks, u64 empty_size,
959 u64 search_start, u64 search_end, u64 hint_block,
960 struct btrfs_key *ins, u64 exclude_start,
961 u64 exclude_nr, int data)
963 struct btrfs_path *path;
964 struct btrfs_key key;
970 u64 orig_search_start = search_start;
972 struct extent_buffer *l;
973 struct btrfs_root * root = orig_root->fs_info->extent_root;
974 struct btrfs_fs_info *info = root->fs_info;
975 int total_needed = num_blocks;
977 struct btrfs_block_group_cache *block_group;
980 u64 cached_search_start = 0;
982 WARN_ON(num_blocks < 1);
983 btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
985 level = btrfs_header_level(root->node);
987 if (search_end == (u64)-1)
988 search_end = btrfs_super_total_blocks(&info->super_copy);
990 block_group = btrfs_lookup_block_group(info, hint_block);
991 block_group = btrfs_find_block_group(root, block_group,
992 hint_block, data, 1);
994 block_group = btrfs_find_block_group(root,
995 trans->block_group, 0,
999 total_needed += empty_size;
1000 path = btrfs_alloc_path();
1003 search_start = find_search_start(root, &block_group,
1004 search_start, total_needed, data);
1005 cached_search_start = search_start;
1007 btrfs_init_path(path);
1008 ins->objectid = search_start;
1013 ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
1017 if (path->slots[0] > 0) {
1022 btrfs_item_key_to_cpu(l, &key, path->slots[0]);
1025 * a rare case, go back one key if we hit a block group item
1026 * instead of an extent item
1028 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY &&
1029 key.objectid + key.offset >= search_start) {
1030 ins->objectid = key.objectid;
1031 ins->offset = key.offset - 1;
1032 btrfs_release_path(root, path);
1033 ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
1037 if (path->slots[0] > 0) {
1044 slot = path->slots[0];
1045 if (slot >= btrfs_header_nritems(l)) {
1046 ret = btrfs_next_leaf(root, path);
1052 ins->objectid = search_start;
1053 ins->offset = search_end - search_start;
1057 ins->objectid = last_block > search_start ?
1058 last_block : search_start;
1059 ins->offset = search_end - ins->objectid;
1063 btrfs_item_key_to_cpu(l, &key, slot);
1064 if (key.objectid >= search_start && key.objectid > last_block &&
1066 if (last_block < search_start)
1067 last_block = search_start;
1068 hole_size = key.objectid - last_block;
1069 if (hole_size >= num_blocks) {
1070 ins->objectid = last_block;
1071 ins->offset = hole_size;
1076 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY)
1080 last_block = key.objectid + key.offset;
1082 if (!full_scan && last_block >= block_group->key.objectid +
1083 block_group->key.offset) {
1084 btrfs_release_path(root, path);
1085 search_start = block_group->key.objectid +
1086 block_group->key.offset * 2;
1094 /* we have to make sure we didn't find an extent that has already
1095 * been allocated by the map tree or the original allocation
1097 btrfs_release_path(root, path);
1098 BUG_ON(ins->objectid < search_start);
1100 if (ins->objectid + num_blocks >= search_end)
1103 for (test_block = ins->objectid;
1104 test_block < ins->objectid + num_blocks; test_block++) {
1105 if (test_radix_bit(&info->pinned_radix, test_block) ||
1106 test_radix_bit(&info->extent_ins_radix, test_block)) {
1107 search_start = test_block + 1;
1111 if (exclude_nr > 0 && (ins->objectid + num_blocks > exclude_start &&
1112 ins->objectid < exclude_start + exclude_nr)) {
1113 search_start = exclude_start + exclude_nr;
1117 block_group = btrfs_lookup_block_group(info, ins->objectid);
1119 trans->block_group = block_group;
1121 ins->offset = num_blocks;
1122 btrfs_free_path(path);
1123 if (0 && ins->objectid != cached_search_start) {
1124 printk("\tcached was %Lu found %Lu\n", cached_search_start, ins->objectid);
1129 if (search_start + num_blocks >= search_end) {
1131 search_start = orig_search_start;
1138 total_needed -= empty_size;
1143 block_group = btrfs_lookup_block_group(info, search_start);
1146 block_group = btrfs_find_block_group(root, block_group,
1147 search_start, data, 0);
1151 btrfs_release_path(root, path);
1152 btrfs_free_path(path);
1156 * finds a free extent and does all the dirty work required for allocation
1157 * returns the key for the extent through ins, and a tree buffer for
1158 * the first block of the extent through buf.
1160 * returns 0 if everything worked, non-zero otherwise.
1162 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
1163 struct btrfs_root *root, u64 owner,
1164 u64 num_blocks, u64 empty_size, u64 hint_block,
1165 u64 search_end, struct btrfs_key *ins, int data)
1169 u64 super_blocks_used, root_blocks_used;
1170 u64 search_start = 0;
1171 struct btrfs_fs_info *info = root->fs_info;
1172 struct btrfs_root *extent_root = info->extent_root;
1173 struct btrfs_extent_item extent_item;
1175 btrfs_set_stack_extent_refs(&extent_item, 1);
1176 btrfs_set_stack_extent_owner(&extent_item, owner);
1178 WARN_ON(num_blocks < 1);
1179 ret = find_free_extent(trans, root, num_blocks, empty_size,
1180 search_start, search_end, hint_block, ins,
1181 trans->alloc_exclude_start,
1182 trans->alloc_exclude_nr, data);
1187 /* block accounting for super block */
1188 super_blocks_used = btrfs_super_blocks_used(&info->super_copy);
1189 btrfs_set_super_blocks_used(&info->super_copy, super_blocks_used +
1192 /* block accounting for root item */
1193 root_blocks_used = btrfs_root_used(&root->root_item);
1194 btrfs_set_root_used(&root->root_item, root_blocks_used +
1197 clear_extent_dirty(&root->fs_info->free_space_cache,
1198 ins->objectid, ins->objectid + ins->offset - 1,
1201 if (root == extent_root) {
1202 BUG_ON(num_blocks != 1);
1203 set_radix_bit(&root->fs_info->extent_ins_radix, ins->objectid);
1207 WARN_ON(trans->alloc_exclude_nr);
1208 trans->alloc_exclude_start = ins->objectid;
1209 trans->alloc_exclude_nr = ins->offset;
1210 ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
1211 sizeof(extent_item));
1213 trans->alloc_exclude_start = 0;
1214 trans->alloc_exclude_nr = 0;
1217 finish_current_insert(trans, extent_root);
1218 pending_ret = del_pending_extents(trans, extent_root);
1228 ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0,
1235 * helper function to allocate a block for a given tree
1236 * returns the tree buffer or NULL.
1238 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1239 struct btrfs_root *root, u64 hint,
1242 struct btrfs_key ins;
1244 struct extent_buffer *buf;
1246 ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
1247 1, empty_size, hint, (u64)-1, &ins, 0);
1250 return ERR_PTR(ret);
1252 buf = btrfs_find_create_tree_block(root, ins.objectid);
1254 btrfs_free_extent(trans, root, ins.objectid, 1, 0);
1255 return ERR_PTR(-ENOMEM);
1257 btrfs_set_buffer_uptodate(buf);
1258 buf->alloc_addr = (unsigned long)__builtin_return_address(0);
1259 set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
1260 buf->start + buf->len - 1, GFP_NOFS);
1262 set_buffer_checked(buf);
1263 set_buffer_defrag(buf);
1265 /* FIXME!!!!!!!!!!!!!!!!
1266 set_radix_bit(&trans->transaction->dirty_pages, buf->pages[0]->index);
1268 trans->blocks_used++;
1272 static int drop_leaf_ref(struct btrfs_trans_handle *trans,
1273 struct btrfs_root *root, struct extent_buffer *leaf)
1275 struct btrfs_key key;
1276 struct btrfs_file_extent_item *fi;
1281 BUG_ON(!btrfs_is_leaf(leaf));
1282 nritems = btrfs_header_nritems(leaf);
1283 for (i = 0; i < nritems; i++) {
1286 btrfs_item_key_to_cpu(leaf, &key, i);
1287 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1289 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1290 if (btrfs_file_extent_type(leaf, fi) ==
1291 BTRFS_FILE_EXTENT_INLINE)
1294 * FIXME make sure to insert a trans record that
1295 * repeats the snapshot del on crash
1297 disk_blocknr = btrfs_file_extent_disk_blocknr(leaf, fi);
1298 if (disk_blocknr == 0)
1300 ret = btrfs_free_extent(trans, root, disk_blocknr,
1301 btrfs_file_extent_disk_num_blocks(leaf, fi), 0);
1307 static void reada_walk_down(struct btrfs_root *root,
1308 struct extent_buffer *node)
1316 nritems = btrfs_header_nritems(node);
1317 for (i = 0; i < nritems; i++) {
1318 blocknr = btrfs_node_blockptr(node, i);
1319 ret = lookup_extent_ref(NULL, root, blocknr, 1, &refs);
1323 mutex_unlock(&root->fs_info->fs_mutex);
1324 ret = readahead_tree_block(root, blocknr);
1326 mutex_lock(&root->fs_info->fs_mutex);
1333 * helper function for drop_snapshot, this walks down the tree dropping ref
1334 * counts as it goes.
1336 static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
1337 *root, struct btrfs_path *path, int *level)
1339 struct extent_buffer *next;
1340 struct extent_buffer *cur;
1345 WARN_ON(*level < 0);
1346 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1347 ret = lookup_extent_ref(trans, root,
1348 extent_buffer_blocknr(path->nodes[*level]),
1355 * walk down to the last node level and free all the leaves
1357 while(*level >= 0) {
1358 WARN_ON(*level < 0);
1359 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1360 cur = path->nodes[*level];
1362 if (*level > 0 && path->slots[*level] == 0)
1363 reada_walk_down(root, cur);
1365 if (btrfs_header_level(cur) != *level)
1368 if (path->slots[*level] >=
1369 btrfs_header_nritems(cur))
1372 ret = drop_leaf_ref(trans, root, cur);
1376 blocknr = btrfs_node_blockptr(cur, path->slots[*level]);
1377 ret = lookup_extent_ref(trans, root, blocknr, 1, &refs);
1380 path->slots[*level]++;
1381 ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
1385 next = btrfs_find_tree_block(root, blocknr);
1386 if (!next || !btrfs_buffer_uptodate(next)) {
1387 free_extent_buffer(next);
1388 mutex_unlock(&root->fs_info->fs_mutex);
1389 next = read_tree_block(root, blocknr);
1390 mutex_lock(&root->fs_info->fs_mutex);
1392 /* we dropped the lock, check one more time */
1393 ret = lookup_extent_ref(trans, root, blocknr, 1, &refs);
1396 path->slots[*level]++;
1397 free_extent_buffer(next);
1398 ret = btrfs_free_extent(trans, root,
1404 WARN_ON(*level <= 0);
1405 if (path->nodes[*level-1])
1406 free_extent_buffer(path->nodes[*level-1]);
1407 path->nodes[*level-1] = next;
1408 *level = btrfs_header_level(next);
1409 path->slots[*level] = 0;
1412 WARN_ON(*level < 0);
1413 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1414 ret = btrfs_free_extent(trans, root,
1415 extent_buffer_blocknr(path->nodes[*level]), 1, 1);
1416 free_extent_buffer(path->nodes[*level]);
1417 path->nodes[*level] = NULL;
1424 * helper for dropping snapshots. This walks back up the tree in the path
1425 * to find the first node higher up where we haven't yet gone through
1428 static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
1429 *root, struct btrfs_path *path, int *level)
1434 struct btrfs_root_item *root_item = &root->root_item;
1436 for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1437 slot = path->slots[i];
1438 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
1439 struct extent_buffer *node;
1440 struct btrfs_disk_key disk_key;
1441 node = path->nodes[i];
1444 WARN_ON(*level == 0);
1445 btrfs_node_key(node, &disk_key, path->slots[i]);
1446 memcpy(&root_item->drop_progress,
1447 &disk_key, sizeof(disk_key));
1448 root_item->drop_level = i;
1451 ret = btrfs_free_extent(trans, root,
1452 extent_buffer_blocknr(path->nodes[*level]),
1455 free_extent_buffer(path->nodes[*level]);
1456 path->nodes[*level] = NULL;
1464 * drop the reference count on the tree rooted at 'snap'. This traverses
1465 * the tree freeing any blocks that have a ref count of zero after being
1468 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
1474 struct btrfs_path *path;
1477 struct btrfs_root_item *root_item = &root->root_item;
1479 path = btrfs_alloc_path();
1482 level = btrfs_header_level(root->node);
1484 if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
1485 path->nodes[level] = root->node;
1486 extent_buffer_get(root->node);
1487 path->slots[level] = 0;
1489 struct btrfs_key key;
1490 struct btrfs_disk_key found_key;
1491 struct extent_buffer *node;
1493 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1494 level = root_item->drop_level;
1495 path->lowest_level = level;
1496 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1501 node = path->nodes[level];
1502 btrfs_node_key(node, &found_key, path->slots[level]);
1503 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
1504 sizeof(found_key)));
1507 wret = walk_down_tree(trans, root, path, &level);
1513 wret = walk_up_tree(trans, root, path, &level);
1521 for (i = 0; i <= orig_level; i++) {
1522 if (path->nodes[i]) {
1523 free_extent_buffer(path->nodes[i]);
1528 btrfs_free_path(path);
1532 static int free_block_group_radix(struct radix_tree_root *radix)
1535 struct btrfs_block_group_cache *cache[8];
1539 ret = radix_tree_gang_lookup(radix, (void **)cache, 0,
1543 for (i = 0; i < ret; i++) {
1544 radix_tree_delete(radix, cache[i]->key.objectid +
1545 cache[i]->key.offset - 1);
1552 int btrfs_free_block_groups(struct btrfs_fs_info *info)
1559 ret = free_block_group_radix(&info->block_group_radix);
1560 ret2 = free_block_group_radix(&info->block_group_data_radix);
1567 ret = find_first_extent_bit(&info->free_space_cache, 0,
1568 &start, &end, EXTENT_DIRTY);
1571 clear_extent_dirty(&info->free_space_cache, start,
1577 int btrfs_read_block_groups(struct btrfs_root *root)
1579 struct btrfs_path *path;
1582 struct btrfs_block_group_cache *cache;
1583 struct btrfs_fs_info *info = root->fs_info;
1584 struct radix_tree_root *radix;
1585 struct btrfs_key key;
1586 struct btrfs_key found_key;
1587 struct extent_buffer *leaf;
1588 u64 group_size_blocks;
1591 group_size_blocks = BTRFS_BLOCK_GROUP_SIZE >>
1592 root->fs_info->sb->s_blocksize_bits;
1593 root = info->extent_root;
1595 key.offset = group_size_blocks;
1596 btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
1598 path = btrfs_alloc_path();
1603 ret = btrfs_search_slot(NULL, info->extent_root,
1609 leaf = path->nodes[0];
1610 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
1611 cache = kmalloc(sizeof(*cache), GFP_NOFS);
1617 read_extent_buffer(leaf, &cache->item,
1618 btrfs_item_ptr_offset(leaf, path->slots[0]),
1619 sizeof(cache->item));
1620 if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
1621 radix = &info->block_group_data_radix;
1624 radix = &info->block_group_radix;
1628 memcpy(&cache->key, &found_key, sizeof(found_key));
1629 cache->last_alloc = cache->key.objectid;
1630 cache->first_free = cache->key.objectid;
1634 cache->radix = radix;
1636 key.objectid = found_key.objectid + found_key.offset;
1637 btrfs_release_path(root, path);
1639 ret = radix_tree_insert(radix, found_key.objectid +
1640 found_key.offset - 1,
1643 used = btrfs_block_group_used(&cache->item);
1644 if (used < div_factor(key.offset, 8)) {
1645 radix_tree_tag_set(radix, found_key.objectid +
1646 found_key.offset - 1,
1647 BTRFS_BLOCK_GROUP_AVAIL);
1650 btrfs_super_total_blocks(&info->super_copy))
1654 btrfs_free_path(path);