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 *)(unsigned long)ptr;
153 if (block_group->key.objectid <= bytenr && bytenr <
154 block_group->key.objectid + block_group->key.offset)
158 static u64 find_search_start(struct btrfs_root *root,
159 struct btrfs_block_group_cache **cache_ret,
160 u64 search_start, int num,
161 int data, int full_scan)
164 struct btrfs_block_group_cache *cache = *cache_ret;
172 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);
187 start = max(last, start);
189 if (last - start < num) {
190 if (last == cache->key.objectid + cache->key.offset)
194 if (data != BTRFS_BLOCK_GROUP_MIXED &&
195 start + num > cache->key.objectid + cache->key.offset)
203 last = cache->key.objectid + cache->key.offset;
205 cache = btrfs_lookup_block_group(root->fs_info, last);
210 data = BTRFS_BLOCK_GROUP_MIXED;
215 if (cache_miss && !cache->cached) {
216 cache_block_group(root, cache);
218 cache = btrfs_lookup_block_group(root->fs_info, last);
221 cache = btrfs_find_block_group(root, cache, last, data, 0);
227 static u64 div_factor(u64 num, int factor)
236 struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
237 struct btrfs_block_group_cache
238 *hint, u64 search_start,
241 struct btrfs_block_group_cache *cache;
242 struct extent_map_tree *block_group_cache;
243 struct btrfs_block_group_cache *found_group = NULL;
244 struct btrfs_fs_info *info = root->fs_info;
258 block_group_cache = &info->block_group_cache;
263 if (data == BTRFS_BLOCK_GROUP_MIXED) {
264 bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
267 bit = BLOCK_GROUP_DATA;
269 bit = BLOCK_GROUP_METADATA;
272 struct btrfs_block_group_cache *shint;
273 shint = btrfs_lookup_block_group(info, search_start);
274 if (shint && (shint->data == data ||
275 shint->data == BTRFS_BLOCK_GROUP_MIXED)) {
276 used = btrfs_block_group_used(&shint->item);
277 if (used + shint->pinned <
278 div_factor(shint->key.offset, factor)) {
283 if (hint && (hint->data == data ||
284 hint->data == BTRFS_BLOCK_GROUP_MIXED)) {
285 used = btrfs_block_group_used(&hint->item);
286 if (used + hint->pinned <
287 div_factor(hint->key.offset, factor)) {
290 last = hint->key.objectid + hint->key.offset;
294 hint_last = max(hint->key.objectid, search_start);
296 hint_last = search_start;
302 ret = find_first_extent_bit(block_group_cache, last,
307 ret = get_state_private(block_group_cache, start, &ptr);
311 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
312 last = cache->key.objectid + cache->key.offset;
313 used = btrfs_block_group_used(&cache->item);
316 free_check = cache->key.offset;
318 free_check = div_factor(cache->key.offset, factor);
319 if (used + cache->pinned < free_check) {
332 bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
340 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
341 struct btrfs_root *root,
342 u64 bytenr, u64 num_bytes)
344 struct btrfs_path *path;
346 struct btrfs_key key;
347 struct extent_buffer *l;
348 struct btrfs_extent_item *item;
351 WARN_ON(num_bytes < root->sectorsize);
352 path = btrfs_alloc_path();
356 key.objectid = bytenr;
357 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
358 key.offset = num_bytes;
359 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
368 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
369 refs = btrfs_extent_refs(l, item);
370 btrfs_set_extent_refs(l, item, refs + 1);
371 btrfs_mark_buffer_dirty(path->nodes[0]);
373 btrfs_release_path(root->fs_info->extent_root, path);
374 btrfs_free_path(path);
375 finish_current_insert(trans, root->fs_info->extent_root);
376 del_pending_extents(trans, root->fs_info->extent_root);
380 int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
381 struct btrfs_root *root)
383 finish_current_insert(trans, root->fs_info->extent_root);
384 del_pending_extents(trans, root->fs_info->extent_root);
388 static int lookup_extent_ref(struct btrfs_trans_handle *trans,
389 struct btrfs_root *root, u64 bytenr,
390 u64 num_bytes, u32 *refs)
392 struct btrfs_path *path;
394 struct btrfs_key key;
395 struct extent_buffer *l;
396 struct btrfs_extent_item *item;
398 WARN_ON(num_bytes < root->sectorsize);
399 path = btrfs_alloc_path();
400 key.objectid = bytenr;
401 key.offset = num_bytes;
402 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
403 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
408 btrfs_print_leaf(root, path->nodes[0]);
409 printk("failed to find block number %Lu\n", bytenr);
413 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
414 *refs = btrfs_extent_refs(l, item);
416 btrfs_free_path(path);
420 int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
421 struct btrfs_root *root)
423 return btrfs_inc_extent_ref(trans, root, root->node->start,
427 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
428 struct extent_buffer *buf)
432 struct btrfs_key key;
433 struct btrfs_file_extent_item *fi;
443 level = btrfs_header_level(buf);
444 nritems = btrfs_header_nritems(buf);
445 for (i = 0; i < nritems; i++) {
448 btrfs_item_key_to_cpu(buf, &key, i);
449 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
451 fi = btrfs_item_ptr(buf, i,
452 struct btrfs_file_extent_item);
453 if (btrfs_file_extent_type(buf, fi) ==
454 BTRFS_FILE_EXTENT_INLINE)
456 disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
457 if (disk_bytenr == 0)
459 ret = btrfs_inc_extent_ref(trans, root, disk_bytenr,
460 btrfs_file_extent_disk_num_bytes(buf, fi));
466 bytenr = btrfs_node_blockptr(buf, i);
467 ret = btrfs_inc_extent_ref(trans, root, bytenr,
468 btrfs_level_size(root, level - 1));
478 for (i =0; i < faili; i++) {
481 btrfs_item_key_to_cpu(buf, &key, i);
482 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
484 fi = btrfs_item_ptr(buf, i,
485 struct btrfs_file_extent_item);
486 if (btrfs_file_extent_type(buf, fi) ==
487 BTRFS_FILE_EXTENT_INLINE)
489 disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
490 if (disk_bytenr == 0)
492 err = btrfs_free_extent(trans, root, disk_bytenr,
493 btrfs_file_extent_disk_num_bytes(buf,
497 bytenr = btrfs_node_blockptr(buf, i);
498 err = btrfs_free_extent(trans, root, bytenr,
499 btrfs_level_size(root, level - 1), 0);
506 static int write_one_cache_group(struct btrfs_trans_handle *trans,
507 struct btrfs_root *root,
508 struct btrfs_path *path,
509 struct btrfs_block_group_cache *cache)
513 struct btrfs_root *extent_root = root->fs_info->extent_root;
515 struct extent_buffer *leaf;
517 ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
522 leaf = path->nodes[0];
523 bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
524 write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
525 btrfs_mark_buffer_dirty(leaf);
526 btrfs_release_path(extent_root, path);
528 finish_current_insert(trans, extent_root);
529 pending_ret = del_pending_extents(trans, extent_root);
538 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
539 struct btrfs_root *root)
541 struct extent_map_tree *block_group_cache;
542 struct btrfs_block_group_cache *cache;
546 struct btrfs_path *path;
552 block_group_cache = &root->fs_info->block_group_cache;
553 path = btrfs_alloc_path();
558 ret = find_first_extent_bit(block_group_cache, last,
559 &start, &end, BLOCK_GROUP_DIRTY);
564 ret = get_state_private(block_group_cache, start, &ptr);
568 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
569 err = write_one_cache_group(trans, root,
572 * if we fail to write the cache group, we want
573 * to keep it marked dirty in hopes that a later
580 clear_extent_bits(block_group_cache, start, end,
581 BLOCK_GROUP_DIRTY, GFP_NOFS);
583 btrfs_free_path(path);
587 static int update_block_group(struct btrfs_trans_handle *trans,
588 struct btrfs_root *root,
589 u64 bytenr, u64 num_bytes, int alloc,
590 int mark_free, int data)
592 struct btrfs_block_group_cache *cache;
593 struct btrfs_fs_info *info = root->fs_info;
594 u64 total = num_bytes;
601 cache = btrfs_lookup_block_group(info, bytenr);
605 byte_in_group = bytenr - cache->key.objectid;
606 WARN_ON(byte_in_group > cache->key.offset);
607 start = cache->key.objectid;
608 end = start + cache->key.offset - 1;
609 set_extent_bits(&info->block_group_cache, start, end,
610 BLOCK_GROUP_DIRTY, GFP_NOFS);
612 old_val = btrfs_block_group_used(&cache->item);
613 num_bytes = min(total, cache->key.offset - byte_in_group);
615 if (cache->data != data &&
616 old_val < (cache->key.offset >> 1)) {
621 bit_to_clear = BLOCK_GROUP_METADATA;
622 bit_to_set = BLOCK_GROUP_DATA;
624 ~BTRFS_BLOCK_GROUP_MIXED;
626 BTRFS_BLOCK_GROUP_DATA;
628 bit_to_clear = BLOCK_GROUP_DATA;
629 bit_to_set = BLOCK_GROUP_METADATA;
631 ~BTRFS_BLOCK_GROUP_MIXED;
633 ~BTRFS_BLOCK_GROUP_DATA;
635 clear_extent_bits(&info->block_group_cache,
636 start, end, bit_to_clear,
638 set_extent_bits(&info->block_group_cache,
639 start, end, bit_to_set,
641 } else if (cache->data != data &&
642 cache->data != BTRFS_BLOCK_GROUP_MIXED) {
643 cache->data = BTRFS_BLOCK_GROUP_MIXED;
644 set_extent_bits(&info->block_group_cache,
647 BLOCK_GROUP_METADATA,
650 old_val += num_bytes;
652 old_val -= num_bytes;
654 set_extent_dirty(&info->free_space_cache,
655 bytenr, bytenr + num_bytes - 1,
659 btrfs_set_block_group_used(&cache->item, old_val);
665 static int update_pinned_extents(struct btrfs_root *root,
666 u64 bytenr, u64 num, int pin)
669 struct btrfs_block_group_cache *cache;
670 struct btrfs_fs_info *fs_info = root->fs_info;
673 set_extent_dirty(&fs_info->pinned_extents,
674 bytenr, bytenr + num - 1, GFP_NOFS);
676 clear_extent_dirty(&fs_info->pinned_extents,
677 bytenr, bytenr + num - 1, GFP_NOFS);
680 cache = btrfs_lookup_block_group(fs_info, bytenr);
682 len = min(num, cache->key.offset -
683 (bytenr - cache->key.objectid));
685 cache->pinned += len;
686 fs_info->total_pinned += len;
688 cache->pinned -= len;
689 fs_info->total_pinned -= len;
697 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_map_tree *copy)
702 struct extent_map_tree *pinned_extents = &root->fs_info->pinned_extents;
706 ret = find_first_extent_bit(pinned_extents, last,
707 &start, &end, EXTENT_DIRTY);
710 set_extent_dirty(copy, start, end, GFP_NOFS);
716 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
717 struct btrfs_root *root,
718 struct extent_map_tree *unpin)
723 struct extent_map_tree *free_space_cache;
724 free_space_cache = &root->fs_info->free_space_cache;
727 ret = find_first_extent_bit(unpin, 0, &start, &end,
731 update_pinned_extents(root, start, end + 1 - start, 0);
732 clear_extent_dirty(unpin, start, end, GFP_NOFS);
733 set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
738 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
739 btrfs_root *extent_root)
741 struct btrfs_key ins;
742 struct btrfs_extent_item extent_item;
747 struct btrfs_fs_info *info = extent_root->fs_info;
749 btrfs_set_stack_extent_refs(&extent_item, 1);
750 btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
751 btrfs_set_stack_extent_owner(&extent_item,
752 extent_root->root_key.objectid);
755 ret = find_first_extent_bit(&info->extent_ins, 0, &start,
756 &end, EXTENT_LOCKED);
760 ins.objectid = start;
761 ins.offset = end + 1 - start;
762 err = btrfs_insert_item(trans, extent_root, &ins,
763 &extent_item, sizeof(extent_item));
764 clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
770 static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
774 struct extent_buffer *buf;
777 buf = btrfs_find_tree_block(root, bytenr, num_bytes);
779 if (btrfs_buffer_uptodate(buf)) {
781 root->fs_info->running_transaction->transid;
782 if (btrfs_header_generation(buf) == transid) {
783 free_extent_buffer(buf);
787 free_extent_buffer(buf);
789 update_pinned_extents(root, bytenr, num_bytes, 1);
791 set_extent_bits(&root->fs_info->pending_del,
792 bytenr, bytenr + num_bytes - 1,
793 EXTENT_LOCKED, GFP_NOFS);
800 * remove an extent from the root, returns 0 on success
802 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
803 *root, u64 bytenr, u64 num_bytes, int pin,
806 struct btrfs_path *path;
807 struct btrfs_key key;
808 struct btrfs_fs_info *info = root->fs_info;
809 struct btrfs_root *extent_root = info->extent_root;
810 struct extent_buffer *leaf;
812 struct btrfs_extent_item *ei;
815 key.objectid = bytenr;
816 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
817 key.offset = num_bytes;
819 path = btrfs_alloc_path();
823 ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
828 leaf = path->nodes[0];
829 ei = btrfs_item_ptr(leaf, path->slots[0],
830 struct btrfs_extent_item);
831 refs = btrfs_extent_refs(leaf, ei);
834 btrfs_set_extent_refs(leaf, ei, refs);
835 btrfs_mark_buffer_dirty(leaf);
842 ret = pin_down_bytes(root, bytenr, num_bytes, 0);
848 /* block accounting for super block */
849 super_used = btrfs_super_bytes_used(&info->super_copy);
850 btrfs_set_super_bytes_used(&info->super_copy,
851 super_used - num_bytes);
853 /* block accounting for root item */
854 root_used = btrfs_root_used(&root->root_item);
855 btrfs_set_root_used(&root->root_item,
856 root_used - num_bytes);
858 ret = btrfs_del_item(trans, extent_root, path);
862 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
866 btrfs_free_path(path);
867 finish_current_insert(trans, extent_root);
872 * find all the blocks marked as pending in the radix tree and remove
873 * them from the extent map
875 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
876 btrfs_root *extent_root)
882 struct extent_map_tree *pending_del;
883 struct extent_map_tree *pinned_extents;
885 pending_del = &extent_root->fs_info->pending_del;
886 pinned_extents = &extent_root->fs_info->pinned_extents;
889 ret = find_first_extent_bit(pending_del, 0, &start, &end,
893 update_pinned_extents(extent_root, start, end + 1 - start, 1);
894 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
896 ret = __free_extent(trans, extent_root,
897 start, end + 1 - start, 0, 0);
905 * remove an extent from the root, returns 0 on success
907 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
908 *root, u64 bytenr, u64 num_bytes, int pin)
910 struct btrfs_root *extent_root = root->fs_info->extent_root;
914 WARN_ON(num_bytes < root->sectorsize);
915 if (root == extent_root) {
916 pin_down_bytes(root, bytenr, num_bytes, 1);
919 ret = __free_extent(trans, root, bytenr, num_bytes, pin, pin == 0);
920 pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
921 return ret ? ret : pending_ret;
925 * walks the btree of allocated extents and find a hole of a given size.
926 * The key ins is changed to record the hole:
927 * ins->objectid == block start
928 * ins->flags = BTRFS_EXTENT_ITEM_KEY
929 * ins->offset == number of blocks
930 * Any available blocks before search_start are skipped.
932 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
933 *orig_root, u64 num_bytes, u64 empty_size,
934 u64 search_start, u64 search_end, u64 hint_byte,
935 struct btrfs_key *ins, u64 exclude_start,
936 u64 exclude_nr, int data)
938 struct btrfs_path *path;
939 struct btrfs_key key;
944 u64 orig_search_start = search_start;
946 struct extent_buffer *l;
947 struct btrfs_root * root = orig_root->fs_info->extent_root;
948 struct btrfs_fs_info *info = root->fs_info;
949 u64 total_needed = num_bytes;
951 struct btrfs_block_group_cache *block_group;
956 WARN_ON(num_bytes < root->sectorsize);
957 btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
959 level = btrfs_header_level(root->node);
961 if (num_bytes >= 96 * 1024 * 1024 && hint_byte) {
962 data = BTRFS_BLOCK_GROUP_MIXED;
965 if (search_end == (u64)-1)
966 search_end = btrfs_super_total_bytes(&info->super_copy);
968 block_group = btrfs_lookup_block_group(info, hint_byte);
969 block_group = btrfs_find_block_group(root, block_group,
972 block_group = btrfs_find_block_group(root,
973 trans->block_group, 0,
977 total_needed += empty_size;
978 path = btrfs_alloc_path();
980 search_start = find_search_start(root, &block_group, search_start,
981 total_needed, data, full_scan);
982 cached_start = search_start;
983 btrfs_init_path(path);
984 ins->objectid = search_start;
989 ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
993 if (path->slots[0] > 0) {
998 btrfs_item_key_to_cpu(l, &key, path->slots[0]);
1001 * a rare case, go back one key if we hit a block group item
1002 * instead of an extent item
1004 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY &&
1005 key.objectid + key.offset >= search_start) {
1006 ins->objectid = key.objectid;
1007 ins->offset = key.offset - 1;
1008 btrfs_release_path(root, path);
1009 ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
1013 if (path->slots[0] > 0) {
1020 slot = path->slots[0];
1021 if (slot >= btrfs_header_nritems(l)) {
1022 ret = btrfs_next_leaf(root, path);
1028 search_start = max(search_start,
1029 block_group->key.objectid);
1031 ins->objectid = search_start;
1032 ins->offset = search_end - search_start;
1036 ins->objectid = last_byte > search_start ?
1037 last_byte : search_start;
1038 ins->offset = search_end - ins->objectid;
1039 BUG_ON(ins->objectid >= search_end);
1042 btrfs_item_key_to_cpu(l, &key, slot);
1044 if (key.objectid >= search_start && key.objectid > last_byte &&
1046 if (last_byte < search_start)
1047 last_byte = search_start;
1048 hole_size = key.objectid - last_byte;
1049 if (hole_size >= num_bytes) {
1050 ins->objectid = last_byte;
1051 ins->offset = hole_size;
1055 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY) {
1057 last_byte = key.objectid;
1065 last_byte = key.objectid + key.offset;
1067 if (!full_scan && data != BTRFS_BLOCK_GROUP_MIXED &&
1068 last_byte >= block_group->key.objectid +
1069 block_group->key.offset) {
1070 btrfs_release_path(root, path);
1071 search_start = block_group->key.objectid +
1072 block_group->key.offset;
1080 /* we have to make sure we didn't find an extent that has already
1081 * been allocated by the map tree or the original allocation
1083 btrfs_release_path(root, path);
1084 BUG_ON(ins->objectid < search_start);
1086 if (ins->objectid + num_bytes >= search_end)
1088 if (!full_scan && data != BTRFS_BLOCK_GROUP_MIXED &&
1089 ins->objectid + num_bytes > block_group->
1090 key.objectid + block_group->key.offset) {
1091 search_start = block_group->key.objectid +
1092 block_group->key.offset;
1095 if (test_range_bit(&info->extent_ins, ins->objectid,
1096 ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
1097 search_start = ins->objectid + num_bytes;
1100 if (test_range_bit(&info->pinned_extents, ins->objectid,
1101 ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
1102 search_start = ins->objectid + num_bytes;
1105 if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
1106 ins->objectid < exclude_start + exclude_nr)) {
1107 search_start = exclude_start + exclude_nr;
1111 block_group = btrfs_lookup_block_group(info, ins->objectid);
1113 trans->block_group = block_group;
1115 ins->offset = num_bytes;
1116 btrfs_free_path(path);
1120 if (search_start + num_bytes >= search_end) {
1122 search_start = orig_search_start;
1129 total_needed -= empty_size;
1134 block_group = btrfs_lookup_block_group(info, search_start);
1137 block_group = btrfs_find_block_group(root, block_group,
1138 search_start, data, 0);
1142 btrfs_release_path(root, path);
1143 btrfs_free_path(path);
1147 * finds a free extent and does all the dirty work required for allocation
1148 * returns the key for the extent through ins, and a tree buffer for
1149 * the first block of the extent through buf.
1151 * returns 0 if everything worked, non-zero otherwise.
1153 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
1154 struct btrfs_root *root, u64 owner,
1155 u64 num_bytes, u64 empty_size, u64 hint_byte,
1156 u64 search_end, struct btrfs_key *ins, int data)
1160 u64 super_used, root_used;
1161 u64 search_start = 0;
1162 struct btrfs_fs_info *info = root->fs_info;
1163 struct btrfs_root *extent_root = info->extent_root;
1164 struct btrfs_extent_item extent_item;
1166 btrfs_set_stack_extent_refs(&extent_item, 1);
1167 btrfs_set_stack_extent_owner(&extent_item, owner);
1169 WARN_ON(num_bytes < root->sectorsize);
1170 ret = find_free_extent(trans, root, num_bytes, empty_size,
1171 search_start, search_end, hint_byte, ins,
1172 trans->alloc_exclude_start,
1173 trans->alloc_exclude_nr, data);
1178 /* block accounting for super block */
1179 super_used = btrfs_super_bytes_used(&info->super_copy);
1180 btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
1182 /* block accounting for root item */
1183 root_used = btrfs_root_used(&root->root_item);
1184 btrfs_set_root_used(&root->root_item, root_used + num_bytes);
1186 clear_extent_dirty(&root->fs_info->free_space_cache,
1187 ins->objectid, ins->objectid + ins->offset - 1,
1190 if (root == extent_root) {
1191 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
1192 ins->objectid + ins->offset - 1,
1193 EXTENT_LOCKED, GFP_NOFS);
1198 WARN_ON(trans->alloc_exclude_nr);
1199 trans->alloc_exclude_start = ins->objectid;
1200 trans->alloc_exclude_nr = ins->offset;
1201 ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
1202 sizeof(extent_item));
1204 trans->alloc_exclude_start = 0;
1205 trans->alloc_exclude_nr = 0;
1208 finish_current_insert(trans, extent_root);
1209 pending_ret = del_pending_extents(trans, extent_root);
1219 ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0,
1226 * helper function to allocate a block for a given tree
1227 * returns the tree buffer or NULL.
1229 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1230 struct btrfs_root *root,
1231 u32 blocksize, u64 hint,
1234 struct btrfs_key ins;
1236 struct extent_buffer *buf;
1238 ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
1239 blocksize, empty_size, hint,
1243 return ERR_PTR(ret);
1245 buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
1247 btrfs_free_extent(trans, root, ins.objectid, blocksize, 0);
1248 return ERR_PTR(-ENOMEM);
1250 btrfs_set_buffer_uptodate(buf);
1251 set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
1252 buf->start + buf->len - 1, GFP_NOFS);
1253 set_extent_bits(&BTRFS_I(root->fs_info->btree_inode)->extent_tree,
1254 buf->start, buf->start + buf->len - 1,
1255 EXTENT_CSUM, GFP_NOFS);
1256 buf->flags |= EXTENT_CSUM;
1257 btrfs_set_buffer_defrag(buf);
1258 trans->blocks_used++;
1262 static int drop_leaf_ref(struct btrfs_trans_handle *trans,
1263 struct btrfs_root *root, struct extent_buffer *leaf)
1265 struct btrfs_key key;
1266 struct btrfs_file_extent_item *fi;
1271 BUG_ON(!btrfs_is_leaf(leaf));
1272 nritems = btrfs_header_nritems(leaf);
1273 for (i = 0; i < nritems; i++) {
1276 btrfs_item_key_to_cpu(leaf, &key, i);
1277 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1279 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1280 if (btrfs_file_extent_type(leaf, fi) ==
1281 BTRFS_FILE_EXTENT_INLINE)
1284 * FIXME make sure to insert a trans record that
1285 * repeats the snapshot del on crash
1287 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
1288 if (disk_bytenr == 0)
1290 ret = btrfs_free_extent(trans, root, disk_bytenr,
1291 btrfs_file_extent_disk_num_bytes(leaf, fi), 0);
1297 static void reada_walk_down(struct btrfs_root *root,
1298 struct extent_buffer *node)
1308 nritems = btrfs_header_nritems(node);
1309 level = btrfs_header_level(node);
1310 for (i = 0; i < nritems; i++) {
1311 bytenr = btrfs_node_blockptr(node, i);
1312 blocksize = btrfs_level_size(root, level - 1);
1313 ret = lookup_extent_ref(NULL, root, bytenr, blocksize, &refs);
1317 mutex_unlock(&root->fs_info->fs_mutex);
1318 ret = readahead_tree_block(root, bytenr, blocksize);
1320 mutex_lock(&root->fs_info->fs_mutex);
1327 * helper function for drop_snapshot, this walks down the tree dropping ref
1328 * counts as it goes.
1330 static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
1331 *root, struct btrfs_path *path, int *level)
1333 struct extent_buffer *next;
1334 struct extent_buffer *cur;
1340 WARN_ON(*level < 0);
1341 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1342 ret = lookup_extent_ref(trans, root,
1343 path->nodes[*level]->start,
1344 path->nodes[*level]->len, &refs);
1350 * walk down to the last node level and free all the leaves
1352 while(*level >= 0) {
1353 WARN_ON(*level < 0);
1354 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1355 cur = path->nodes[*level];
1357 if (*level > 0 && path->slots[*level] == 0)
1358 reada_walk_down(root, cur);
1360 if (btrfs_header_level(cur) != *level)
1363 if (path->slots[*level] >=
1364 btrfs_header_nritems(cur))
1367 ret = drop_leaf_ref(trans, root, cur);
1371 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1372 blocksize = btrfs_level_size(root, *level - 1);
1373 ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
1376 path->slots[*level]++;
1377 ret = btrfs_free_extent(trans, root, bytenr,
1382 next = btrfs_find_tree_block(root, bytenr, blocksize);
1383 if (!next || !btrfs_buffer_uptodate(next)) {
1384 free_extent_buffer(next);
1385 mutex_unlock(&root->fs_info->fs_mutex);
1386 next = read_tree_block(root, bytenr, blocksize);
1387 mutex_lock(&root->fs_info->fs_mutex);
1389 /* we dropped the lock, check one more time */
1390 ret = lookup_extent_ref(trans, root, bytenr,
1394 path->slots[*level]++;
1395 free_extent_buffer(next);
1396 ret = btrfs_free_extent(trans, root,
1397 bytenr, blocksize, 1);
1402 WARN_ON(*level <= 0);
1403 if (path->nodes[*level-1])
1404 free_extent_buffer(path->nodes[*level-1]);
1405 path->nodes[*level-1] = next;
1406 *level = btrfs_header_level(next);
1407 path->slots[*level] = 0;
1410 WARN_ON(*level < 0);
1411 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1412 ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
1413 path->nodes[*level]->len, 1);
1414 free_extent_buffer(path->nodes[*level]);
1415 path->nodes[*level] = NULL;
1422 * helper for dropping snapshots. This walks back up the tree in the path
1423 * to find the first node higher up where we haven't yet gone through
1426 static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
1427 *root, struct btrfs_path *path, int *level)
1432 struct btrfs_root_item *root_item = &root->root_item;
1434 for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1435 slot = path->slots[i];
1436 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
1437 struct extent_buffer *node;
1438 struct btrfs_disk_key disk_key;
1439 node = path->nodes[i];
1442 WARN_ON(*level == 0);
1443 btrfs_node_key(node, &disk_key, path->slots[i]);
1444 memcpy(&root_item->drop_progress,
1445 &disk_key, sizeof(disk_key));
1446 root_item->drop_level = i;
1449 ret = btrfs_free_extent(trans, root,
1450 path->nodes[*level]->start,
1451 path->nodes[*level]->len, 1);
1453 free_extent_buffer(path->nodes[*level]);
1454 path->nodes[*level] = NULL;
1462 * drop the reference count on the tree rooted at 'snap'. This traverses
1463 * the tree freeing any blocks that have a ref count of zero after being
1466 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
1472 struct btrfs_path *path;
1475 struct btrfs_root_item *root_item = &root->root_item;
1477 path = btrfs_alloc_path();
1480 level = btrfs_header_level(root->node);
1482 if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
1483 path->nodes[level] = root->node;
1484 extent_buffer_get(root->node);
1485 path->slots[level] = 0;
1487 struct btrfs_key key;
1488 struct btrfs_disk_key found_key;
1489 struct extent_buffer *node;
1491 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1492 level = root_item->drop_level;
1493 path->lowest_level = level;
1494 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1499 node = path->nodes[level];
1500 btrfs_node_key(node, &found_key, path->slots[level]);
1501 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
1502 sizeof(found_key)));
1505 wret = walk_down_tree(trans, root, path, &level);
1511 wret = walk_up_tree(trans, root, path, &level);
1519 for (i = 0; i <= orig_level; i++) {
1520 if (path->nodes[i]) {
1521 free_extent_buffer(path->nodes[i]);
1522 path->nodes[i] = NULL;
1526 btrfs_free_path(path);
1530 int btrfs_free_block_groups(struct btrfs_fs_info *info)
1537 ret = find_first_extent_bit(&info->block_group_cache, 0,
1538 &start, &end, (unsigned int)-1);
1541 ret = get_state_private(&info->block_group_cache, start, &ptr);
1543 kfree((void *)(unsigned long)ptr);
1544 clear_extent_bits(&info->block_group_cache, start,
1545 end, (unsigned int)-1, GFP_NOFS);
1548 ret = find_first_extent_bit(&info->free_space_cache, 0,
1549 &start, &end, EXTENT_DIRTY);
1552 clear_extent_dirty(&info->free_space_cache, start,
1558 int btrfs_read_block_groups(struct btrfs_root *root)
1560 struct btrfs_path *path;
1564 struct btrfs_block_group_cache *cache;
1565 struct btrfs_fs_info *info = root->fs_info;
1566 struct extent_map_tree *block_group_cache;
1567 struct btrfs_key key;
1568 struct btrfs_key found_key;
1569 struct extent_buffer *leaf;
1571 block_group_cache = &info->block_group_cache;
1573 root = info->extent_root;
1575 key.offset = BTRFS_BLOCK_GROUP_SIZE;
1576 btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
1578 path = btrfs_alloc_path();
1583 ret = btrfs_search_slot(NULL, info->extent_root,
1589 leaf = path->nodes[0];
1590 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
1591 cache = kmalloc(sizeof(*cache), GFP_NOFS);
1597 read_extent_buffer(leaf, &cache->item,
1598 btrfs_item_ptr_offset(leaf, path->slots[0]),
1599 sizeof(cache->item));
1600 memcpy(&cache->key, &found_key, sizeof(found_key));
1603 key.objectid = found_key.objectid + found_key.offset;
1604 btrfs_release_path(root, path);
1606 if (cache->item.flags & BTRFS_BLOCK_GROUP_MIXED) {
1607 bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
1608 cache->data = BTRFS_BLOCK_GROUP_MIXED;
1609 } else if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
1610 bit = BLOCK_GROUP_DATA;
1611 cache->data = BTRFS_BLOCK_GROUP_DATA;
1613 bit = BLOCK_GROUP_METADATA;
1617 /* use EXTENT_LOCKED to prevent merging */
1618 set_extent_bits(block_group_cache, found_key.objectid,
1619 found_key.objectid + found_key.offset - 1,
1620 bit | EXTENT_LOCKED, GFP_NOFS);
1621 set_state_private(block_group_cache, found_key.objectid,
1622 (unsigned long)cache);
1625 btrfs_super_total_bytes(&info->super_copy))
1629 btrfs_free_path(path);