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.
18 #include <linux/sched.h>
19 #include <linux/pagemap.h>
20 #include <linux/writeback.h>
21 #include <linux/blkdev.h>
22 #include <linux/sort.h>
23 #include <linux/rcupdate.h>
29 #include "print-tree.h"
30 #include "transaction.h"
33 #include "free-space-cache.h"
35 static int update_reserved_extents(struct btrfs_root *root,
36 u64 bytenr, u64 num, int reserve);
37 static int update_block_group(struct btrfs_trans_handle *trans,
38 struct btrfs_root *root,
39 u64 bytenr, u64 num_bytes, int alloc,
41 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
42 struct btrfs_root *root,
43 u64 bytenr, u64 num_bytes, u64 parent,
44 u64 root_objectid, u64 owner_objectid,
45 u64 owner_offset, int refs_to_drop,
46 struct btrfs_delayed_extent_op *extra_op);
47 static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
48 struct extent_buffer *leaf,
49 struct btrfs_extent_item *ei);
50 static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
51 struct btrfs_root *root,
52 u64 parent, u64 root_objectid,
53 u64 flags, u64 owner, u64 offset,
54 struct btrfs_key *ins, int ref_mod);
55 static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
56 struct btrfs_root *root,
57 u64 parent, u64 root_objectid,
58 u64 flags, struct btrfs_disk_key *key,
59 int level, struct btrfs_key *ins);
61 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
62 struct btrfs_root *extent_root, u64 alloc_bytes,
63 u64 flags, int force);
65 static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
67 return (cache->flags & bits) == bits;
71 * this adds the block group to the fs_info rb tree for the block group
74 static int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
75 struct btrfs_block_group_cache *block_group)
78 struct rb_node *parent = NULL;
79 struct btrfs_block_group_cache *cache;
81 spin_lock(&info->block_group_cache_lock);
82 p = &info->block_group_cache_tree.rb_node;
86 cache = rb_entry(parent, struct btrfs_block_group_cache,
88 if (block_group->key.objectid < cache->key.objectid) {
90 } else if (block_group->key.objectid > cache->key.objectid) {
93 spin_unlock(&info->block_group_cache_lock);
98 rb_link_node(&block_group->cache_node, parent, p);
99 rb_insert_color(&block_group->cache_node,
100 &info->block_group_cache_tree);
101 spin_unlock(&info->block_group_cache_lock);
107 * This will return the block group at or after bytenr if contains is 0, else
108 * it will return the block group that contains the bytenr
110 static struct btrfs_block_group_cache *
111 block_group_cache_tree_search(struct btrfs_fs_info *info, u64 bytenr,
114 struct btrfs_block_group_cache *cache, *ret = NULL;
118 spin_lock(&info->block_group_cache_lock);
119 n = info->block_group_cache_tree.rb_node;
122 cache = rb_entry(n, struct btrfs_block_group_cache,
124 end = cache->key.objectid + cache->key.offset - 1;
125 start = cache->key.objectid;
127 if (bytenr < start) {
128 if (!contains && (!ret || start < ret->key.objectid))
131 } else if (bytenr > start) {
132 if (contains && bytenr <= end) {
143 atomic_inc(&ret->count);
144 spin_unlock(&info->block_group_cache_lock);
150 * this is only called by cache_block_group, since we could have freed extents
151 * we need to check the pinned_extents for any extents that can't be used yet
152 * since their free space will be released as soon as the transaction commits.
154 static int add_new_free_space(struct btrfs_block_group_cache *block_group,
155 struct btrfs_fs_info *info, u64 start, u64 end)
157 u64 extent_start, extent_end, size;
160 while (start < end) {
161 ret = find_first_extent_bit(&info->pinned_extents, start,
162 &extent_start, &extent_end,
167 if (extent_start == start) {
168 start = extent_end + 1;
169 } else if (extent_start > start && extent_start < end) {
170 size = extent_start - start;
171 ret = btrfs_add_free_space(block_group, start,
174 start = extent_end + 1;
182 ret = btrfs_add_free_space(block_group, start, size);
189 static int remove_sb_from_cache(struct btrfs_root *root,
190 struct btrfs_block_group_cache *cache)
197 for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
198 bytenr = btrfs_sb_offset(i);
199 ret = btrfs_rmap_block(&root->fs_info->mapping_tree,
200 cache->key.objectid, bytenr, 0,
201 &logical, &nr, &stripe_len);
204 btrfs_remove_free_space(cache, logical[nr],
212 static int cache_block_group(struct btrfs_root *root,
213 struct btrfs_block_group_cache *block_group)
215 struct btrfs_path *path;
217 struct btrfs_key key;
218 struct extent_buffer *leaf;
225 root = root->fs_info->extent_root;
227 if (block_group->cached)
230 path = btrfs_alloc_path();
236 * we get into deadlocks with paths held by callers of this function.
237 * since the alloc_mutex is protecting things right now, just
238 * skip the locking here
240 path->skip_locking = 1;
241 last = max_t(u64, block_group->key.objectid, BTRFS_SUPER_INFO_OFFSET);
244 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
245 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
250 leaf = path->nodes[0];
251 slot = path->slots[0];
252 if (slot >= btrfs_header_nritems(leaf)) {
253 ret = btrfs_next_leaf(root, path);
261 btrfs_item_key_to_cpu(leaf, &key, slot);
262 if (key.objectid < block_group->key.objectid)
265 if (key.objectid >= block_group->key.objectid +
266 block_group->key.offset)
269 if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
270 add_new_free_space(block_group, root->fs_info, last,
273 last = key.objectid + key.offset;
279 add_new_free_space(block_group, root->fs_info, last,
280 block_group->key.objectid +
281 block_group->key.offset);
283 block_group->cached = 1;
284 remove_sb_from_cache(root, block_group);
287 btrfs_free_path(path);
292 * return the block group that starts at or after bytenr
294 static struct btrfs_block_group_cache *
295 btrfs_lookup_first_block_group(struct btrfs_fs_info *info, u64 bytenr)
297 struct btrfs_block_group_cache *cache;
299 cache = block_group_cache_tree_search(info, bytenr, 0);
305 * return the block group that contains the given bytenr
307 struct btrfs_block_group_cache *btrfs_lookup_block_group(
308 struct btrfs_fs_info *info,
311 struct btrfs_block_group_cache *cache;
313 cache = block_group_cache_tree_search(info, bytenr, 1);
318 void btrfs_put_block_group(struct btrfs_block_group_cache *cache)
320 if (atomic_dec_and_test(&cache->count))
324 static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
327 struct list_head *head = &info->space_info;
328 struct btrfs_space_info *found;
331 list_for_each_entry_rcu(found, head, list) {
332 if (found->flags == flags) {
342 * after adding space to the filesystem, we need to clear the full flags
343 * on all the space infos.
345 void btrfs_clear_space_info_full(struct btrfs_fs_info *info)
347 struct list_head *head = &info->space_info;
348 struct btrfs_space_info *found;
351 list_for_each_entry_rcu(found, head, list)
356 static u64 div_factor(u64 num, int factor)
365 u64 btrfs_find_block_group(struct btrfs_root *root,
366 u64 search_start, u64 search_hint, int owner)
368 struct btrfs_block_group_cache *cache;
370 u64 last = max(search_hint, search_start);
377 cache = btrfs_lookup_first_block_group(root->fs_info, last);
381 spin_lock(&cache->lock);
382 last = cache->key.objectid + cache->key.offset;
383 used = btrfs_block_group_used(&cache->item);
385 if ((full_search || !cache->ro) &&
386 block_group_bits(cache, BTRFS_BLOCK_GROUP_METADATA)) {
387 if (used + cache->pinned + cache->reserved <
388 div_factor(cache->key.offset, factor)) {
389 group_start = cache->key.objectid;
390 spin_unlock(&cache->lock);
391 btrfs_put_block_group(cache);
395 spin_unlock(&cache->lock);
396 btrfs_put_block_group(cache);
404 if (!full_search && factor < 10) {
414 /* simple helper to search for an existing extent at a given offset */
415 int btrfs_lookup_extent(struct btrfs_root *root, u64 start, u64 len)
418 struct btrfs_key key;
419 struct btrfs_path *path;
421 path = btrfs_alloc_path();
423 key.objectid = start;
425 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
426 ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, path,
428 btrfs_free_path(path);
433 * Back reference rules. Back refs have three main goals:
435 * 1) differentiate between all holders of references to an extent so that
436 * when a reference is dropped we can make sure it was a valid reference
437 * before freeing the extent.
439 * 2) Provide enough information to quickly find the holders of an extent
440 * if we notice a given block is corrupted or bad.
442 * 3) Make it easy to migrate blocks for FS shrinking or storage pool
443 * maintenance. This is actually the same as #2, but with a slightly
444 * different use case.
446 * There are two kinds of back refs. The implicit back refs is optimized
447 * for pointers in non-shared tree blocks. For a given pointer in a block,
448 * back refs of this kind provide information about the block's owner tree
449 * and the pointer's key. These information allow us to find the block by
450 * b-tree searching. The full back refs is for pointers in tree blocks not
451 * referenced by their owner trees. The location of tree block is recorded
452 * in the back refs. Actually the full back refs is generic, and can be
453 * used in all cases the implicit back refs is used. The major shortcoming
454 * of the full back refs is its overhead. Every time a tree block gets
455 * COWed, we have to update back refs entry for all pointers in it.
457 * For a newly allocated tree block, we use implicit back refs for
458 * pointers in it. This means most tree related operations only involve
459 * implicit back refs. For a tree block created in old transaction, the
460 * only way to drop a reference to it is COW it. So we can detect the
461 * event that tree block loses its owner tree's reference and do the
462 * back refs conversion.
464 * When a tree block is COW'd through a tree, there are four cases:
466 * The reference count of the block is one and the tree is the block's
467 * owner tree. Nothing to do in this case.
469 * The reference count of the block is one and the tree is not the
470 * block's owner tree. In this case, full back refs is used for pointers
471 * in the block. Remove these full back refs, add implicit back refs for
472 * every pointers in the new block.
474 * The reference count of the block is greater than one and the tree is
475 * the block's owner tree. In this case, implicit back refs is used for
476 * pointers in the block. Add full back refs for every pointers in the
477 * block, increase lower level extents' reference counts. The original
478 * implicit back refs are entailed to the new block.
480 * The reference count of the block is greater than one and the tree is
481 * not the block's owner tree. Add implicit back refs for every pointer in
482 * the new block, increase lower level extents' reference count.
484 * Back Reference Key composing:
486 * The key objectid corresponds to the first byte in the extent,
487 * The key type is used to differentiate between types of back refs.
488 * There are different meanings of the key offset for different types
491 * File extents can be referenced by:
493 * - multiple snapshots, subvolumes, or different generations in one subvol
494 * - different files inside a single subvolume
495 * - different offsets inside a file (bookend extents in file.c)
497 * The extent ref structure for the implicit back refs has fields for:
499 * - Objectid of the subvolume root
500 * - objectid of the file holding the reference
501 * - original offset in the file
502 * - how many bookend extents
504 * The key offset for the implicit back refs is hash of the first
507 * The extent ref structure for the full back refs has field for:
509 * - number of pointers in the tree leaf
511 * The key offset for the implicit back refs is the first byte of
514 * When a file extent is allocated, The implicit back refs is used.
515 * the fields are filled in:
517 * (root_key.objectid, inode objectid, offset in file, 1)
519 * When a file extent is removed file truncation, we find the
520 * corresponding implicit back refs and check the following fields:
522 * (btrfs_header_owner(leaf), inode objectid, offset in file)
524 * Btree extents can be referenced by:
526 * - Different subvolumes
528 * Both the implicit back refs and the full back refs for tree blocks
529 * only consist of key. The key offset for the implicit back refs is
530 * objectid of block's owner tree. The key offset for the full back refs
531 * is the first byte of parent block.
533 * When implicit back refs is used, information about the lowest key and
534 * level of the tree block are required. These information are stored in
535 * tree block info structure.
538 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
539 static int convert_extent_item_v0(struct btrfs_trans_handle *trans,
540 struct btrfs_root *root,
541 struct btrfs_path *path,
542 u64 owner, u32 extra_size)
544 struct btrfs_extent_item *item;
545 struct btrfs_extent_item_v0 *ei0;
546 struct btrfs_extent_ref_v0 *ref0;
547 struct btrfs_tree_block_info *bi;
548 struct extent_buffer *leaf;
549 struct btrfs_key key;
550 struct btrfs_key found_key;
551 u32 new_size = sizeof(*item);
555 leaf = path->nodes[0];
556 BUG_ON(btrfs_item_size_nr(leaf, path->slots[0]) != sizeof(*ei0));
558 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
559 ei0 = btrfs_item_ptr(leaf, path->slots[0],
560 struct btrfs_extent_item_v0);
561 refs = btrfs_extent_refs_v0(leaf, ei0);
563 if (owner == (u64)-1) {
565 if (path->slots[0] >= btrfs_header_nritems(leaf)) {
566 ret = btrfs_next_leaf(root, path);
570 leaf = path->nodes[0];
572 btrfs_item_key_to_cpu(leaf, &found_key,
574 BUG_ON(key.objectid != found_key.objectid);
575 if (found_key.type != BTRFS_EXTENT_REF_V0_KEY) {
579 ref0 = btrfs_item_ptr(leaf, path->slots[0],
580 struct btrfs_extent_ref_v0);
581 owner = btrfs_ref_objectid_v0(leaf, ref0);
585 btrfs_release_path(root, path);
587 if (owner < BTRFS_FIRST_FREE_OBJECTID)
588 new_size += sizeof(*bi);
590 new_size -= sizeof(*ei0);
591 ret = btrfs_search_slot(trans, root, &key, path,
592 new_size + extra_size, 1);
597 ret = btrfs_extend_item(trans, root, path, new_size);
600 leaf = path->nodes[0];
601 item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
602 btrfs_set_extent_refs(leaf, item, refs);
603 /* FIXME: get real generation */
604 btrfs_set_extent_generation(leaf, item, 0);
605 if (owner < BTRFS_FIRST_FREE_OBJECTID) {
606 btrfs_set_extent_flags(leaf, item,
607 BTRFS_EXTENT_FLAG_TREE_BLOCK |
608 BTRFS_BLOCK_FLAG_FULL_BACKREF);
609 bi = (struct btrfs_tree_block_info *)(item + 1);
610 /* FIXME: get first key of the block */
611 memset_extent_buffer(leaf, 0, (unsigned long)bi, sizeof(*bi));
612 btrfs_set_tree_block_level(leaf, bi, (int)owner);
614 btrfs_set_extent_flags(leaf, item, BTRFS_EXTENT_FLAG_DATA);
616 btrfs_mark_buffer_dirty(leaf);
621 static u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
623 u32 high_crc = ~(u32)0;
624 u32 low_crc = ~(u32)0;
627 lenum = cpu_to_le64(root_objectid);
628 high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
629 lenum = cpu_to_le64(owner);
630 low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
631 lenum = cpu_to_le64(offset);
632 low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
634 return ((u64)high_crc << 31) ^ (u64)low_crc;
637 static u64 hash_extent_data_ref_item(struct extent_buffer *leaf,
638 struct btrfs_extent_data_ref *ref)
640 return hash_extent_data_ref(btrfs_extent_data_ref_root(leaf, ref),
641 btrfs_extent_data_ref_objectid(leaf, ref),
642 btrfs_extent_data_ref_offset(leaf, ref));
645 static int match_extent_data_ref(struct extent_buffer *leaf,
646 struct btrfs_extent_data_ref *ref,
647 u64 root_objectid, u64 owner, u64 offset)
649 if (btrfs_extent_data_ref_root(leaf, ref) != root_objectid ||
650 btrfs_extent_data_ref_objectid(leaf, ref) != owner ||
651 btrfs_extent_data_ref_offset(leaf, ref) != offset)
656 static noinline int lookup_extent_data_ref(struct btrfs_trans_handle *trans,
657 struct btrfs_root *root,
658 struct btrfs_path *path,
659 u64 bytenr, u64 parent,
661 u64 owner, u64 offset)
663 struct btrfs_key key;
664 struct btrfs_extent_data_ref *ref;
665 struct extent_buffer *leaf;
671 key.objectid = bytenr;
673 key.type = BTRFS_SHARED_DATA_REF_KEY;
676 key.type = BTRFS_EXTENT_DATA_REF_KEY;
677 key.offset = hash_extent_data_ref(root_objectid,
682 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
691 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
692 key.type = BTRFS_EXTENT_REF_V0_KEY;
693 btrfs_release_path(root, path);
694 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
705 leaf = path->nodes[0];
706 nritems = btrfs_header_nritems(leaf);
708 if (path->slots[0] >= nritems) {
709 ret = btrfs_next_leaf(root, path);
715 leaf = path->nodes[0];
716 nritems = btrfs_header_nritems(leaf);
720 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
721 if (key.objectid != bytenr ||
722 key.type != BTRFS_EXTENT_DATA_REF_KEY)
725 ref = btrfs_item_ptr(leaf, path->slots[0],
726 struct btrfs_extent_data_ref);
728 if (match_extent_data_ref(leaf, ref, root_objectid,
731 btrfs_release_path(root, path);
743 static noinline int insert_extent_data_ref(struct btrfs_trans_handle *trans,
744 struct btrfs_root *root,
745 struct btrfs_path *path,
746 u64 bytenr, u64 parent,
747 u64 root_objectid, u64 owner,
748 u64 offset, int refs_to_add)
750 struct btrfs_key key;
751 struct extent_buffer *leaf;
756 key.objectid = bytenr;
758 key.type = BTRFS_SHARED_DATA_REF_KEY;
760 size = sizeof(struct btrfs_shared_data_ref);
762 key.type = BTRFS_EXTENT_DATA_REF_KEY;
763 key.offset = hash_extent_data_ref(root_objectid,
765 size = sizeof(struct btrfs_extent_data_ref);
768 ret = btrfs_insert_empty_item(trans, root, path, &key, size);
769 if (ret && ret != -EEXIST)
772 leaf = path->nodes[0];
774 struct btrfs_shared_data_ref *ref;
775 ref = btrfs_item_ptr(leaf, path->slots[0],
776 struct btrfs_shared_data_ref);
778 btrfs_set_shared_data_ref_count(leaf, ref, refs_to_add);
780 num_refs = btrfs_shared_data_ref_count(leaf, ref);
781 num_refs += refs_to_add;
782 btrfs_set_shared_data_ref_count(leaf, ref, num_refs);
785 struct btrfs_extent_data_ref *ref;
786 while (ret == -EEXIST) {
787 ref = btrfs_item_ptr(leaf, path->slots[0],
788 struct btrfs_extent_data_ref);
789 if (match_extent_data_ref(leaf, ref, root_objectid,
792 btrfs_release_path(root, path);
794 ret = btrfs_insert_empty_item(trans, root, path, &key,
796 if (ret && ret != -EEXIST)
799 leaf = path->nodes[0];
801 ref = btrfs_item_ptr(leaf, path->slots[0],
802 struct btrfs_extent_data_ref);
804 btrfs_set_extent_data_ref_root(leaf, ref,
806 btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
807 btrfs_set_extent_data_ref_offset(leaf, ref, offset);
808 btrfs_set_extent_data_ref_count(leaf, ref, refs_to_add);
810 num_refs = btrfs_extent_data_ref_count(leaf, ref);
811 num_refs += refs_to_add;
812 btrfs_set_extent_data_ref_count(leaf, ref, num_refs);
815 btrfs_mark_buffer_dirty(leaf);
818 btrfs_release_path(root, path);
822 static noinline int remove_extent_data_ref(struct btrfs_trans_handle *trans,
823 struct btrfs_root *root,
824 struct btrfs_path *path,
827 struct btrfs_key key;
828 struct btrfs_extent_data_ref *ref1 = NULL;
829 struct btrfs_shared_data_ref *ref2 = NULL;
830 struct extent_buffer *leaf;
834 leaf = path->nodes[0];
835 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
837 if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
838 ref1 = btrfs_item_ptr(leaf, path->slots[0],
839 struct btrfs_extent_data_ref);
840 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
841 } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
842 ref2 = btrfs_item_ptr(leaf, path->slots[0],
843 struct btrfs_shared_data_ref);
844 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
845 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
846 } else if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
847 struct btrfs_extent_ref_v0 *ref0;
848 ref0 = btrfs_item_ptr(leaf, path->slots[0],
849 struct btrfs_extent_ref_v0);
850 num_refs = btrfs_ref_count_v0(leaf, ref0);
856 BUG_ON(num_refs < refs_to_drop);
857 num_refs -= refs_to_drop;
860 ret = btrfs_del_item(trans, root, path);
862 if (key.type == BTRFS_EXTENT_DATA_REF_KEY)
863 btrfs_set_extent_data_ref_count(leaf, ref1, num_refs);
864 else if (key.type == BTRFS_SHARED_DATA_REF_KEY)
865 btrfs_set_shared_data_ref_count(leaf, ref2, num_refs);
866 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
868 struct btrfs_extent_ref_v0 *ref0;
869 ref0 = btrfs_item_ptr(leaf, path->slots[0],
870 struct btrfs_extent_ref_v0);
871 btrfs_set_ref_count_v0(leaf, ref0, num_refs);
874 btrfs_mark_buffer_dirty(leaf);
879 static noinline u32 extent_data_ref_count(struct btrfs_root *root,
880 struct btrfs_path *path,
881 struct btrfs_extent_inline_ref *iref)
883 struct btrfs_key key;
884 struct extent_buffer *leaf;
885 struct btrfs_extent_data_ref *ref1;
886 struct btrfs_shared_data_ref *ref2;
889 leaf = path->nodes[0];
890 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
892 if (btrfs_extent_inline_ref_type(leaf, iref) ==
893 BTRFS_EXTENT_DATA_REF_KEY) {
894 ref1 = (struct btrfs_extent_data_ref *)(&iref->offset);
895 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
897 ref2 = (struct btrfs_shared_data_ref *)(iref + 1);
898 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
900 } else if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
901 ref1 = btrfs_item_ptr(leaf, path->slots[0],
902 struct btrfs_extent_data_ref);
903 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
904 } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
905 ref2 = btrfs_item_ptr(leaf, path->slots[0],
906 struct btrfs_shared_data_ref);
907 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
908 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
909 } else if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
910 struct btrfs_extent_ref_v0 *ref0;
911 ref0 = btrfs_item_ptr(leaf, path->slots[0],
912 struct btrfs_extent_ref_v0);
913 num_refs = btrfs_ref_count_v0(leaf, ref0);
921 static noinline int lookup_tree_block_ref(struct btrfs_trans_handle *trans,
922 struct btrfs_root *root,
923 struct btrfs_path *path,
924 u64 bytenr, u64 parent,
927 struct btrfs_key key;
930 key.objectid = bytenr;
932 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
935 key.type = BTRFS_TREE_BLOCK_REF_KEY;
936 key.offset = root_objectid;
939 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
942 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
943 if (ret == -ENOENT && parent) {
944 btrfs_release_path(root, path);
945 key.type = BTRFS_EXTENT_REF_V0_KEY;
946 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
954 static noinline int insert_tree_block_ref(struct btrfs_trans_handle *trans,
955 struct btrfs_root *root,
956 struct btrfs_path *path,
957 u64 bytenr, u64 parent,
960 struct btrfs_key key;
963 key.objectid = bytenr;
965 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
968 key.type = BTRFS_TREE_BLOCK_REF_KEY;
969 key.offset = root_objectid;
972 ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
973 btrfs_release_path(root, path);
977 static inline int extent_ref_type(u64 parent, u64 owner)
980 if (owner < BTRFS_FIRST_FREE_OBJECTID) {
982 type = BTRFS_SHARED_BLOCK_REF_KEY;
984 type = BTRFS_TREE_BLOCK_REF_KEY;
987 type = BTRFS_SHARED_DATA_REF_KEY;
989 type = BTRFS_EXTENT_DATA_REF_KEY;
994 static int find_next_key(struct btrfs_path *path, struct btrfs_key *key)
998 BUG_ON(!path->keep_locks);
999 for (level = 0; level < BTRFS_MAX_LEVEL; level++) {
1000 if (!path->nodes[level])
1002 btrfs_assert_tree_locked(path->nodes[level]);
1003 if (path->slots[level] + 1 >=
1004 btrfs_header_nritems(path->nodes[level]))
1007 btrfs_item_key_to_cpu(path->nodes[level], key,
1008 path->slots[level] + 1);
1010 btrfs_node_key_to_cpu(path->nodes[level], key,
1011 path->slots[level] + 1);
1018 * look for inline back ref. if back ref is found, *ref_ret is set
1019 * to the address of inline back ref, and 0 is returned.
1021 * if back ref isn't found, *ref_ret is set to the address where it
1022 * should be inserted, and -ENOENT is returned.
1024 * if insert is true and there are too many inline back refs, the path
1025 * points to the extent item, and -EAGAIN is returned.
1027 * NOTE: inline back refs are ordered in the same way that back ref
1028 * items in the tree are ordered.
1030 static noinline_for_stack
1031 int lookup_inline_extent_backref(struct btrfs_trans_handle *trans,
1032 struct btrfs_root *root,
1033 struct btrfs_path *path,
1034 struct btrfs_extent_inline_ref **ref_ret,
1035 u64 bytenr, u64 num_bytes,
1036 u64 parent, u64 root_objectid,
1037 u64 owner, u64 offset, int insert)
1039 struct btrfs_key key;
1040 struct extent_buffer *leaf;
1041 struct btrfs_extent_item *ei;
1042 struct btrfs_extent_inline_ref *iref;
1053 key.objectid = bytenr;
1054 key.type = BTRFS_EXTENT_ITEM_KEY;
1055 key.offset = num_bytes;
1057 want = extent_ref_type(parent, owner);
1059 extra_size = btrfs_extent_inline_ref_size(want);
1060 if (owner >= BTRFS_FIRST_FREE_OBJECTID)
1061 path->keep_locks = 1;
1064 ret = btrfs_search_slot(trans, root, &key, path, extra_size, 1);
1071 leaf = path->nodes[0];
1072 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1073 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1074 if (item_size < sizeof(*ei)) {
1079 ret = convert_extent_item_v0(trans, root, path, owner,
1085 leaf = path->nodes[0];
1086 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1089 BUG_ON(item_size < sizeof(*ei));
1091 if (owner < BTRFS_FIRST_FREE_OBJECTID && insert &&
1092 item_size + extra_size >= BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
1097 ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1098 flags = btrfs_extent_flags(leaf, ei);
1100 ptr = (unsigned long)(ei + 1);
1101 end = (unsigned long)ei + item_size;
1103 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
1104 ptr += sizeof(struct btrfs_tree_block_info);
1107 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA));
1116 iref = (struct btrfs_extent_inline_ref *)ptr;
1117 type = btrfs_extent_inline_ref_type(leaf, iref);
1121 ptr += btrfs_extent_inline_ref_size(type);
1125 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1126 struct btrfs_extent_data_ref *dref;
1127 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1128 if (match_extent_data_ref(leaf, dref, root_objectid,
1133 if (hash_extent_data_ref_item(leaf, dref) <
1134 hash_extent_data_ref(root_objectid, owner, offset))
1138 ref_offset = btrfs_extent_inline_ref_offset(leaf, iref);
1140 if (parent == ref_offset) {
1144 if (ref_offset < parent)
1147 if (root_objectid == ref_offset) {
1151 if (ref_offset < root_objectid)
1155 ptr += btrfs_extent_inline_ref_size(type);
1157 if (err == -ENOENT && insert) {
1158 if (item_size + extra_size >=
1159 BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
1164 * To add new inline back ref, we have to make sure
1165 * there is no corresponding back ref item.
1166 * For simplicity, we just do not add new inline back
1167 * ref if there is any kind of item for this block
1169 if (owner >= BTRFS_FIRST_FREE_OBJECTID &&
1170 find_next_key(path, &key) == 0 && key.objectid == bytenr) {
1175 *ref_ret = (struct btrfs_extent_inline_ref *)ptr;
1177 if (insert && owner >= BTRFS_FIRST_FREE_OBJECTID) {
1178 path->keep_locks = 0;
1179 btrfs_unlock_up_safe(path, 1);
1185 * helper to add new inline back ref
1187 static noinline_for_stack
1188 int setup_inline_extent_backref(struct btrfs_trans_handle *trans,
1189 struct btrfs_root *root,
1190 struct btrfs_path *path,
1191 struct btrfs_extent_inline_ref *iref,
1192 u64 parent, u64 root_objectid,
1193 u64 owner, u64 offset, int refs_to_add,
1194 struct btrfs_delayed_extent_op *extent_op)
1196 struct extent_buffer *leaf;
1197 struct btrfs_extent_item *ei;
1200 unsigned long item_offset;
1206 leaf = path->nodes[0];
1207 ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1208 item_offset = (unsigned long)iref - (unsigned long)ei;
1210 type = extent_ref_type(parent, owner);
1211 size = btrfs_extent_inline_ref_size(type);
1213 ret = btrfs_extend_item(trans, root, path, size);
1216 ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1217 refs = btrfs_extent_refs(leaf, ei);
1218 refs += refs_to_add;
1219 btrfs_set_extent_refs(leaf, ei, refs);
1221 __run_delayed_extent_op(extent_op, leaf, ei);
1223 ptr = (unsigned long)ei + item_offset;
1224 end = (unsigned long)ei + btrfs_item_size_nr(leaf, path->slots[0]);
1225 if (ptr < end - size)
1226 memmove_extent_buffer(leaf, ptr + size, ptr,
1229 iref = (struct btrfs_extent_inline_ref *)ptr;
1230 btrfs_set_extent_inline_ref_type(leaf, iref, type);
1231 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1232 struct btrfs_extent_data_ref *dref;
1233 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1234 btrfs_set_extent_data_ref_root(leaf, dref, root_objectid);
1235 btrfs_set_extent_data_ref_objectid(leaf, dref, owner);
1236 btrfs_set_extent_data_ref_offset(leaf, dref, offset);
1237 btrfs_set_extent_data_ref_count(leaf, dref, refs_to_add);
1238 } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1239 struct btrfs_shared_data_ref *sref;
1240 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1241 btrfs_set_shared_data_ref_count(leaf, sref, refs_to_add);
1242 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1243 } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
1244 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1246 btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
1248 btrfs_mark_buffer_dirty(leaf);
1252 static int lookup_extent_backref(struct btrfs_trans_handle *trans,
1253 struct btrfs_root *root,
1254 struct btrfs_path *path,
1255 struct btrfs_extent_inline_ref **ref_ret,
1256 u64 bytenr, u64 num_bytes, u64 parent,
1257 u64 root_objectid, u64 owner, u64 offset)
1261 ret = lookup_inline_extent_backref(trans, root, path, ref_ret,
1262 bytenr, num_bytes, parent,
1263 root_objectid, owner, offset, 0);
1267 btrfs_release_path(root, path);
1270 if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1271 ret = lookup_tree_block_ref(trans, root, path, bytenr, parent,
1274 ret = lookup_extent_data_ref(trans, root, path, bytenr, parent,
1275 root_objectid, owner, offset);
1281 * helper to update/remove inline back ref
1283 static noinline_for_stack
1284 int update_inline_extent_backref(struct btrfs_trans_handle *trans,
1285 struct btrfs_root *root,
1286 struct btrfs_path *path,
1287 struct btrfs_extent_inline_ref *iref,
1289 struct btrfs_delayed_extent_op *extent_op)
1291 struct extent_buffer *leaf;
1292 struct btrfs_extent_item *ei;
1293 struct btrfs_extent_data_ref *dref = NULL;
1294 struct btrfs_shared_data_ref *sref = NULL;
1303 leaf = path->nodes[0];
1304 ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1305 refs = btrfs_extent_refs(leaf, ei);
1306 WARN_ON(refs_to_mod < 0 && refs + refs_to_mod <= 0);
1307 refs += refs_to_mod;
1308 btrfs_set_extent_refs(leaf, ei, refs);
1310 __run_delayed_extent_op(extent_op, leaf, ei);
1312 type = btrfs_extent_inline_ref_type(leaf, iref);
1314 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1315 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1316 refs = btrfs_extent_data_ref_count(leaf, dref);
1317 } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1318 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1319 refs = btrfs_shared_data_ref_count(leaf, sref);
1322 BUG_ON(refs_to_mod != -1);
1325 BUG_ON(refs_to_mod < 0 && refs < -refs_to_mod);
1326 refs += refs_to_mod;
1329 if (type == BTRFS_EXTENT_DATA_REF_KEY)
1330 btrfs_set_extent_data_ref_count(leaf, dref, refs);
1332 btrfs_set_shared_data_ref_count(leaf, sref, refs);
1334 size = btrfs_extent_inline_ref_size(type);
1335 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1336 ptr = (unsigned long)iref;
1337 end = (unsigned long)ei + item_size;
1338 if (ptr + size < end)
1339 memmove_extent_buffer(leaf, ptr, ptr + size,
1342 ret = btrfs_truncate_item(trans, root, path, item_size, 1);
1345 btrfs_mark_buffer_dirty(leaf);
1349 static noinline_for_stack
1350 int insert_inline_extent_backref(struct btrfs_trans_handle *trans,
1351 struct btrfs_root *root,
1352 struct btrfs_path *path,
1353 u64 bytenr, u64 num_bytes, u64 parent,
1354 u64 root_objectid, u64 owner,
1355 u64 offset, int refs_to_add,
1356 struct btrfs_delayed_extent_op *extent_op)
1358 struct btrfs_extent_inline_ref *iref;
1361 ret = lookup_inline_extent_backref(trans, root, path, &iref,
1362 bytenr, num_bytes, parent,
1363 root_objectid, owner, offset, 1);
1365 BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID);
1366 ret = update_inline_extent_backref(trans, root, path, iref,
1367 refs_to_add, extent_op);
1368 } else if (ret == -ENOENT) {
1369 ret = setup_inline_extent_backref(trans, root, path, iref,
1370 parent, root_objectid,
1371 owner, offset, refs_to_add,
1377 static int insert_extent_backref(struct btrfs_trans_handle *trans,
1378 struct btrfs_root *root,
1379 struct btrfs_path *path,
1380 u64 bytenr, u64 parent, u64 root_objectid,
1381 u64 owner, u64 offset, int refs_to_add)
1384 if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1385 BUG_ON(refs_to_add != 1);
1386 ret = insert_tree_block_ref(trans, root, path, bytenr,
1387 parent, root_objectid);
1389 ret = insert_extent_data_ref(trans, root, path, bytenr,
1390 parent, root_objectid,
1391 owner, offset, refs_to_add);
1396 static int remove_extent_backref(struct btrfs_trans_handle *trans,
1397 struct btrfs_root *root,
1398 struct btrfs_path *path,
1399 struct btrfs_extent_inline_ref *iref,
1400 int refs_to_drop, int is_data)
1404 BUG_ON(!is_data && refs_to_drop != 1);
1406 ret = update_inline_extent_backref(trans, root, path, iref,
1407 -refs_to_drop, NULL);
1408 } else if (is_data) {
1409 ret = remove_extent_data_ref(trans, root, path, refs_to_drop);
1411 ret = btrfs_del_item(trans, root, path);
1416 #ifdef BIO_RW_DISCARD
1417 static void btrfs_issue_discard(struct block_device *bdev,
1420 blkdev_issue_discard(bdev, start >> 9, len >> 9, GFP_KERNEL);
1424 static int btrfs_discard_extent(struct btrfs_root *root, u64 bytenr,
1427 #ifdef BIO_RW_DISCARD
1429 u64 map_length = num_bytes;
1430 struct btrfs_multi_bio *multi = NULL;
1432 /* Tell the block device(s) that the sectors can be discarded */
1433 ret = btrfs_map_block(&root->fs_info->mapping_tree, READ,
1434 bytenr, &map_length, &multi, 0);
1436 struct btrfs_bio_stripe *stripe = multi->stripes;
1439 if (map_length > num_bytes)
1440 map_length = num_bytes;
1442 for (i = 0; i < multi->num_stripes; i++, stripe++) {
1443 btrfs_issue_discard(stripe->dev->bdev,
1456 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
1457 struct btrfs_root *root,
1458 u64 bytenr, u64 num_bytes, u64 parent,
1459 u64 root_objectid, u64 owner, u64 offset)
1462 BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID &&
1463 root_objectid == BTRFS_TREE_LOG_OBJECTID);
1465 if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1466 ret = btrfs_add_delayed_tree_ref(trans, bytenr, num_bytes,
1467 parent, root_objectid, (int)owner,
1468 BTRFS_ADD_DELAYED_REF, NULL);
1470 ret = btrfs_add_delayed_data_ref(trans, bytenr, num_bytes,
1471 parent, root_objectid, owner, offset,
1472 BTRFS_ADD_DELAYED_REF, NULL);
1477 static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
1478 struct btrfs_root *root,
1479 u64 bytenr, u64 num_bytes,
1480 u64 parent, u64 root_objectid,
1481 u64 owner, u64 offset, int refs_to_add,
1482 struct btrfs_delayed_extent_op *extent_op)
1484 struct btrfs_path *path;
1485 struct extent_buffer *leaf;
1486 struct btrfs_extent_item *item;
1491 path = btrfs_alloc_path();
1496 path->leave_spinning = 1;
1497 /* this will setup the path even if it fails to insert the back ref */
1498 ret = insert_inline_extent_backref(trans, root->fs_info->extent_root,
1499 path, bytenr, num_bytes, parent,
1500 root_objectid, owner, offset,
1501 refs_to_add, extent_op);
1505 if (ret != -EAGAIN) {
1510 leaf = path->nodes[0];
1511 item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1512 refs = btrfs_extent_refs(leaf, item);
1513 btrfs_set_extent_refs(leaf, item, refs + refs_to_add);
1515 __run_delayed_extent_op(extent_op, leaf, item);
1517 btrfs_mark_buffer_dirty(leaf);
1518 btrfs_release_path(root->fs_info->extent_root, path);
1521 path->leave_spinning = 1;
1523 /* now insert the actual backref */
1524 ret = insert_extent_backref(trans, root->fs_info->extent_root,
1525 path, bytenr, parent, root_objectid,
1526 owner, offset, refs_to_add);
1529 btrfs_free_path(path);
1533 static int run_delayed_data_ref(struct btrfs_trans_handle *trans,
1534 struct btrfs_root *root,
1535 struct btrfs_delayed_ref_node *node,
1536 struct btrfs_delayed_extent_op *extent_op,
1537 int insert_reserved)
1540 struct btrfs_delayed_data_ref *ref;
1541 struct btrfs_key ins;
1546 ins.objectid = node->bytenr;
1547 ins.offset = node->num_bytes;
1548 ins.type = BTRFS_EXTENT_ITEM_KEY;
1550 ref = btrfs_delayed_node_to_data_ref(node);
1551 if (node->type == BTRFS_SHARED_DATA_REF_KEY)
1552 parent = ref->parent;
1554 ref_root = ref->root;
1556 if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
1558 BUG_ON(extent_op->update_key);
1559 flags |= extent_op->flags_to_set;
1561 ret = alloc_reserved_file_extent(trans, root,
1562 parent, ref_root, flags,
1563 ref->objectid, ref->offset,
1564 &ins, node->ref_mod);
1565 update_reserved_extents(root, ins.objectid, ins.offset, 0);
1566 } else if (node->action == BTRFS_ADD_DELAYED_REF) {
1567 ret = __btrfs_inc_extent_ref(trans, root, node->bytenr,
1568 node->num_bytes, parent,
1569 ref_root, ref->objectid,
1570 ref->offset, node->ref_mod,
1572 } else if (node->action == BTRFS_DROP_DELAYED_REF) {
1573 ret = __btrfs_free_extent(trans, root, node->bytenr,
1574 node->num_bytes, parent,
1575 ref_root, ref->objectid,
1576 ref->offset, node->ref_mod,
1584 static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
1585 struct extent_buffer *leaf,
1586 struct btrfs_extent_item *ei)
1588 u64 flags = btrfs_extent_flags(leaf, ei);
1589 if (extent_op->update_flags) {
1590 flags |= extent_op->flags_to_set;
1591 btrfs_set_extent_flags(leaf, ei, flags);
1594 if (extent_op->update_key) {
1595 struct btrfs_tree_block_info *bi;
1596 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK));
1597 bi = (struct btrfs_tree_block_info *)(ei + 1);
1598 btrfs_set_tree_block_key(leaf, bi, &extent_op->key);
1602 static int run_delayed_extent_op(struct btrfs_trans_handle *trans,
1603 struct btrfs_root *root,
1604 struct btrfs_delayed_ref_node *node,
1605 struct btrfs_delayed_extent_op *extent_op)
1607 struct btrfs_key key;
1608 struct btrfs_path *path;
1609 struct btrfs_extent_item *ei;
1610 struct extent_buffer *leaf;
1615 path = btrfs_alloc_path();
1619 key.objectid = node->bytenr;
1620 key.type = BTRFS_EXTENT_ITEM_KEY;
1621 key.offset = node->num_bytes;
1624 path->leave_spinning = 1;
1625 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key,
1636 leaf = path->nodes[0];
1637 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1638 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1639 if (item_size < sizeof(*ei)) {
1640 ret = convert_extent_item_v0(trans, root->fs_info->extent_root,
1646 leaf = path->nodes[0];
1647 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1650 BUG_ON(item_size < sizeof(*ei));
1651 ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1652 __run_delayed_extent_op(extent_op, leaf, ei);
1654 btrfs_mark_buffer_dirty(leaf);
1656 btrfs_free_path(path);
1660 static int run_delayed_tree_ref(struct btrfs_trans_handle *trans,
1661 struct btrfs_root *root,
1662 struct btrfs_delayed_ref_node *node,
1663 struct btrfs_delayed_extent_op *extent_op,
1664 int insert_reserved)
1667 struct btrfs_delayed_tree_ref *ref;
1668 struct btrfs_key ins;
1672 ins.objectid = node->bytenr;
1673 ins.offset = node->num_bytes;
1674 ins.type = BTRFS_EXTENT_ITEM_KEY;
1676 ref = btrfs_delayed_node_to_tree_ref(node);
1677 if (node->type == BTRFS_SHARED_BLOCK_REF_KEY)
1678 parent = ref->parent;
1680 ref_root = ref->root;
1682 BUG_ON(node->ref_mod != 1);
1683 if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
1684 BUG_ON(!extent_op || !extent_op->update_flags ||
1685 !extent_op->update_key);
1686 ret = alloc_reserved_tree_block(trans, root,
1688 extent_op->flags_to_set,
1691 update_reserved_extents(root, ins.objectid, ins.offset, 0);
1692 } else if (node->action == BTRFS_ADD_DELAYED_REF) {
1693 ret = __btrfs_inc_extent_ref(trans, root, node->bytenr,
1694 node->num_bytes, parent, ref_root,
1695 ref->level, 0, 1, extent_op);
1696 } else if (node->action == BTRFS_DROP_DELAYED_REF) {
1697 ret = __btrfs_free_extent(trans, root, node->bytenr,
1698 node->num_bytes, parent, ref_root,
1699 ref->level, 0, 1, extent_op);
1707 /* helper function to actually process a single delayed ref entry */
1708 static int run_one_delayed_ref(struct btrfs_trans_handle *trans,
1709 struct btrfs_root *root,
1710 struct btrfs_delayed_ref_node *node,
1711 struct btrfs_delayed_extent_op *extent_op,
1712 int insert_reserved)
1715 if (btrfs_delayed_ref_is_head(node)) {
1716 struct btrfs_delayed_ref_head *head;
1718 * we've hit the end of the chain and we were supposed
1719 * to insert this extent into the tree. But, it got
1720 * deleted before we ever needed to insert it, so all
1721 * we have to do is clean up the accounting
1724 head = btrfs_delayed_node_to_head(node);
1725 if (insert_reserved) {
1726 if (head->is_data) {
1727 ret = btrfs_del_csums(trans, root,
1732 btrfs_update_pinned_extents(root, node->bytenr,
1733 node->num_bytes, 1);
1734 update_reserved_extents(root, node->bytenr,
1735 node->num_bytes, 0);
1737 mutex_unlock(&head->mutex);
1741 if (node->type == BTRFS_TREE_BLOCK_REF_KEY ||
1742 node->type == BTRFS_SHARED_BLOCK_REF_KEY)
1743 ret = run_delayed_tree_ref(trans, root, node, extent_op,
1745 else if (node->type == BTRFS_EXTENT_DATA_REF_KEY ||
1746 node->type == BTRFS_SHARED_DATA_REF_KEY)
1747 ret = run_delayed_data_ref(trans, root, node, extent_op,
1754 static noinline struct btrfs_delayed_ref_node *
1755 select_delayed_ref(struct btrfs_delayed_ref_head *head)
1757 struct rb_node *node;
1758 struct btrfs_delayed_ref_node *ref;
1759 int action = BTRFS_ADD_DELAYED_REF;
1762 * select delayed ref of type BTRFS_ADD_DELAYED_REF first.
1763 * this prevents ref count from going down to zero when
1764 * there still are pending delayed ref.
1766 node = rb_prev(&head->node.rb_node);
1770 ref = rb_entry(node, struct btrfs_delayed_ref_node,
1772 if (ref->bytenr != head->node.bytenr)
1774 if (ref->action == action)
1776 node = rb_prev(node);
1778 if (action == BTRFS_ADD_DELAYED_REF) {
1779 action = BTRFS_DROP_DELAYED_REF;
1785 static noinline int run_clustered_refs(struct btrfs_trans_handle *trans,
1786 struct btrfs_root *root,
1787 struct list_head *cluster)
1789 struct btrfs_delayed_ref_root *delayed_refs;
1790 struct btrfs_delayed_ref_node *ref;
1791 struct btrfs_delayed_ref_head *locked_ref = NULL;
1792 struct btrfs_delayed_extent_op *extent_op;
1795 int must_insert_reserved = 0;
1797 delayed_refs = &trans->transaction->delayed_refs;
1800 /* pick a new head ref from the cluster list */
1801 if (list_empty(cluster))
1804 locked_ref = list_entry(cluster->next,
1805 struct btrfs_delayed_ref_head, cluster);
1807 /* grab the lock that says we are going to process
1808 * all the refs for this head */
1809 ret = btrfs_delayed_ref_lock(trans, locked_ref);
1812 * we may have dropped the spin lock to get the head
1813 * mutex lock, and that might have given someone else
1814 * time to free the head. If that's true, it has been
1815 * removed from our list and we can move on.
1817 if (ret == -EAGAIN) {
1825 * record the must insert reserved flag before we
1826 * drop the spin lock.
1828 must_insert_reserved = locked_ref->must_insert_reserved;
1829 locked_ref->must_insert_reserved = 0;
1831 extent_op = locked_ref->extent_op;
1832 locked_ref->extent_op = NULL;
1835 * locked_ref is the head node, so we have to go one
1836 * node back for any delayed ref updates
1838 ref = select_delayed_ref(locked_ref);
1840 /* All delayed refs have been processed, Go ahead
1841 * and send the head node to run_one_delayed_ref,
1842 * so that any accounting fixes can happen
1844 ref = &locked_ref->node;
1846 if (extent_op && must_insert_reserved) {
1852 spin_unlock(&delayed_refs->lock);
1854 ret = run_delayed_extent_op(trans, root,
1860 spin_lock(&delayed_refs->lock);
1864 list_del_init(&locked_ref->cluster);
1869 rb_erase(&ref->rb_node, &delayed_refs->root);
1870 delayed_refs->num_entries--;
1872 spin_unlock(&delayed_refs->lock);
1874 ret = run_one_delayed_ref(trans, root, ref, extent_op,
1875 must_insert_reserved);
1878 btrfs_put_delayed_ref(ref);
1883 spin_lock(&delayed_refs->lock);
1889 * this starts processing the delayed reference count updates and
1890 * extent insertions we have queued up so far. count can be
1891 * 0, which means to process everything in the tree at the start
1892 * of the run (but not newly added entries), or it can be some target
1893 * number you'd like to process.
1895 int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
1896 struct btrfs_root *root, unsigned long count)
1898 struct rb_node *node;
1899 struct btrfs_delayed_ref_root *delayed_refs;
1900 struct btrfs_delayed_ref_node *ref;
1901 struct list_head cluster;
1903 int run_all = count == (unsigned long)-1;
1906 if (root == root->fs_info->extent_root)
1907 root = root->fs_info->tree_root;
1909 delayed_refs = &trans->transaction->delayed_refs;
1910 INIT_LIST_HEAD(&cluster);
1912 spin_lock(&delayed_refs->lock);
1914 count = delayed_refs->num_entries * 2;
1918 if (!(run_all || run_most) &&
1919 delayed_refs->num_heads_ready < 64)
1923 * go find something we can process in the rbtree. We start at
1924 * the beginning of the tree, and then build a cluster
1925 * of refs to process starting at the first one we are able to
1928 ret = btrfs_find_ref_cluster(trans, &cluster,
1929 delayed_refs->run_delayed_start);
1933 ret = run_clustered_refs(trans, root, &cluster);
1936 count -= min_t(unsigned long, ret, count);
1943 node = rb_first(&delayed_refs->root);
1946 count = (unsigned long)-1;
1949 ref = rb_entry(node, struct btrfs_delayed_ref_node,
1951 if (btrfs_delayed_ref_is_head(ref)) {
1952 struct btrfs_delayed_ref_head *head;
1954 head = btrfs_delayed_node_to_head(ref);
1955 atomic_inc(&ref->refs);
1957 spin_unlock(&delayed_refs->lock);
1958 mutex_lock(&head->mutex);
1959 mutex_unlock(&head->mutex);
1961 btrfs_put_delayed_ref(ref);
1965 node = rb_next(node);
1967 spin_unlock(&delayed_refs->lock);
1968 schedule_timeout(1);
1972 spin_unlock(&delayed_refs->lock);
1976 int btrfs_set_disk_extent_flags(struct btrfs_trans_handle *trans,
1977 struct btrfs_root *root,
1978 u64 bytenr, u64 num_bytes, u64 flags,
1981 struct btrfs_delayed_extent_op *extent_op;
1984 extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
1988 extent_op->flags_to_set = flags;
1989 extent_op->update_flags = 1;
1990 extent_op->update_key = 0;
1991 extent_op->is_data = is_data ? 1 : 0;
1993 ret = btrfs_add_delayed_extent_op(trans, bytenr, num_bytes, extent_op);
1999 static noinline int check_delayed_ref(struct btrfs_trans_handle *trans,
2000 struct btrfs_root *root,
2001 struct btrfs_path *path,
2002 u64 objectid, u64 offset, u64 bytenr)
2004 struct btrfs_delayed_ref_head *head;
2005 struct btrfs_delayed_ref_node *ref;
2006 struct btrfs_delayed_data_ref *data_ref;
2007 struct btrfs_delayed_ref_root *delayed_refs;
2008 struct rb_node *node;
2012 delayed_refs = &trans->transaction->delayed_refs;
2013 spin_lock(&delayed_refs->lock);
2014 head = btrfs_find_delayed_ref_head(trans, bytenr);
2018 if (!mutex_trylock(&head->mutex)) {
2019 atomic_inc(&head->node.refs);
2020 spin_unlock(&delayed_refs->lock);
2022 btrfs_release_path(root->fs_info->extent_root, path);
2024 mutex_lock(&head->mutex);
2025 mutex_unlock(&head->mutex);
2026 btrfs_put_delayed_ref(&head->node);
2030 node = rb_prev(&head->node.rb_node);
2034 ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
2036 if (ref->bytenr != bytenr)
2040 if (ref->type != BTRFS_EXTENT_DATA_REF_KEY)
2043 data_ref = btrfs_delayed_node_to_data_ref(ref);
2045 node = rb_prev(node);
2047 ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
2048 if (ref->bytenr == bytenr)
2052 if (data_ref->root != root->root_key.objectid ||
2053 data_ref->objectid != objectid || data_ref->offset != offset)
2058 mutex_unlock(&head->mutex);
2060 spin_unlock(&delayed_refs->lock);
2064 static noinline int check_committed_ref(struct btrfs_trans_handle *trans,
2065 struct btrfs_root *root,
2066 struct btrfs_path *path,
2067 u64 objectid, u64 offset, u64 bytenr)
2069 struct btrfs_root *extent_root = root->fs_info->extent_root;
2070 struct extent_buffer *leaf;
2071 struct btrfs_extent_data_ref *ref;
2072 struct btrfs_extent_inline_ref *iref;
2073 struct btrfs_extent_item *ei;
2074 struct btrfs_key key;
2078 key.objectid = bytenr;
2079 key.offset = (u64)-1;
2080 key.type = BTRFS_EXTENT_ITEM_KEY;
2082 ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
2088 if (path->slots[0] == 0)
2092 leaf = path->nodes[0];
2093 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
2095 if (key.objectid != bytenr || key.type != BTRFS_EXTENT_ITEM_KEY)
2099 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2100 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2101 if (item_size < sizeof(*ei)) {
2102 WARN_ON(item_size != sizeof(struct btrfs_extent_item_v0));
2106 ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
2108 if (item_size != sizeof(*ei) +
2109 btrfs_extent_inline_ref_size(BTRFS_EXTENT_DATA_REF_KEY))
2112 if (btrfs_extent_generation(leaf, ei) <=
2113 btrfs_root_last_snapshot(&root->root_item))
2116 iref = (struct btrfs_extent_inline_ref *)(ei + 1);
2117 if (btrfs_extent_inline_ref_type(leaf, iref) !=
2118 BTRFS_EXTENT_DATA_REF_KEY)
2121 ref = (struct btrfs_extent_data_ref *)(&iref->offset);
2122 if (btrfs_extent_refs(leaf, ei) !=
2123 btrfs_extent_data_ref_count(leaf, ref) ||
2124 btrfs_extent_data_ref_root(leaf, ref) !=
2125 root->root_key.objectid ||
2126 btrfs_extent_data_ref_objectid(leaf, ref) != objectid ||
2127 btrfs_extent_data_ref_offset(leaf, ref) != offset)
2135 int btrfs_cross_ref_exist(struct btrfs_trans_handle *trans,
2136 struct btrfs_root *root,
2137 u64 objectid, u64 offset, u64 bytenr)
2139 struct btrfs_path *path;
2143 path = btrfs_alloc_path();
2148 ret = check_committed_ref(trans, root, path, objectid,
2150 if (ret && ret != -ENOENT)
2153 ret2 = check_delayed_ref(trans, root, path, objectid,
2155 } while (ret2 == -EAGAIN);
2157 if (ret2 && ret2 != -ENOENT) {
2162 if (ret != -ENOENT || ret2 != -ENOENT)
2165 btrfs_free_path(path);
2170 int btrfs_cache_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2171 struct extent_buffer *buf, u32 nr_extents)
2173 struct btrfs_key key;
2174 struct btrfs_file_extent_item *fi;
2182 if (!root->ref_cows)
2185 if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
2187 root_gen = root->root_key.offset;
2190 root_gen = trans->transid - 1;
2193 level = btrfs_header_level(buf);
2194 nritems = btrfs_header_nritems(buf);
2197 struct btrfs_leaf_ref *ref;
2198 struct btrfs_extent_info *info;
2200 ref = btrfs_alloc_leaf_ref(root, nr_extents);
2206 ref->root_gen = root_gen;
2207 ref->bytenr = buf->start;
2208 ref->owner = btrfs_header_owner(buf);
2209 ref->generation = btrfs_header_generation(buf);
2210 ref->nritems = nr_extents;
2211 info = ref->extents;
2213 for (i = 0; nr_extents > 0 && i < nritems; i++) {
2215 btrfs_item_key_to_cpu(buf, &key, i);
2216 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2218 fi = btrfs_item_ptr(buf, i,
2219 struct btrfs_file_extent_item);
2220 if (btrfs_file_extent_type(buf, fi) ==
2221 BTRFS_FILE_EXTENT_INLINE)
2223 disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
2224 if (disk_bytenr == 0)
2227 info->bytenr = disk_bytenr;
2229 btrfs_file_extent_disk_num_bytes(buf, fi);
2230 info->objectid = key.objectid;
2231 info->offset = key.offset;
2235 ret = btrfs_add_leaf_ref(root, ref, shared);
2236 if (ret == -EEXIST && shared) {
2237 struct btrfs_leaf_ref *old;
2238 old = btrfs_lookup_leaf_ref(root, ref->bytenr);
2240 btrfs_remove_leaf_ref(root, old);
2241 btrfs_free_leaf_ref(root, old);
2242 ret = btrfs_add_leaf_ref(root, ref, shared);
2245 btrfs_free_leaf_ref(root, ref);
2251 /* when a block goes through cow, we update the reference counts of
2252 * everything that block points to. The internal pointers of the block
2253 * can be in just about any order, and it is likely to have clusters of
2254 * things that are close together and clusters of things that are not.
2256 * To help reduce the seeks that come with updating all of these reference
2257 * counts, sort them by byte number before actual updates are done.
2259 * struct refsort is used to match byte number to slot in the btree block.
2260 * we sort based on the byte number and then use the slot to actually
2263 * struct refsort is smaller than strcut btrfs_item and smaller than
2264 * struct btrfs_key_ptr. Since we're currently limited to the page size
2265 * for a btree block, there's no way for a kmalloc of refsorts for a
2266 * single node to be bigger than a page.
2274 * for passing into sort()
2276 static int refsort_cmp(const void *a_void, const void *b_void)
2278 const struct refsort *a = a_void;
2279 const struct refsort *b = b_void;
2281 if (a->bytenr < b->bytenr)
2283 if (a->bytenr > b->bytenr)
2289 static int __btrfs_mod_ref(struct btrfs_trans_handle *trans,
2290 struct btrfs_root *root,
2291 struct extent_buffer *buf,
2292 int full_backref, int inc)
2299 struct btrfs_key key;
2300 struct btrfs_file_extent_item *fi;
2304 int (*process_func)(struct btrfs_trans_handle *, struct btrfs_root *,
2305 u64, u64, u64, u64, u64, u64);
2307 ref_root = btrfs_header_owner(buf);
2308 nritems = btrfs_header_nritems(buf);
2309 level = btrfs_header_level(buf);
2311 if (!root->ref_cows && level == 0)
2315 process_func = btrfs_inc_extent_ref;
2317 process_func = btrfs_free_extent;
2320 parent = buf->start;
2324 for (i = 0; i < nritems; i++) {
2326 btrfs_item_key_to_cpu(buf, &key, i);
2327 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2329 fi = btrfs_item_ptr(buf, i,
2330 struct btrfs_file_extent_item);
2331 if (btrfs_file_extent_type(buf, fi) ==
2332 BTRFS_FILE_EXTENT_INLINE)
2334 bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
2338 num_bytes = btrfs_file_extent_disk_num_bytes(buf, fi);
2339 key.offset -= btrfs_file_extent_offset(buf, fi);
2340 ret = process_func(trans, root, bytenr, num_bytes,
2341 parent, ref_root, key.objectid,
2346 bytenr = btrfs_node_blockptr(buf, i);
2347 num_bytes = btrfs_level_size(root, level - 1);
2348 ret = process_func(trans, root, bytenr, num_bytes,
2349 parent, ref_root, level - 1, 0);
2360 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2361 struct extent_buffer *buf, int full_backref)
2363 return __btrfs_mod_ref(trans, root, buf, full_backref, 1);
2366 int btrfs_dec_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2367 struct extent_buffer *buf, int full_backref)
2369 return __btrfs_mod_ref(trans, root, buf, full_backref, 0);
2372 static int write_one_cache_group(struct btrfs_trans_handle *trans,
2373 struct btrfs_root *root,
2374 struct btrfs_path *path,
2375 struct btrfs_block_group_cache *cache)
2378 struct btrfs_root *extent_root = root->fs_info->extent_root;
2380 struct extent_buffer *leaf;
2382 ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
2387 leaf = path->nodes[0];
2388 bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
2389 write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
2390 btrfs_mark_buffer_dirty(leaf);
2391 btrfs_release_path(extent_root, path);
2399 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
2400 struct btrfs_root *root)
2402 struct btrfs_block_group_cache *cache, *entry;
2406 struct btrfs_path *path;
2409 path = btrfs_alloc_path();
2415 spin_lock(&root->fs_info->block_group_cache_lock);
2416 for (n = rb_first(&root->fs_info->block_group_cache_tree);
2417 n; n = rb_next(n)) {
2418 entry = rb_entry(n, struct btrfs_block_group_cache,
2425 spin_unlock(&root->fs_info->block_group_cache_lock);
2431 last += cache->key.offset;
2433 err = write_one_cache_group(trans, root,
2436 * if we fail to write the cache group, we want
2437 * to keep it marked dirty in hopes that a later
2445 btrfs_free_path(path);
2449 int btrfs_extent_readonly(struct btrfs_root *root, u64 bytenr)
2451 struct btrfs_block_group_cache *block_group;
2454 block_group = btrfs_lookup_block_group(root->fs_info, bytenr);
2455 if (!block_group || block_group->ro)
2458 btrfs_put_block_group(block_group);
2462 static int update_space_info(struct btrfs_fs_info *info, u64 flags,
2463 u64 total_bytes, u64 bytes_used,
2464 struct btrfs_space_info **space_info)
2466 struct btrfs_space_info *found;
2468 found = __find_space_info(info, flags);
2470 spin_lock(&found->lock);
2471 found->total_bytes += total_bytes;
2472 found->bytes_used += bytes_used;
2474 spin_unlock(&found->lock);
2475 *space_info = found;
2478 found = kzalloc(sizeof(*found), GFP_NOFS);
2482 INIT_LIST_HEAD(&found->block_groups);
2483 init_rwsem(&found->groups_sem);
2484 spin_lock_init(&found->lock);
2485 found->flags = flags;
2486 found->total_bytes = total_bytes;
2487 found->bytes_used = bytes_used;
2488 found->bytes_pinned = 0;
2489 found->bytes_reserved = 0;
2490 found->bytes_readonly = 0;
2491 found->bytes_delalloc = 0;
2493 found->force_alloc = 0;
2494 *space_info = found;
2495 list_add_rcu(&found->list, &info->space_info);
2499 static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
2501 u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
2502 BTRFS_BLOCK_GROUP_RAID1 |
2503 BTRFS_BLOCK_GROUP_RAID10 |
2504 BTRFS_BLOCK_GROUP_DUP);
2506 if (flags & BTRFS_BLOCK_GROUP_DATA)
2507 fs_info->avail_data_alloc_bits |= extra_flags;
2508 if (flags & BTRFS_BLOCK_GROUP_METADATA)
2509 fs_info->avail_metadata_alloc_bits |= extra_flags;
2510 if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
2511 fs_info->avail_system_alloc_bits |= extra_flags;
2515 static void set_block_group_readonly(struct btrfs_block_group_cache *cache)
2517 spin_lock(&cache->space_info->lock);
2518 spin_lock(&cache->lock);
2520 cache->space_info->bytes_readonly += cache->key.offset -
2521 btrfs_block_group_used(&cache->item);
2524 spin_unlock(&cache->lock);
2525 spin_unlock(&cache->space_info->lock);
2528 u64 btrfs_reduce_alloc_profile(struct btrfs_root *root, u64 flags)
2530 u64 num_devices = root->fs_info->fs_devices->rw_devices;
2532 if (num_devices == 1)
2533 flags &= ~(BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID0);
2534 if (num_devices < 4)
2535 flags &= ~BTRFS_BLOCK_GROUP_RAID10;
2537 if ((flags & BTRFS_BLOCK_GROUP_DUP) &&
2538 (flags & (BTRFS_BLOCK_GROUP_RAID1 |
2539 BTRFS_BLOCK_GROUP_RAID10))) {
2540 flags &= ~BTRFS_BLOCK_GROUP_DUP;
2543 if ((flags & BTRFS_BLOCK_GROUP_RAID1) &&
2544 (flags & BTRFS_BLOCK_GROUP_RAID10)) {
2545 flags &= ~BTRFS_BLOCK_GROUP_RAID1;
2548 if ((flags & BTRFS_BLOCK_GROUP_RAID0) &&
2549 ((flags & BTRFS_BLOCK_GROUP_RAID1) |
2550 (flags & BTRFS_BLOCK_GROUP_RAID10) |
2551 (flags & BTRFS_BLOCK_GROUP_DUP)))
2552 flags &= ~BTRFS_BLOCK_GROUP_RAID0;
2556 static u64 btrfs_get_alloc_profile(struct btrfs_root *root, u64 data)
2558 struct btrfs_fs_info *info = root->fs_info;
2562 alloc_profile = info->avail_data_alloc_bits &
2563 info->data_alloc_profile;
2564 data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
2565 } else if (root == root->fs_info->chunk_root) {
2566 alloc_profile = info->avail_system_alloc_bits &
2567 info->system_alloc_profile;
2568 data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
2570 alloc_profile = info->avail_metadata_alloc_bits &
2571 info->metadata_alloc_profile;
2572 data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
2575 return btrfs_reduce_alloc_profile(root, data);
2578 void btrfs_set_inode_space_info(struct btrfs_root *root, struct inode *inode)
2582 alloc_target = btrfs_get_alloc_profile(root, 1);
2583 BTRFS_I(inode)->space_info = __find_space_info(root->fs_info,
2588 * for now this just makes sure we have at least 5% of our metadata space free
2591 int btrfs_check_metadata_free_space(struct btrfs_root *root)
2593 struct btrfs_fs_info *info = root->fs_info;
2594 struct btrfs_space_info *meta_sinfo;
2595 u64 alloc_target, thresh;
2596 int committed = 0, ret;
2598 /* get the space info for where the metadata will live */
2599 alloc_target = btrfs_get_alloc_profile(root, 0);
2600 meta_sinfo = __find_space_info(info, alloc_target);
2603 spin_lock(&meta_sinfo->lock);
2604 if (!meta_sinfo->full)
2605 thresh = meta_sinfo->total_bytes * 80;
2607 thresh = meta_sinfo->total_bytes * 95;
2609 do_div(thresh, 100);
2611 if (meta_sinfo->bytes_used + meta_sinfo->bytes_reserved +
2612 meta_sinfo->bytes_pinned + meta_sinfo->bytes_readonly > thresh) {
2613 struct btrfs_trans_handle *trans;
2614 if (!meta_sinfo->full) {
2615 meta_sinfo->force_alloc = 1;
2616 spin_unlock(&meta_sinfo->lock);
2618 trans = btrfs_start_transaction(root, 1);
2622 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2623 2 * 1024 * 1024, alloc_target, 0);
2624 btrfs_end_transaction(trans, root);
2627 spin_unlock(&meta_sinfo->lock);
2631 trans = btrfs_join_transaction(root, 1);
2634 ret = btrfs_commit_transaction(trans, root);
2641 spin_unlock(&meta_sinfo->lock);
2647 * This will check the space that the inode allocates from to make sure we have
2648 * enough space for bytes.
2650 int btrfs_check_data_free_space(struct btrfs_root *root, struct inode *inode,
2653 struct btrfs_space_info *data_sinfo;
2654 int ret = 0, committed = 0;
2656 /* make sure bytes are sectorsize aligned */
2657 bytes = (bytes + root->sectorsize - 1) & ~((u64)root->sectorsize - 1);
2659 data_sinfo = BTRFS_I(inode)->space_info;
2661 /* make sure we have enough space to handle the data first */
2662 spin_lock(&data_sinfo->lock);
2663 if (data_sinfo->total_bytes - data_sinfo->bytes_used -
2664 data_sinfo->bytes_delalloc - data_sinfo->bytes_reserved -
2665 data_sinfo->bytes_pinned - data_sinfo->bytes_readonly -
2666 data_sinfo->bytes_may_use < bytes) {
2667 struct btrfs_trans_handle *trans;
2670 * if we don't have enough free bytes in this space then we need
2671 * to alloc a new chunk.
2673 if (!data_sinfo->full) {
2676 data_sinfo->force_alloc = 1;
2677 spin_unlock(&data_sinfo->lock);
2679 alloc_target = btrfs_get_alloc_profile(root, 1);
2680 trans = btrfs_start_transaction(root, 1);
2684 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2685 bytes + 2 * 1024 * 1024,
2687 btrfs_end_transaction(trans, root);
2692 spin_unlock(&data_sinfo->lock);
2694 /* commit the current transaction and try again */
2697 trans = btrfs_join_transaction(root, 1);
2700 ret = btrfs_commit_transaction(trans, root);
2706 printk(KERN_ERR "no space left, need %llu, %llu delalloc bytes"
2707 ", %llu bytes_used, %llu bytes_reserved, "
2708 "%llu bytes_pinned, %llu bytes_readonly, %llu may use"
2709 "%llu total\n", (unsigned long long)bytes,
2710 (unsigned long long)data_sinfo->bytes_delalloc,
2711 (unsigned long long)data_sinfo->bytes_used,
2712 (unsigned long long)data_sinfo->bytes_reserved,
2713 (unsigned long long)data_sinfo->bytes_pinned,
2714 (unsigned long long)data_sinfo->bytes_readonly,
2715 (unsigned long long)data_sinfo->bytes_may_use,
2716 (unsigned long long)data_sinfo->total_bytes);
2719 data_sinfo->bytes_may_use += bytes;
2720 BTRFS_I(inode)->reserved_bytes += bytes;
2721 spin_unlock(&data_sinfo->lock);
2723 return btrfs_check_metadata_free_space(root);
2727 * if there was an error for whatever reason after calling
2728 * btrfs_check_data_free_space, call this so we can cleanup the counters.
2730 void btrfs_free_reserved_data_space(struct btrfs_root *root,
2731 struct inode *inode, u64 bytes)
2733 struct btrfs_space_info *data_sinfo;
2735 /* make sure bytes are sectorsize aligned */
2736 bytes = (bytes + root->sectorsize - 1) & ~((u64)root->sectorsize - 1);
2738 data_sinfo = BTRFS_I(inode)->space_info;
2739 spin_lock(&data_sinfo->lock);
2740 data_sinfo->bytes_may_use -= bytes;
2741 BTRFS_I(inode)->reserved_bytes -= bytes;
2742 spin_unlock(&data_sinfo->lock);
2745 /* called when we are adding a delalloc extent to the inode's io_tree */
2746 void btrfs_delalloc_reserve_space(struct btrfs_root *root, struct inode *inode,
2749 struct btrfs_space_info *data_sinfo;
2751 /* get the space info for where this inode will be storing its data */
2752 data_sinfo = BTRFS_I(inode)->space_info;
2754 /* make sure we have enough space to handle the data first */
2755 spin_lock(&data_sinfo->lock);
2756 data_sinfo->bytes_delalloc += bytes;
2759 * we are adding a delalloc extent without calling
2760 * btrfs_check_data_free_space first. This happens on a weird
2761 * writepage condition, but shouldn't hurt our accounting
2763 if (unlikely(bytes > BTRFS_I(inode)->reserved_bytes)) {
2764 data_sinfo->bytes_may_use -= BTRFS_I(inode)->reserved_bytes;
2765 BTRFS_I(inode)->reserved_bytes = 0;
2767 data_sinfo->bytes_may_use -= bytes;
2768 BTRFS_I(inode)->reserved_bytes -= bytes;
2771 spin_unlock(&data_sinfo->lock);
2774 /* called when we are clearing an delalloc extent from the inode's io_tree */
2775 void btrfs_delalloc_free_space(struct btrfs_root *root, struct inode *inode,
2778 struct btrfs_space_info *info;
2780 info = BTRFS_I(inode)->space_info;
2782 spin_lock(&info->lock);
2783 info->bytes_delalloc -= bytes;
2784 spin_unlock(&info->lock);
2787 static void force_metadata_allocation(struct btrfs_fs_info *info)
2789 struct list_head *head = &info->space_info;
2790 struct btrfs_space_info *found;
2793 list_for_each_entry_rcu(found, head, list) {
2794 if (found->flags & BTRFS_BLOCK_GROUP_METADATA)
2795 found->force_alloc = 1;
2800 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
2801 struct btrfs_root *extent_root, u64 alloc_bytes,
2802 u64 flags, int force)
2804 struct btrfs_space_info *space_info;
2805 struct btrfs_fs_info *fs_info = extent_root->fs_info;
2809 mutex_lock(&fs_info->chunk_mutex);
2811 flags = btrfs_reduce_alloc_profile(extent_root, flags);
2813 space_info = __find_space_info(extent_root->fs_info, flags);
2815 ret = update_space_info(extent_root->fs_info, flags,
2819 BUG_ON(!space_info);
2821 spin_lock(&space_info->lock);
2822 if (space_info->force_alloc) {
2824 space_info->force_alloc = 0;
2826 if (space_info->full) {
2827 spin_unlock(&space_info->lock);
2831 thresh = space_info->total_bytes - space_info->bytes_readonly;
2832 thresh = div_factor(thresh, 6);
2834 (space_info->bytes_used + space_info->bytes_pinned +
2835 space_info->bytes_reserved + alloc_bytes) < thresh) {
2836 spin_unlock(&space_info->lock);
2839 spin_unlock(&space_info->lock);
2842 * if we're doing a data chunk, go ahead and make sure that
2843 * we keep a reasonable number of metadata chunks allocated in the
2846 if (flags & BTRFS_BLOCK_GROUP_DATA) {
2847 fs_info->data_chunk_allocations++;
2848 if (!(fs_info->data_chunk_allocations %
2849 fs_info->metadata_ratio))
2850 force_metadata_allocation(fs_info);
2853 ret = btrfs_alloc_chunk(trans, extent_root, flags);
2855 space_info->full = 1;
2857 mutex_unlock(&extent_root->fs_info->chunk_mutex);
2861 static int update_block_group(struct btrfs_trans_handle *trans,
2862 struct btrfs_root *root,
2863 u64 bytenr, u64 num_bytes, int alloc,
2866 struct btrfs_block_group_cache *cache;
2867 struct btrfs_fs_info *info = root->fs_info;
2868 u64 total = num_bytes;
2872 /* block accounting for super block */
2873 spin_lock(&info->delalloc_lock);
2874 old_val = btrfs_super_bytes_used(&info->super_copy);
2876 old_val += num_bytes;
2878 old_val -= num_bytes;
2879 btrfs_set_super_bytes_used(&info->super_copy, old_val);
2881 /* block accounting for root item */
2882 old_val = btrfs_root_used(&root->root_item);
2884 old_val += num_bytes;
2886 old_val -= num_bytes;
2887 btrfs_set_root_used(&root->root_item, old_val);
2888 spin_unlock(&info->delalloc_lock);
2891 cache = btrfs_lookup_block_group(info, bytenr);
2894 byte_in_group = bytenr - cache->key.objectid;
2895 WARN_ON(byte_in_group > cache->key.offset);
2897 spin_lock(&cache->space_info->lock);
2898 spin_lock(&cache->lock);
2900 old_val = btrfs_block_group_used(&cache->item);
2901 num_bytes = min(total, cache->key.offset - byte_in_group);
2903 old_val += num_bytes;
2904 cache->space_info->bytes_used += num_bytes;
2906 cache->space_info->bytes_readonly -= num_bytes;
2907 btrfs_set_block_group_used(&cache->item, old_val);
2908 spin_unlock(&cache->lock);
2909 spin_unlock(&cache->space_info->lock);
2911 old_val -= num_bytes;
2912 cache->space_info->bytes_used -= num_bytes;
2914 cache->space_info->bytes_readonly += num_bytes;
2915 btrfs_set_block_group_used(&cache->item, old_val);
2916 spin_unlock(&cache->lock);
2917 spin_unlock(&cache->space_info->lock);
2921 ret = btrfs_discard_extent(root, bytenr,
2925 ret = btrfs_add_free_space(cache, bytenr,
2930 btrfs_put_block_group(cache);
2932 bytenr += num_bytes;
2937 static u64 first_logical_byte(struct btrfs_root *root, u64 search_start)
2939 struct btrfs_block_group_cache *cache;
2942 cache = btrfs_lookup_first_block_group(root->fs_info, search_start);
2946 bytenr = cache->key.objectid;
2947 btrfs_put_block_group(cache);
2952 int btrfs_update_pinned_extents(struct btrfs_root *root,
2953 u64 bytenr, u64 num, int pin)
2956 struct btrfs_block_group_cache *cache;
2957 struct btrfs_fs_info *fs_info = root->fs_info;
2960 set_extent_dirty(&fs_info->pinned_extents,
2961 bytenr, bytenr + num - 1, GFP_NOFS);
2963 clear_extent_dirty(&fs_info->pinned_extents,
2964 bytenr, bytenr + num - 1, GFP_NOFS);
2968 cache = btrfs_lookup_block_group(fs_info, bytenr);
2970 len = min(num, cache->key.offset -
2971 (bytenr - cache->key.objectid));
2973 spin_lock(&cache->space_info->lock);
2974 spin_lock(&cache->lock);
2975 cache->pinned += len;
2976 cache->space_info->bytes_pinned += len;
2977 spin_unlock(&cache->lock);
2978 spin_unlock(&cache->space_info->lock);
2979 fs_info->total_pinned += len;
2981 spin_lock(&cache->space_info->lock);
2982 spin_lock(&cache->lock);
2983 cache->pinned -= len;
2984 cache->space_info->bytes_pinned -= len;
2985 spin_unlock(&cache->lock);
2986 spin_unlock(&cache->space_info->lock);
2987 fs_info->total_pinned -= len;
2989 btrfs_add_free_space(cache, bytenr, len);
2991 btrfs_put_block_group(cache);
2998 static int update_reserved_extents(struct btrfs_root *root,
2999 u64 bytenr, u64 num, int reserve)
3002 struct btrfs_block_group_cache *cache;
3003 struct btrfs_fs_info *fs_info = root->fs_info;
3006 cache = btrfs_lookup_block_group(fs_info, bytenr);
3008 len = min(num, cache->key.offset -
3009 (bytenr - cache->key.objectid));
3011 spin_lock(&cache->space_info->lock);
3012 spin_lock(&cache->lock);
3014 cache->reserved += len;
3015 cache->space_info->bytes_reserved += len;
3017 cache->reserved -= len;
3018 cache->space_info->bytes_reserved -= len;
3020 spin_unlock(&cache->lock);
3021 spin_unlock(&cache->space_info->lock);
3022 btrfs_put_block_group(cache);
3029 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
3034 struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
3038 ret = find_first_extent_bit(pinned_extents, last,
3039 &start, &end, EXTENT_DIRTY);
3042 set_extent_dirty(copy, start, end, GFP_NOFS);
3048 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
3049 struct btrfs_root *root,
3050 struct extent_io_tree *unpin)
3057 ret = find_first_extent_bit(unpin, 0, &start, &end,
3062 ret = btrfs_discard_extent(root, start, end + 1 - start);
3064 /* unlocks the pinned mutex */
3065 btrfs_update_pinned_extents(root, start, end + 1 - start, 0);
3066 clear_extent_dirty(unpin, start, end, GFP_NOFS);
3073 static int pin_down_bytes(struct btrfs_trans_handle *trans,
3074 struct btrfs_root *root,
3075 struct btrfs_path *path,
3076 u64 bytenr, u64 num_bytes, int is_data,
3077 struct extent_buffer **must_clean)
3080 struct extent_buffer *buf;
3085 buf = btrfs_find_tree_block(root, bytenr, num_bytes);
3089 /* we can reuse a block if it hasn't been written
3090 * and it is from this transaction. We can't
3091 * reuse anything from the tree log root because
3092 * it has tiny sub-transactions.
3094 if (btrfs_buffer_uptodate(buf, 0) &&
3095 btrfs_try_tree_lock(buf)) {
3096 u64 header_owner = btrfs_header_owner(buf);
3097 u64 header_transid = btrfs_header_generation(buf);
3098 if (header_owner != BTRFS_TREE_LOG_OBJECTID &&
3099 header_transid == trans->transid &&
3100 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
3104 btrfs_tree_unlock(buf);
3106 free_extent_buffer(buf);
3108 btrfs_set_path_blocking(path);
3109 /* unlocks the pinned mutex */
3110 btrfs_update_pinned_extents(root, bytenr, num_bytes, 1);
3117 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
3118 struct btrfs_root *root,
3119 u64 bytenr, u64 num_bytes, u64 parent,
3120 u64 root_objectid, u64 owner_objectid,
3121 u64 owner_offset, int refs_to_drop,
3122 struct btrfs_delayed_extent_op *extent_op)
3124 struct btrfs_key key;
3125 struct btrfs_path *path;
3126 struct btrfs_fs_info *info = root->fs_info;
3127 struct btrfs_root *extent_root = info->extent_root;
3128 struct extent_buffer *leaf;
3129 struct btrfs_extent_item *ei;
3130 struct btrfs_extent_inline_ref *iref;
3133 int extent_slot = 0;
3134 int found_extent = 0;
3139 path = btrfs_alloc_path();
3144 path->leave_spinning = 1;
3146 is_data = owner_objectid >= BTRFS_FIRST_FREE_OBJECTID;
3147 BUG_ON(!is_data && refs_to_drop != 1);
3149 ret = lookup_extent_backref(trans, extent_root, path, &iref,
3150 bytenr, num_bytes, parent,
3151 root_objectid, owner_objectid,
3154 extent_slot = path->slots[0];
3155 while (extent_slot >= 0) {
3156 btrfs_item_key_to_cpu(path->nodes[0], &key,
3158 if (key.objectid != bytenr)
3160 if (key.type == BTRFS_EXTENT_ITEM_KEY &&
3161 key.offset == num_bytes) {
3165 if (path->slots[0] - extent_slot > 5)
3169 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
3170 item_size = btrfs_item_size_nr(path->nodes[0], extent_slot);
3171 if (found_extent && item_size < sizeof(*ei))
3174 if (!found_extent) {
3176 ret = remove_extent_backref(trans, extent_root, path,
3180 btrfs_release_path(extent_root, path);
3181 path->leave_spinning = 1;
3183 key.objectid = bytenr;
3184 key.type = BTRFS_EXTENT_ITEM_KEY;
3185 key.offset = num_bytes;
3187 ret = btrfs_search_slot(trans, extent_root,
3190 printk(KERN_ERR "umm, got %d back from search"
3191 ", was looking for %llu\n", ret,
3192 (unsigned long long)bytenr);
3193 btrfs_print_leaf(extent_root, path->nodes[0]);
3196 extent_slot = path->slots[0];
3199 btrfs_print_leaf(extent_root, path->nodes[0]);
3201 printk(KERN_ERR "btrfs unable to find ref byte nr %llu "
3202 "parent %llu root %llu owner %llu offset %llu\n",
3203 (unsigned long long)bytenr,
3204 (unsigned long long)parent,
3205 (unsigned long long)root_objectid,
3206 (unsigned long long)owner_objectid,
3207 (unsigned long long)owner_offset);
3210 leaf = path->nodes[0];
3211 item_size = btrfs_item_size_nr(leaf, extent_slot);
3212 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
3213 if (item_size < sizeof(*ei)) {
3214 BUG_ON(found_extent || extent_slot != path->slots[0]);
3215 ret = convert_extent_item_v0(trans, extent_root, path,
3219 btrfs_release_path(extent_root, path);
3220 path->leave_spinning = 1;
3222 key.objectid = bytenr;
3223 key.type = BTRFS_EXTENT_ITEM_KEY;
3224 key.offset = num_bytes;
3226 ret = btrfs_search_slot(trans, extent_root, &key, path,
3229 printk(KERN_ERR "umm, got %d back from search"
3230 ", was looking for %llu\n", ret,
3231 (unsigned long long)bytenr);
3232 btrfs_print_leaf(extent_root, path->nodes[0]);
3235 extent_slot = path->slots[0];
3236 leaf = path->nodes[0];
3237 item_size = btrfs_item_size_nr(leaf, extent_slot);
3240 BUG_ON(item_size < sizeof(*ei));
3241 ei = btrfs_item_ptr(leaf, extent_slot,
3242 struct btrfs_extent_item);
3243 if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID) {
3244 struct btrfs_tree_block_info *bi;
3245 BUG_ON(item_size < sizeof(*ei) + sizeof(*bi));
3246 bi = (struct btrfs_tree_block_info *)(ei + 1);
3247 WARN_ON(owner_objectid != btrfs_tree_block_level(leaf, bi));
3250 refs = btrfs_extent_refs(leaf, ei);
3251 BUG_ON(refs < refs_to_drop);
3252 refs -= refs_to_drop;
3256 __run_delayed_extent_op(extent_op, leaf, ei);
3258 * In the case of inline back ref, reference count will
3259 * be updated by remove_extent_backref
3262 BUG_ON(!found_extent);
3264 btrfs_set_extent_refs(leaf, ei, refs);
3265 btrfs_mark_buffer_dirty(leaf);
3268 ret = remove_extent_backref(trans, extent_root, path,
3275 struct extent_buffer *must_clean = NULL;
3278 BUG_ON(is_data && refs_to_drop !=
3279 extent_data_ref_count(root, path, iref));
3281 BUG_ON(path->slots[0] != extent_slot);
3283 BUG_ON(path->slots[0] != extent_slot + 1);
3284 path->slots[0] = extent_slot;
3289 ret = pin_down_bytes(trans, root, path, bytenr,
3290 num_bytes, is_data, &must_clean);
3295 * it is going to be very rare for someone to be waiting
3296 * on the block we're freeing. del_items might need to
3297 * schedule, so rather than get fancy, just force it
3301 btrfs_set_lock_blocking(must_clean);
3303 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
3306 btrfs_release_path(extent_root, path);
3309 clean_tree_block(NULL, root, must_clean);
3310 btrfs_tree_unlock(must_clean);
3311 free_extent_buffer(must_clean);
3315 ret = btrfs_del_csums(trans, root, bytenr, num_bytes);
3318 invalidate_mapping_pages(info->btree_inode->i_mapping,
3319 bytenr >> PAGE_CACHE_SHIFT,
3320 (bytenr + num_bytes - 1) >> PAGE_CACHE_SHIFT);
3323 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
3327 btrfs_free_path(path);
3332 * when we free an extent, it is possible (and likely) that we free the last
3333 * delayed ref for that extent as well. This searches the delayed ref tree for
3334 * a given extent, and if there are no other delayed refs to be processed, it
3335 * removes it from the tree.
3337 static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans,
3338 struct btrfs_root *root, u64 bytenr)
3340 struct btrfs_delayed_ref_head *head;
3341 struct btrfs_delayed_ref_root *delayed_refs;
3342 struct btrfs_delayed_ref_node *ref;
3343 struct rb_node *node;
3346 delayed_refs = &trans->transaction->delayed_refs;
3347 spin_lock(&delayed_refs->lock);
3348 head = btrfs_find_delayed_ref_head(trans, bytenr);
3352 node = rb_prev(&head->node.rb_node);
3356 ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
3358 /* there are still entries for this ref, we can't drop it */
3359 if (ref->bytenr == bytenr)
3362 if (head->extent_op) {
3363 if (!head->must_insert_reserved)
3365 kfree(head->extent_op);
3366 head->extent_op = NULL;
3370 * waiting for the lock here would deadlock. If someone else has it
3371 * locked they are already in the process of dropping it anyway
3373 if (!mutex_trylock(&head->mutex))
3377 * at this point we have a head with no other entries. Go
3378 * ahead and process it.
3380 head->node.in_tree = 0;
3381 rb_erase(&head->node.rb_node, &delayed_refs->root);
3383 delayed_refs->num_entries--;
3386 * we don't take a ref on the node because we're removing it from the
3387 * tree, so we just steal the ref the tree was holding.
3389 delayed_refs->num_heads--;
3390 if (list_empty(&head->cluster))
3391 delayed_refs->num_heads_ready--;
3393 list_del_init(&head->cluster);
3394 spin_unlock(&delayed_refs->lock);
3396 ret = run_one_delayed_ref(trans, root->fs_info->tree_root,
3397 &head->node, head->extent_op,
3398 head->must_insert_reserved);
3400 btrfs_put_delayed_ref(&head->node);
3403 spin_unlock(&delayed_refs->lock);
3407 int btrfs_free_extent(struct btrfs_trans_handle *trans,
3408 struct btrfs_root *root,
3409 u64 bytenr, u64 num_bytes, u64 parent,
3410 u64 root_objectid, u64 owner, u64 offset)
3415 * tree log blocks never actually go into the extent allocation
3416 * tree, just update pinning info and exit early.
3418 if (root_objectid == BTRFS_TREE_LOG_OBJECTID) {
3419 WARN_ON(owner >= BTRFS_FIRST_FREE_OBJECTID);
3420 /* unlocks the pinned mutex */
3421 btrfs_update_pinned_extents(root, bytenr, num_bytes, 1);
3422 update_reserved_extents(root, bytenr, num_bytes, 0);
3424 } else if (owner < BTRFS_FIRST_FREE_OBJECTID) {
3425 ret = btrfs_add_delayed_tree_ref(trans, bytenr, num_bytes,
3426 parent, root_objectid, (int)owner,
3427 BTRFS_DROP_DELAYED_REF, NULL);
3429 ret = check_ref_cleanup(trans, root, bytenr);
3432 ret = btrfs_add_delayed_data_ref(trans, bytenr, num_bytes,
3433 parent, root_objectid, owner,
3434 offset, BTRFS_DROP_DELAYED_REF, NULL);
3440 static u64 stripe_align(struct btrfs_root *root, u64 val)
3442 u64 mask = ((u64)root->stripesize - 1);
3443 u64 ret = (val + mask) & ~mask;
3448 * walks the btree of allocated extents and find a hole of a given size.
3449 * The key ins is changed to record the hole:
3450 * ins->objectid == block start
3451 * ins->flags = BTRFS_EXTENT_ITEM_KEY
3452 * ins->offset == number of blocks
3453 * Any available blocks before search_start are skipped.
3455 static noinline int find_free_extent(struct btrfs_trans_handle *trans,
3456 struct btrfs_root *orig_root,
3457 u64 num_bytes, u64 empty_size,
3458 u64 search_start, u64 search_end,
3459 u64 hint_byte, struct btrfs_key *ins,
3460 u64 exclude_start, u64 exclude_nr,
3464 struct btrfs_root *root = orig_root->fs_info->extent_root;
3465 struct btrfs_free_cluster *last_ptr = NULL;
3466 struct btrfs_block_group_cache *block_group = NULL;
3467 int empty_cluster = 2 * 1024 * 1024;
3468 int allowed_chunk_alloc = 0;
3469 struct btrfs_space_info *space_info;
3470 int last_ptr_loop = 0;
3473 WARN_ON(num_bytes < root->sectorsize);
3474 btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
3478 space_info = __find_space_info(root->fs_info, data);
3480 if (orig_root->ref_cows || empty_size)
3481 allowed_chunk_alloc = 1;
3483 if (data & BTRFS_BLOCK_GROUP_METADATA) {
3484 last_ptr = &root->fs_info->meta_alloc_cluster;
3485 if (!btrfs_test_opt(root, SSD))
3486 empty_cluster = 64 * 1024;
3489 if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD)) {
3490 last_ptr = &root->fs_info->data_alloc_cluster;
3494 spin_lock(&last_ptr->lock);
3495 if (last_ptr->block_group)
3496 hint_byte = last_ptr->window_start;
3497 spin_unlock(&last_ptr->lock);
3500 search_start = max(search_start, first_logical_byte(root, 0));
3501 search_start = max(search_start, hint_byte);
3508 if (search_start == hint_byte) {
3509 block_group = btrfs_lookup_block_group(root->fs_info,
3511 if (block_group && block_group_bits(block_group, data)) {
3512 down_read(&space_info->groups_sem);
3513 if (list_empty(&block_group->list) ||
3516 * someone is removing this block group,
3517 * we can't jump into the have_block_group
3518 * target because our list pointers are not
3521 btrfs_put_block_group(block_group);
3522 up_read(&space_info->groups_sem);
3524 goto have_block_group;
3525 } else if (block_group) {
3526 btrfs_put_block_group(block_group);
3531 down_read(&space_info->groups_sem);
3532 list_for_each_entry(block_group, &space_info->block_groups, list) {
3535 atomic_inc(&block_group->count);
3536 search_start = block_group->key.objectid;
3539 if (unlikely(!block_group->cached)) {
3540 mutex_lock(&block_group->cache_mutex);
3541 ret = cache_block_group(root, block_group);
3542 mutex_unlock(&block_group->cache_mutex);
3544 btrfs_put_block_group(block_group);
3549 if (unlikely(block_group->ro))
3554 * the refill lock keeps out other
3555 * people trying to start a new cluster
3557 spin_lock(&last_ptr->refill_lock);
3558 if (last_ptr->block_group &&
3559 (last_ptr->block_group->ro ||
3560 !block_group_bits(last_ptr->block_group, data))) {
3562 goto refill_cluster;
3565 offset = btrfs_alloc_from_cluster(block_group, last_ptr,
3566 num_bytes, search_start);
3568 /* we have a block, we're done */
3569 spin_unlock(&last_ptr->refill_lock);
3573 spin_lock(&last_ptr->lock);
3575 * whoops, this cluster doesn't actually point to
3576 * this block group. Get a ref on the block
3577 * group is does point to and try again
3579 if (!last_ptr_loop && last_ptr->block_group &&
3580 last_ptr->block_group != block_group) {
3582 btrfs_put_block_group(block_group);
3583 block_group = last_ptr->block_group;
3584 atomic_inc(&block_group->count);
3585 spin_unlock(&last_ptr->lock);
3586 spin_unlock(&last_ptr->refill_lock);
3589 search_start = block_group->key.objectid;
3591 * we know this block group is properly
3592 * in the list because
3593 * btrfs_remove_block_group, drops the
3594 * cluster before it removes the block
3595 * group from the list
3597 goto have_block_group;
3599 spin_unlock(&last_ptr->lock);
3602 * this cluster didn't work out, free it and
3605 btrfs_return_cluster_to_free_space(NULL, last_ptr);
3609 /* allocate a cluster in this block group */
3610 ret = btrfs_find_space_cluster(trans, root,
3611 block_group, last_ptr,
3613 empty_cluster + empty_size);
3616 * now pull our allocation out of this
3619 offset = btrfs_alloc_from_cluster(block_group,
3620 last_ptr, num_bytes,
3623 /* we found one, proceed */
3624 spin_unlock(&last_ptr->refill_lock);
3629 * at this point we either didn't find a cluster
3630 * or we weren't able to allocate a block from our
3631 * cluster. Free the cluster we've been trying
3632 * to use, and go to the next block group
3635 btrfs_return_cluster_to_free_space(NULL,
3637 spin_unlock(&last_ptr->refill_lock);
3640 spin_unlock(&last_ptr->refill_lock);
3643 offset = btrfs_find_space_for_alloc(block_group, search_start,
3644 num_bytes, empty_size);
3648 search_start = stripe_align(root, offset);
3650 /* move on to the next group */
3651 if (search_start + num_bytes >= search_end) {
3652 btrfs_add_free_space(block_group, offset, num_bytes);
3656 /* move on to the next group */
3657 if (search_start + num_bytes >
3658 block_group->key.objectid + block_group->key.offset) {
3659 btrfs_add_free_space(block_group, offset, num_bytes);
3663 if (exclude_nr > 0 &&
3664 (search_start + num_bytes > exclude_start &&
3665 search_start < exclude_start + exclude_nr)) {
3666 search_start = exclude_start + exclude_nr;
3668 btrfs_add_free_space(block_group, offset, num_bytes);
3670 * if search_start is still in this block group
3671 * then we just re-search this block group
3673 if (search_start >= block_group->key.objectid &&
3674 search_start < (block_group->key.objectid +
3675 block_group->key.offset))
3676 goto have_block_group;
3680 ins->objectid = search_start;
3681 ins->offset = num_bytes;
3683 if (offset < search_start)
3684 btrfs_add_free_space(block_group, offset,
3685 search_start - offset);
3686 BUG_ON(offset > search_start);
3688 /* we are all good, lets return */
3691 btrfs_put_block_group(block_group);
3693 up_read(&space_info->groups_sem);
3695 /* loop == 0, try to find a clustered alloc in every block group
3696 * loop == 1, try again after forcing a chunk allocation
3697 * loop == 2, set empty_size and empty_cluster to 0 and try again
3699 if (!ins->objectid && loop < 3 &&
3700 (empty_size || empty_cluster || allowed_chunk_alloc)) {
3706 if (allowed_chunk_alloc) {
3707 ret = do_chunk_alloc(trans, root, num_bytes +
3708 2 * 1024 * 1024, data, 1);
3709 allowed_chunk_alloc = 0;
3711 space_info->force_alloc = 1;
3719 } else if (!ins->objectid) {
3723 /* we found what we needed */
3724 if (ins->objectid) {
3725 if (!(data & BTRFS_BLOCK_GROUP_DATA))
3726 trans->block_group = block_group->key.objectid;
3728 btrfs_put_block_group(block_group);
3735 static void dump_space_info(struct btrfs_space_info *info, u64 bytes)
3737 struct btrfs_block_group_cache *cache;
3739 printk(KERN_INFO "space_info has %llu free, is %sfull\n",
3740 (unsigned long long)(info->total_bytes - info->bytes_used -
3741 info->bytes_pinned - info->bytes_reserved),
3742 (info->full) ? "" : "not ");
3743 printk(KERN_INFO "space_info total=%llu, pinned=%llu, delalloc=%llu,"
3744 " may_use=%llu, used=%llu\n",
3745 (unsigned long long)info->total_bytes,
3746 (unsigned long long)info->bytes_pinned,
3747 (unsigned long long)info->bytes_delalloc,
3748 (unsigned long long)info->bytes_may_use,
3749 (unsigned long long)info->bytes_used);
3751 down_read(&info->groups_sem);
3752 list_for_each_entry(cache, &info->block_groups, list) {
3753 spin_lock(&cache->lock);
3754 printk(KERN_INFO "block group %llu has %llu bytes, %llu used "
3755 "%llu pinned %llu reserved\n",
3756 (unsigned long long)cache->key.objectid,
3757 (unsigned long long)cache->key.offset,
3758 (unsigned long long)btrfs_block_group_used(&cache->item),
3759 (unsigned long long)cache->pinned,
3760 (unsigned long long)cache->reserved);
3761 btrfs_dump_free_space(cache, bytes);
3762 spin_unlock(&cache->lock);
3764 up_read(&info->groups_sem);
3767 static int __btrfs_reserve_extent(struct btrfs_trans_handle *trans,
3768 struct btrfs_root *root,
3769 u64 num_bytes, u64 min_alloc_size,
3770 u64 empty_size, u64 hint_byte,
3771 u64 search_end, struct btrfs_key *ins,
3775 u64 search_start = 0;
3776 struct btrfs_fs_info *info = root->fs_info;
3778 data = btrfs_get_alloc_profile(root, data);
3781 * the only place that sets empty_size is btrfs_realloc_node, which
3782 * is not called recursively on allocations
3784 if (empty_size || root->ref_cows) {
3785 if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
3786 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
3788 BTRFS_BLOCK_GROUP_METADATA |
3789 (info->metadata_alloc_profile &
3790 info->avail_metadata_alloc_bits), 0);
3792 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
3793 num_bytes + 2 * 1024 * 1024, data, 0);
3796 WARN_ON(num_bytes < root->sectorsize);
3797 ret = find_free_extent(trans, root, num_bytes, empty_size,
3798 search_start, search_end, hint_byte, ins,
3799 trans->alloc_exclude_start,
3800 trans->alloc_exclude_nr, data);
3802 if (ret == -ENOSPC && num_bytes > min_alloc_size) {
3803 num_bytes = num_bytes >> 1;
3804 num_bytes = num_bytes & ~(root->sectorsize - 1);
3805 num_bytes = max(num_bytes, min_alloc_size);
3806 do_chunk_alloc(trans, root->fs_info->extent_root,
3807 num_bytes, data, 1);
3811 struct btrfs_space_info *sinfo;
3813 sinfo = __find_space_info(root->fs_info, data);
3814 printk(KERN_ERR "btrfs allocation failed flags %llu, "
3815 "wanted %llu\n", (unsigned long long)data,
3816 (unsigned long long)num_bytes);
3817 dump_space_info(sinfo, num_bytes);
3824 int btrfs_free_reserved_extent(struct btrfs_root *root, u64 start, u64 len)
3826 struct btrfs_block_group_cache *cache;
3829 cache = btrfs_lookup_block_group(root->fs_info, start);
3831 printk(KERN_ERR "Unable to find block group for %llu\n",
3832 (unsigned long long)start);
3836 ret = btrfs_discard_extent(root, start, len);
3838 btrfs_add_free_space(cache, start, len);
3839 btrfs_put_block_group(cache);
3840 update_reserved_extents(root, start, len, 0);
3845 int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
3846 struct btrfs_root *root,
3847 u64 num_bytes, u64 min_alloc_size,
3848 u64 empty_size, u64 hint_byte,
3849 u64 search_end, struct btrfs_key *ins,
3853 ret = __btrfs_reserve_extent(trans, root, num_bytes, min_alloc_size,
3854 empty_size, hint_byte, search_end, ins,
3856 update_reserved_extents(root, ins->objectid, ins->offset, 1);
3860 static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
3861 struct btrfs_root *root,
3862 u64 parent, u64 root_objectid,
3863 u64 flags, u64 owner, u64 offset,
3864 struct btrfs_key *ins, int ref_mod)
3867 struct btrfs_fs_info *fs_info = root->fs_info;
3868 struct btrfs_extent_item *extent_item;
3869 struct btrfs_extent_inline_ref *iref;
3870 struct btrfs_path *path;
3871 struct extent_buffer *leaf;
3876 type = BTRFS_SHARED_DATA_REF_KEY;
3878 type = BTRFS_EXTENT_DATA_REF_KEY;
3880 size = sizeof(*extent_item) + btrfs_extent_inline_ref_size(type);
3882 path = btrfs_alloc_path();
3885 path->leave_spinning = 1;
3886 ret = btrfs_insert_empty_item(trans, fs_info->extent_root, path,
3890 leaf = path->nodes[0];
3891 extent_item = btrfs_item_ptr(leaf, path->slots[0],
3892 struct btrfs_extent_item);
3893 btrfs_set_extent_refs(leaf, extent_item, ref_mod);
3894 btrfs_set_extent_generation(leaf, extent_item, trans->transid);
3895 btrfs_set_extent_flags(leaf, extent_item,
3896 flags | BTRFS_EXTENT_FLAG_DATA);
3898 iref = (struct btrfs_extent_inline_ref *)(extent_item + 1);
3899 btrfs_set_extent_inline_ref_type(leaf, iref, type);
3901 struct btrfs_shared_data_ref *ref;
3902 ref = (struct btrfs_shared_data_ref *)(iref + 1);
3903 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
3904 btrfs_set_shared_data_ref_count(leaf, ref, ref_mod);
3906 struct btrfs_extent_data_ref *ref;
3907 ref = (struct btrfs_extent_data_ref *)(&iref->offset);
3908 btrfs_set_extent_data_ref_root(leaf, ref, root_objectid);
3909 btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
3910 btrfs_set_extent_data_ref_offset(leaf, ref, offset);
3911 btrfs_set_extent_data_ref_count(leaf, ref, ref_mod);
3914 btrfs_mark_buffer_dirty(path->nodes[0]);
3915 btrfs_free_path(path);
3917 ret = update_block_group(trans, root, ins->objectid, ins->offset,
3920 printk(KERN_ERR "btrfs update block group failed for %llu "
3921 "%llu\n", (unsigned long long)ins->objectid,
3922 (unsigned long long)ins->offset);
3928 static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
3929 struct btrfs_root *root,
3930 u64 parent, u64 root_objectid,
3931 u64 flags, struct btrfs_disk_key *key,
3932 int level, struct btrfs_key *ins)
3935 struct btrfs_fs_info *fs_info = root->fs_info;
3936 struct btrfs_extent_item *extent_item;
3937 struct btrfs_tree_block_info *block_info;
3938 struct btrfs_extent_inline_ref *iref;
3939 struct btrfs_path *path;
3940 struct extent_buffer *leaf;
3941 u32 size = sizeof(*extent_item) + sizeof(*block_info) + sizeof(*iref);
3943 path = btrfs_alloc_path();
3946 path->leave_spinning = 1;
3947 ret = btrfs_insert_empty_item(trans, fs_info->extent_root, path,
3951 leaf = path->nodes[0];
3952 extent_item = btrfs_item_ptr(leaf, path->slots[0],
3953 struct btrfs_extent_item);
3954 btrfs_set_extent_refs(leaf, extent_item, 1);
3955 btrfs_set_extent_generation(leaf, extent_item, trans->transid);
3956 btrfs_set_extent_flags(leaf, extent_item,
3957 flags | BTRFS_EXTENT_FLAG_TREE_BLOCK);
3958 block_info = (struct btrfs_tree_block_info *)(extent_item + 1);
3960 btrfs_set_tree_block_key(leaf, block_info, key);
3961 btrfs_set_tree_block_level(leaf, block_info, level);
3963 iref = (struct btrfs_extent_inline_ref *)(block_info + 1);
3965 BUG_ON(!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
3966 btrfs_set_extent_inline_ref_type(leaf, iref,
3967 BTRFS_SHARED_BLOCK_REF_KEY);
3968 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
3970 btrfs_set_extent_inline_ref_type(leaf, iref,
3971 BTRFS_TREE_BLOCK_REF_KEY);
3972 btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
3975 btrfs_mark_buffer_dirty(leaf);
3976 btrfs_free_path(path);
3978 ret = update_block_group(trans, root, ins->objectid, ins->offset,
3981 printk(KERN_ERR "btrfs update block group failed for %llu "
3982 "%llu\n", (unsigned long long)ins->objectid,
3983 (unsigned long long)ins->offset);
3989 int btrfs_alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
3990 struct btrfs_root *root,
3991 u64 root_objectid, u64 owner,
3992 u64 offset, struct btrfs_key *ins)
3996 BUG_ON(root_objectid == BTRFS_TREE_LOG_OBJECTID);
3998 ret = btrfs_add_delayed_data_ref(trans, ins->objectid, ins->offset,
3999 0, root_objectid, owner, offset,
4000 BTRFS_ADD_DELAYED_EXTENT, NULL);
4005 * this is used by the tree logging recovery code. It records that
4006 * an extent has been allocated and makes sure to clear the free
4007 * space cache bits as well
4009 int btrfs_alloc_logged_file_extent(struct btrfs_trans_handle *trans,
4010 struct btrfs_root *root,
4011 u64 root_objectid, u64 owner, u64 offset,
4012 struct btrfs_key *ins)
4015 struct btrfs_block_group_cache *block_group;
4017 block_group = btrfs_lookup_block_group(root->fs_info, ins->objectid);
4018 mutex_lock(&block_group->cache_mutex);
4019 cache_block_group(root, block_group);
4020 mutex_unlock(&block_group->cache_mutex);
4022 ret = btrfs_remove_free_space(block_group, ins->objectid,
4025 btrfs_put_block_group(block_group);
4026 ret = alloc_reserved_file_extent(trans, root, 0, root_objectid,
4027 0, owner, offset, ins, 1);
4032 * finds a free extent and does all the dirty work required for allocation
4033 * returns the key for the extent through ins, and a tree buffer for
4034 * the first block of the extent through buf.
4036 * returns 0 if everything worked, non-zero otherwise.
4038 static int alloc_tree_block(struct btrfs_trans_handle *trans,
4039 struct btrfs_root *root,
4040 u64 num_bytes, u64 parent, u64 root_objectid,
4041 struct btrfs_disk_key *key, int level,
4042 u64 empty_size, u64 hint_byte, u64 search_end,
4043 struct btrfs_key *ins)
4048 ret = __btrfs_reserve_extent(trans, root, num_bytes, num_bytes,
4049 empty_size, hint_byte, search_end,
4053 if (root_objectid == BTRFS_TREE_RELOC_OBJECTID) {
4055 parent = ins->objectid;
4056 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
4060 update_reserved_extents(root, ins->objectid, ins->offset, 1);
4061 if (root_objectid != BTRFS_TREE_LOG_OBJECTID) {
4062 struct btrfs_delayed_extent_op *extent_op;
4063 extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
4066 memcpy(&extent_op->key, key, sizeof(extent_op->key));
4068 memset(&extent_op->key, 0, sizeof(extent_op->key));
4069 extent_op->flags_to_set = flags;
4070 extent_op->update_key = 1;
4071 extent_op->update_flags = 1;
4072 extent_op->is_data = 0;
4074 ret = btrfs_add_delayed_tree_ref(trans, ins->objectid,
4075 ins->offset, parent, root_objectid,
4076 level, BTRFS_ADD_DELAYED_EXTENT,
4083 struct extent_buffer *btrfs_init_new_buffer(struct btrfs_trans_handle *trans,
4084 struct btrfs_root *root,
4085 u64 bytenr, u32 blocksize,
4088 struct extent_buffer *buf;
4090 buf = btrfs_find_create_tree_block(root, bytenr, blocksize);
4092 return ERR_PTR(-ENOMEM);
4093 btrfs_set_header_generation(buf, trans->transid);
4094 btrfs_set_buffer_lockdep_class(buf, level);
4095 btrfs_tree_lock(buf);
4096 clean_tree_block(trans, root, buf);
4098 btrfs_set_lock_blocking(buf);
4099 btrfs_set_buffer_uptodate(buf);
4101 if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID) {
4102 set_extent_dirty(&root->dirty_log_pages, buf->start,
4103 buf->start + buf->len - 1, GFP_NOFS);
4105 set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
4106 buf->start + buf->len - 1, GFP_NOFS);
4108 trans->blocks_used++;
4109 /* this returns a buffer locked for blocking */
4114 * helper function to allocate a block for a given tree
4115 * returns the tree buffer or NULL.
4117 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
4118 struct btrfs_root *root, u32 blocksize,
4119 u64 parent, u64 root_objectid,
4120 struct btrfs_disk_key *key, int level,
4121 u64 hint, u64 empty_size)
4123 struct btrfs_key ins;
4125 struct extent_buffer *buf;
4127 ret = alloc_tree_block(trans, root, blocksize, parent, root_objectid,
4128 key, level, empty_size, hint, (u64)-1, &ins);
4131 return ERR_PTR(ret);
4134 buf = btrfs_init_new_buffer(trans, root, ins.objectid,
4139 int btrfs_drop_leaf_ref(struct btrfs_trans_handle *trans,
4140 struct btrfs_root *root, struct extent_buffer *leaf)
4144 struct btrfs_key key;
4145 struct btrfs_file_extent_item *fi;
4150 BUG_ON(!btrfs_is_leaf(leaf));
4151 nritems = btrfs_header_nritems(leaf);
4153 for (i = 0; i < nritems; i++) {
4155 btrfs_item_key_to_cpu(leaf, &key, i);
4157 /* only extents have references, skip everything else */
4158 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
4161 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
4163 /* inline extents live in the btree, they don't have refs */
4164 if (btrfs_file_extent_type(leaf, fi) ==
4165 BTRFS_FILE_EXTENT_INLINE)
4168 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
4170 /* holes don't have refs */
4171 if (disk_bytenr == 0)
4174 num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
4175 ret = btrfs_free_extent(trans, root, disk_bytenr, num_bytes,
4176 leaf->start, 0, key.objectid, 0);
4184 static noinline int cache_drop_leaf_ref(struct btrfs_trans_handle *trans,
4185 struct btrfs_root *root,
4186 struct btrfs_leaf_ref *ref)
4190 struct btrfs_extent_info *info;
4191 struct refsort *sorted;
4193 if (ref->nritems == 0)
4196 sorted = kmalloc(sizeof(*sorted) * ref->nritems, GFP_NOFS);
4197 for (i = 0; i < ref->nritems; i++) {
4198 sorted[i].bytenr = ref->extents[i].bytenr;
4201 sort(sorted, ref->nritems, sizeof(struct refsort), refsort_cmp, NULL);
4204 * the items in the ref were sorted when the ref was inserted
4205 * into the ref cache, so this is already in order
4207 for (i = 0; i < ref->nritems; i++) {
4208 info = ref->extents + sorted[i].slot;
4209 ret = btrfs_free_extent(trans, root, info->bytenr,
4210 info->num_bytes, ref->bytenr,
4211 ref->owner, ref->generation,
4214 atomic_inc(&root->fs_info->throttle_gen);
4215 wake_up(&root->fs_info->transaction_throttle);
4227 static int drop_snap_lookup_refcount(struct btrfs_trans_handle *trans,
4228 struct btrfs_root *root, u64 start,
4233 ret = btrfs_lookup_extent_refs(trans, root, start, len, refs);
4236 #if 0 /* some debugging code in case we see problems here */
4237 /* if the refs count is one, it won't get increased again. But
4238 * if the ref count is > 1, someone may be decreasing it at
4239 * the same time we are.
4242 struct extent_buffer *eb = NULL;
4243 eb = btrfs_find_create_tree_block(root, start, len);
4245 btrfs_tree_lock(eb);
4247 mutex_lock(&root->fs_info->alloc_mutex);
4248 ret = lookup_extent_ref(NULL, root, start, len, refs);
4250 mutex_unlock(&root->fs_info->alloc_mutex);
4253 btrfs_tree_unlock(eb);
4254 free_extent_buffer(eb);
4257 printk(KERN_ERR "btrfs block %llu went down to one "
4258 "during drop_snap\n", (unsigned long long)start);
4270 * this is used while deleting old snapshots, and it drops the refs
4271 * on a whole subtree starting from a level 1 node.
4273 * The idea is to sort all the leaf pointers, and then drop the
4274 * ref on all the leaves in order. Most of the time the leaves
4275 * will have ref cache entries, so no leaf IOs will be required to
4276 * find the extents they have references on.
4278 * For each leaf, any references it has are also dropped in order
4280 * This ends up dropping the references in something close to optimal
4281 * order for reading and modifying the extent allocation tree.
4283 static noinline int drop_level_one_refs(struct btrfs_trans_handle *trans,
4284 struct btrfs_root *root,
4285 struct btrfs_path *path)
4290 struct extent_buffer *eb = path->nodes[1];
4291 struct extent_buffer *leaf;
4292 struct btrfs_leaf_ref *ref;
4293 struct refsort *sorted = NULL;
4294 int nritems = btrfs_header_nritems(eb);
4298 int slot = path->slots[1];
4299 u32 blocksize = btrfs_level_size(root, 0);
4305 root_owner = btrfs_header_owner(eb);
4306 root_gen = btrfs_header_generation(eb);
4307 sorted = kmalloc(sizeof(*sorted) * nritems, GFP_NOFS);
4310 * step one, sort all the leaf pointers so we don't scribble
4311 * randomly into the extent allocation tree
4313 for (i = slot; i < nritems; i++) {
4314 sorted[refi].bytenr = btrfs_node_blockptr(eb, i);
4315 sorted[refi].slot = i;
4320 * nritems won't be zero, but if we're picking up drop_snapshot
4321 * after a crash, slot might be > 0, so double check things
4327 sort(sorted, refi, sizeof(struct refsort), refsort_cmp, NULL);
4330 * the first loop frees everything the leaves point to
4332 for (i = 0; i < refi; i++) {
4335 bytenr = sorted[i].bytenr;
4338 * check the reference count on this leaf. If it is > 1
4339 * we just decrement it below and don't update any
4340 * of the refs the leaf points to.
4342 ret = drop_snap_lookup_refcount(trans, root, bytenr,
4348 ptr_gen = btrfs_node_ptr_generation(eb, sorted[i].slot);
4351 * the leaf only had one reference, which means the
4352 * only thing pointing to this leaf is the snapshot
4353 * we're deleting. It isn't possible for the reference
4354 * count to increase again later
4356 * The reference cache is checked for the leaf,
4357 * and if found we'll be able to drop any refs held by
4358 * the leaf without needing to read it in.
4360 ref = btrfs_lookup_leaf_ref(root, bytenr);
4361 if (ref && ref->generation != ptr_gen) {
4362 btrfs_free_leaf_ref(root, ref);
4366 ret = cache_drop_leaf_ref(trans, root, ref);
4368 btrfs_remove_leaf_ref(root, ref);
4369 btrfs_free_leaf_ref(root, ref);
4372 * the leaf wasn't in the reference cache, so
4373 * we have to read it.
4375 leaf = read_tree_block(root, bytenr, blocksize,
4377 ret = btrfs_drop_leaf_ref(trans, root, leaf);
4379 free_extent_buffer(leaf);
4381 atomic_inc(&root->fs_info->throttle_gen);
4382 wake_up(&root->fs_info->transaction_throttle);
4387 * run through the loop again to free the refs on the leaves.
4388 * This is faster than doing it in the loop above because
4389 * the leaves are likely to be clustered together. We end up
4390 * working in nice chunks on the extent allocation tree.
4392 for (i = 0; i < refi; i++) {
4393 bytenr = sorted[i].bytenr;
4394 ret = btrfs_free_extent(trans, root, bytenr,
4395 blocksize, eb->start,
4396 root_owner, root_gen, 0, 1);
4399 atomic_inc(&root->fs_info->throttle_gen);
4400 wake_up(&root->fs_info->transaction_throttle);
4407 * update the path to show we've processed the entire level 1
4408 * node. This will get saved into the root's drop_snapshot_progress
4409 * field so these drops are not repeated again if this transaction
4412 path->slots[1] = nritems;
4417 * helper function for drop_snapshot, this walks down the tree dropping ref
4418 * counts as it goes.
4420 static noinline int walk_down_tree(struct btrfs_trans_handle *trans,
4421 struct btrfs_root *root,
4422 struct btrfs_path *path, int *level)
4428 struct extent_buffer *next;
4429 struct extent_buffer *cur;
4430 struct extent_buffer *parent;
4435 WARN_ON(*level < 0);
4436 WARN_ON(*level >= BTRFS_MAX_LEVEL);
4437 ret = drop_snap_lookup_refcount(trans, root, path->nodes[*level]->start,
4438 path->nodes[*level]->len, &refs);
4444 * walk down to the last node level and free all the leaves
4446 while (*level >= 0) {
4447 WARN_ON(*level < 0);
4448 WARN_ON(*level >= BTRFS_MAX_LEVEL);
4449 cur = path->nodes[*level];
4451 if (btrfs_header_level(cur) != *level)
4454 if (path->slots[*level] >=
4455 btrfs_header_nritems(cur))
4458 /* the new code goes down to level 1 and does all the
4459 * leaves pointed to that node in bulk. So, this check
4460 * for level 0 will always be false.
4462 * But, the disk format allows the drop_snapshot_progress
4463 * field in the root to leave things in a state where
4464 * a leaf will need cleaning up here. If someone crashes
4465 * with the old code and then boots with the new code,
4466 * we might find a leaf here.
4469 ret = btrfs_drop_leaf_ref(trans, root, cur);
4475 * once we get to level one, process the whole node
4476 * at once, including everything below it.
4479 ret = drop_level_one_refs(trans, root, path);
4484 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
4485 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
4486 blocksize = btrfs_level_size(root, *level - 1);
4488 ret = drop_snap_lookup_refcount(trans, root, bytenr,
4493 * if there is more than one reference, we don't need
4494 * to read that node to drop any references it has. We
4495 * just drop the ref we hold on that node and move on to the
4496 * next slot in this level.
4499 parent = path->nodes[*level];
4500 root_owner = btrfs_header_owner(parent);
4501 root_gen = btrfs_header_generation(parent);
4502 path->slots[*level]++;
4504 ret = btrfs_free_extent(trans, root, bytenr,
4505 blocksize, parent->start,
4506 root_owner, root_gen,
4510 atomic_inc(&root->fs_info->throttle_gen);
4511 wake_up(&root->fs_info->transaction_throttle);
4518 * we need to keep freeing things in the next level down.
4519 * read the block and loop around to process it
4521 next = read_tree_block(root, bytenr, blocksize, ptr_gen);
4522 WARN_ON(*level <= 0);
4523 if (path->nodes[*level-1])
4524 free_extent_buffer(path->nodes[*level-1]);
4525 path->nodes[*level-1] = next;
4526 *level = btrfs_header_level(next);
4527 path->slots[*level] = 0;
4531 WARN_ON(*level < 0);
4532 WARN_ON(*level >= BTRFS_MAX_LEVEL);
4534 if (path->nodes[*level] == root->node) {
4535 parent = path->nodes[*level];
4536 bytenr = path->nodes[*level]->start;
4538 parent = path->nodes[*level + 1];
4539 bytenr = btrfs_node_blockptr(parent, path->slots[*level + 1]);
4542 blocksize = btrfs_level_size(root, *level);
4543 root_owner = btrfs_header_owner(parent);
4544 root_gen = btrfs_header_generation(parent);
4547 * cleanup and free the reference on the last node
4550 ret = btrfs_free_extent(trans, root, bytenr, blocksize,
4551 parent->start, root_owner, root_gen,
4553 free_extent_buffer(path->nodes[*level]);
4554 path->nodes[*level] = NULL;
4565 * helper function for drop_subtree, this function is similar to
4566 * walk_down_tree. The main difference is that it checks reference
4567 * counts while tree blocks are locked.
4569 static noinline int walk_down_tree(struct btrfs_trans_handle *trans,
4570 struct btrfs_root *root,
4571 struct btrfs_path *path, int *level)
4573 struct extent_buffer *next;
4574 struct extent_buffer *cur;
4575 struct extent_buffer *parent;
4583 cur = path->nodes[*level];
4584 ret = btrfs_lookup_extent_info(trans, root, cur->start, cur->len,
4590 BUG_ON(!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
4592 while (*level >= 0) {
4593 cur = path->nodes[*level];
4595 ret = btrfs_drop_leaf_ref(trans, root, cur);
4597 clean_tree_block(trans, root, cur);
4600 if (path->slots[*level] >= btrfs_header_nritems(cur)) {
4601 clean_tree_block(trans, root, cur);
4605 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
4606 blocksize = btrfs_level_size(root, *level - 1);
4607 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
4609 next = read_tree_block(root, bytenr, blocksize, ptr_gen);
4610 btrfs_tree_lock(next);
4611 btrfs_set_lock_blocking(next);
4613 ret = btrfs_lookup_extent_info(trans, root, bytenr, blocksize,
4617 parent = path->nodes[*level];
4618 ret = btrfs_free_extent(trans, root, bytenr,
4619 blocksize, parent->start,
4620 btrfs_header_owner(parent),
4623 path->slots[*level]++;
4624 btrfs_tree_unlock(next);
4625 free_extent_buffer(next);
4629 BUG_ON(!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
4631 *level = btrfs_header_level(next);
4632 path->nodes[*level] = next;
4633 path->slots[*level] = 0;
4634 path->locks[*level] = 1;
4638 if (path->nodes[*level] == root->node)
4639 parent = path->nodes[*level];
4641 parent = path->nodes[*level + 1];
4642 bytenr = path->nodes[*level]->start;
4643 blocksize = path->nodes[*level]->len;
4645 ret = btrfs_free_extent(trans, root, bytenr, blocksize, parent->start,
4646 btrfs_header_owner(parent), *level, 0);
4649 if (path->locks[*level]) {
4650 btrfs_tree_unlock(path->nodes[*level]);
4651 path->locks[*level] = 0;
4653 free_extent_buffer(path->nodes[*level]);
4654 path->nodes[*level] = NULL;
4661 * helper for dropping snapshots. This walks back up the tree in the path
4662 * to find the first node higher up where we haven't yet gone through
4665 static noinline int walk_up_tree(struct btrfs_trans_handle *trans,
4666 struct btrfs_root *root,
4667 struct btrfs_path *path,
4668 int *level, int max_level)
4670 struct btrfs_root_item *root_item = &root->root_item;
4675 for (i = *level; i < max_level && path->nodes[i]; i++) {
4676 slot = path->slots[i];
4677 if (slot + 1 < btrfs_header_nritems(path->nodes[i])) {
4679 * there is more work to do in this level.
4680 * Update the drop_progress marker to reflect
4681 * the work we've done so far, and then bump
4685 WARN_ON(*level == 0);
4686 if (max_level == BTRFS_MAX_LEVEL) {
4687 btrfs_node_key(path->nodes[i],
4688 &root_item->drop_progress,
4690 root_item->drop_level = i;
4695 struct extent_buffer *parent;
4698 * this whole node is done, free our reference
4699 * on it and go up one level
4701 if (path->nodes[*level] == root->node)
4702 parent = path->nodes[*level];
4704 parent = path->nodes[*level + 1];
4706 clean_tree_block(trans, root, path->nodes[i]);
4707 ret = btrfs_free_extent(trans, root,
4708 path->nodes[i]->start,
4709 path->nodes[i]->len,
4711 btrfs_header_owner(parent),
4714 if (path->locks[*level]) {
4715 btrfs_tree_unlock(path->nodes[i]);
4718 free_extent_buffer(path->nodes[i]);
4719 path->nodes[i] = NULL;
4727 * drop the reference count on the tree rooted at 'snap'. This traverses
4728 * the tree freeing any blocks that have a ref count of zero after being
4731 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
4737 struct btrfs_path *path;
4739 struct btrfs_root_item *root_item = &root->root_item;
4741 path = btrfs_alloc_path();
4744 level = btrfs_header_level(root->node);
4745 if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
4746 path->nodes[level] = btrfs_lock_root_node(root);
4747 btrfs_set_lock_blocking(path->nodes[level]);
4748 path->slots[level] = 0;
4749 path->locks[level] = 1;
4751 struct btrfs_key key;
4752 struct btrfs_disk_key found_key;
4753 struct extent_buffer *node;
4755 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
4756 level = root_item->drop_level;
4757 path->lowest_level = level;
4758 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4763 node = path->nodes[level];
4764 btrfs_node_key(node, &found_key, path->slots[level]);
4765 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
4766 sizeof(found_key)));
4768 * unlock our path, this is safe because only this
4769 * function is allowed to delete this snapshot
4771 btrfs_unlock_up_safe(path, 0);
4774 unsigned long update;
4775 wret = walk_down_tree(trans, root, path, &level);
4781 wret = walk_up_tree(trans, root, path, &level,
4787 if (trans->transaction->in_commit ||
4788 trans->transaction->delayed_refs.flushing) {
4792 for (update_count = 0; update_count < 16; update_count++) {
4793 update = trans->delayed_ref_updates;
4794 trans->delayed_ref_updates = 0;
4796 btrfs_run_delayed_refs(trans, root, update);
4802 btrfs_free_path(path);
4806 int btrfs_drop_subtree(struct btrfs_trans_handle *trans,
4807 struct btrfs_root *root,
4808 struct extent_buffer *node,
4809 struct extent_buffer *parent)
4811 struct btrfs_path *path;
4817 path = btrfs_alloc_path();
4820 btrfs_assert_tree_locked(parent);
4821 parent_level = btrfs_header_level(parent);
4822 extent_buffer_get(parent);
4823 path->nodes[parent_level] = parent;
4824 path->slots[parent_level] = btrfs_header_nritems(parent);
4826 btrfs_assert_tree_locked(node);
4827 level = btrfs_header_level(node);
4828 extent_buffer_get(node);
4829 path->nodes[level] = node;
4830 path->slots[level] = 0;
4833 wret = walk_down_tree(trans, root, path, &level);
4839 wret = walk_up_tree(trans, root, path, &level, parent_level);
4846 btrfs_free_path(path);
4851 static unsigned long calc_ra(unsigned long start, unsigned long last,
4854 return min(last, start + nr - 1);
4857 static noinline int relocate_inode_pages(struct inode *inode, u64 start,
4862 unsigned long first_index;
4863 unsigned long last_index;
4866 struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
4867 struct file_ra_state *ra;
4868 struct btrfs_ordered_extent *ordered;
4869 unsigned int total_read = 0;
4870 unsigned int total_dirty = 0;
4873 ra = kzalloc(sizeof(*ra), GFP_NOFS);
4875 mutex_lock(&inode->i_mutex);
4876 first_index = start >> PAGE_CACHE_SHIFT;
4877 last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;
4879 /* make sure the dirty trick played by the caller work */
4880 ret = invalidate_inode_pages2_range(inode->i_mapping,
4881 first_index, last_index);
4885 file_ra_state_init(ra, inode->i_mapping);
4887 for (i = first_index ; i <= last_index; i++) {
4888 if (total_read % ra->ra_pages == 0) {
4889 btrfs_force_ra(inode->i_mapping, ra, NULL, i,
4890 calc_ra(i, last_index, ra->ra_pages));
4894 if (((u64)i << PAGE_CACHE_SHIFT) > i_size_read(inode))
4896 page = grab_cache_page(inode->i_mapping, i);
4901 if (!PageUptodate(page)) {
4902 btrfs_readpage(NULL, page);
4904 if (!PageUptodate(page)) {
4906 page_cache_release(page);
4911 wait_on_page_writeback(page);
4913 page_start = (u64)page->index << PAGE_CACHE_SHIFT;
4914 page_end = page_start + PAGE_CACHE_SIZE - 1;
4915 lock_extent(io_tree, page_start, page_end, GFP_NOFS);
4917 ordered = btrfs_lookup_ordered_extent(inode, page_start);
4919 unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
4921 page_cache_release(page);
4922 btrfs_start_ordered_extent(inode, ordered, 1);
4923 btrfs_put_ordered_extent(ordered);
4926 set_page_extent_mapped(page);
4928 if (i == first_index)
4929 set_extent_bits(io_tree, page_start, page_end,
4930 EXTENT_BOUNDARY, GFP_NOFS);
4931 btrfs_set_extent_delalloc(inode, page_start, page_end);
4933 set_page_dirty(page);
4936 unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
4938 page_cache_release(page);
4943 mutex_unlock(&inode->i_mutex);
4944 balance_dirty_pages_ratelimited_nr(inode->i_mapping, total_dirty);
4948 static noinline int relocate_data_extent(struct inode *reloc_inode,
4949 struct btrfs_key *extent_key,
4952 struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
4953 struct extent_map_tree *em_tree = &BTRFS_I(reloc_inode)->extent_tree;
4954 struct extent_map *em;
4955 u64 start = extent_key->objectid - offset;
4956 u64 end = start + extent_key->offset - 1;
4958 em = alloc_extent_map(GFP_NOFS);
4959 BUG_ON(!em || IS_ERR(em));
4962 em->len = extent_key->offset;
4963 em->block_len = extent_key->offset;
4964 em->block_start = extent_key->objectid;
4965 em->bdev = root->fs_info->fs_devices->latest_bdev;
4966 set_bit(EXTENT_FLAG_PINNED, &em->flags);
4968 /* setup extent map to cheat btrfs_readpage */
4969 lock_extent(&BTRFS_I(reloc_inode)->io_tree, start, end, GFP_NOFS);
4972 spin_lock(&em_tree->lock);
4973 ret = add_extent_mapping(em_tree, em);
4974 spin_unlock(&em_tree->lock);
4975 if (ret != -EEXIST) {
4976 free_extent_map(em);
4979 btrfs_drop_extent_cache(reloc_inode, start, end, 0);
4981 unlock_extent(&BTRFS_I(reloc_inode)->io_tree, start, end, GFP_NOFS);
4983 return relocate_inode_pages(reloc_inode, start, extent_key->offset);
4986 struct btrfs_ref_path {
4988 u64 nodes[BTRFS_MAX_LEVEL];
4990 u64 root_generation;
4997 struct btrfs_key node_keys[BTRFS_MAX_LEVEL];
4998 u64 new_nodes[BTRFS_MAX_LEVEL];
5001 struct disk_extent {
5012 static int is_cowonly_root(u64 root_objectid)
5014 if (root_objectid == BTRFS_ROOT_TREE_OBJECTID ||
5015 root_objectid == BTRFS_EXTENT_TREE_OBJECTID ||
5016 root_objectid == BTRFS_CHUNK_TREE_OBJECTID ||
5017 root_objectid == BTRFS_DEV_TREE_OBJECTID ||
5018 root_objectid == BTRFS_TREE_LOG_OBJECTID ||
5019 root_objectid == BTRFS_CSUM_TREE_OBJECTID)
5024 static noinline int __next_ref_path(struct btrfs_trans_handle *trans,
5025 struct btrfs_root *extent_root,
5026 struct btrfs_ref_path *ref_path,
5029 struct extent_buffer *leaf;
5030 struct btrfs_path *path;
5031 struct btrfs_extent_ref *ref;
5032 struct btrfs_key key;
5033 struct btrfs_key found_key;
5039 path = btrfs_alloc_path();
5044 ref_path->lowest_level = -1;
5045 ref_path->current_level = -1;
5046 ref_path->shared_level = -1;
5050 level = ref_path->current_level - 1;
5051 while (level >= -1) {
5053 if (level < ref_path->lowest_level)
5057 bytenr = ref_path->nodes[level];
5059 bytenr = ref_path->extent_start;
5060 BUG_ON(bytenr == 0);
5062 parent = ref_path->nodes[level + 1];
5063 ref_path->nodes[level + 1] = 0;
5064 ref_path->current_level = level;
5065 BUG_ON(parent == 0);
5067 key.objectid = bytenr;
5068 key.offset = parent + 1;
5069 key.type = BTRFS_EXTENT_REF_KEY;
5071 ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
5076 leaf = path->nodes[0];
5077 nritems = btrfs_header_nritems(leaf);
5078 if (path->slots[0] >= nritems) {
5079 ret = btrfs_next_leaf(extent_root, path);
5084 leaf = path->nodes[0];
5087 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5088 if (found_key.objectid == bytenr &&
5089 found_key.type == BTRFS_EXTENT_REF_KEY) {
5090 if (level < ref_path->shared_level)
5091 ref_path->shared_level = level;
5096 btrfs_release_path(extent_root, path);
5099 /* reached lowest level */
5103 level = ref_path->current_level;
5104 while (level < BTRFS_MAX_LEVEL - 1) {
5108 bytenr = ref_path->nodes[level];
5110 bytenr = ref_path->extent_start;
5112 BUG_ON(bytenr == 0);
5114 key.objectid = bytenr;
5116 key.type = BTRFS_EXTENT_REF_KEY;
5118 ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
5122 leaf = path->nodes[0];
5123 nritems = btrfs_header_nritems(leaf);
5124 if (path->slots[0] >= nritems) {
5125 ret = btrfs_next_leaf(extent_root, path);
5129 /* the extent was freed by someone */
5130 if (ref_path->lowest_level == level)
5132 btrfs_release_path(extent_root, path);
5135 leaf = path->nodes[0];
5138 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5139 if (found_key.objectid != bytenr ||
5140 found_key.type != BTRFS_EXTENT_REF_KEY) {
5141 /* the extent was freed by someone */
5142 if (ref_path->lowest_level == level) {
5146 btrfs_release_path(extent_root, path);
5150 ref = btrfs_item_ptr(leaf, path->slots[0],
5151 struct btrfs_extent_ref);
5152 ref_objectid = btrfs_ref_objectid(leaf, ref);
5153 if (ref_objectid < BTRFS_FIRST_FREE_OBJECTID) {
5155 level = (int)ref_objectid;
5156 BUG_ON(level >= BTRFS_MAX_LEVEL);
5157 ref_path->lowest_level = level;
5158 ref_path->current_level = level;
5159 ref_path->nodes[level] = bytenr;
5161 WARN_ON(ref_objectid != level);
5164 WARN_ON(level != -1);
5168 if (ref_path->lowest_level == level) {
5169 ref_path->owner_objectid = ref_objectid;
5170 ref_path->num_refs = btrfs_ref_num_refs(leaf, ref);
5174 * the block is tree root or the block isn't in reference
5177 if (found_key.objectid == found_key.offset ||
5178 is_cowonly_root(btrfs_ref_root(leaf, ref))) {
5179 ref_path->root_objectid = btrfs_ref_root(leaf, ref);
5180 ref_path->root_generation =
5181 btrfs_ref_generation(leaf, ref);
5183 /* special reference from the tree log */
5184 ref_path->nodes[0] = found_key.offset;
5185 ref_path->current_level = 0;
5192 BUG_ON(ref_path->nodes[level] != 0);
5193 ref_path->nodes[level] = found_key.offset;
5194 ref_path->current_level = level;
5197 * the reference was created in the running transaction,
5198 * no need to continue walking up.
5200 if (btrfs_ref_generation(leaf, ref) == trans->transid) {
5201 ref_path->root_objectid = btrfs_ref_root(leaf, ref);
5202 ref_path->root_generation =
5203 btrfs_ref_generation(leaf, ref);
5208 btrfs_release_path(extent_root, path);
5211 /* reached max tree level, but no tree root found. */
5214 btrfs_free_path(path);
5218 static int btrfs_first_ref_path(struct btrfs_trans_handle *trans,
5219 struct btrfs_root *extent_root,
5220 struct btrfs_ref_path *ref_path,
5223 memset(ref_path, 0, sizeof(*ref_path));
5224 ref_path->extent_start = extent_start;
5226 return __next_ref_path(trans, extent_root, ref_path, 1);
5229 static int btrfs_next_ref_path(struct btrfs_trans_handle *trans,
5230 struct btrfs_root *extent_root,
5231 struct btrfs_ref_path *ref_path)
5233 return __next_ref_path(trans, extent_root, ref_path, 0);
5236 static noinline int get_new_locations(struct inode *reloc_inode,
5237 struct btrfs_key *extent_key,
5238 u64 offset, int no_fragment,
5239 struct disk_extent **extents,
5242 struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
5243 struct btrfs_path *path;
5244 struct btrfs_file_extent_item *fi;
5245 struct extent_buffer *leaf;
5246 struct disk_extent *exts = *extents;
5247 struct btrfs_key found_key;
5252 int max = *nr_extents;
5255 WARN_ON(!no_fragment && *extents);
5258 exts = kmalloc(sizeof(*exts) * max, GFP_NOFS);
5263 path = btrfs_alloc_path();
5266 cur_pos = extent_key->objectid - offset;
5267 last_byte = extent_key->objectid + extent_key->offset;
5268 ret = btrfs_lookup_file_extent(NULL, root, path, reloc_inode->i_ino,
5278 leaf = path->nodes[0];
5279 nritems = btrfs_header_nritems(leaf);
5280 if (path->slots[0] >= nritems) {
5281 ret = btrfs_next_leaf(root, path);
5286 leaf = path->nodes[0];
5289 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5290 if (found_key.offset != cur_pos ||
5291 found_key.type != BTRFS_EXTENT_DATA_KEY ||
5292 found_key.objectid != reloc_inode->i_ino)
5295 fi = btrfs_item_ptr(leaf, path->slots[0],
5296 struct btrfs_file_extent_item);
5297 if (btrfs_file_extent_type(leaf, fi) !=
5298 BTRFS_FILE_EXTENT_REG ||
5299 btrfs_file_extent_disk_bytenr(leaf, fi) == 0)
5303 struct disk_extent *old = exts;
5305 exts = kzalloc(sizeof(*exts) * max, GFP_NOFS);
5306 memcpy(exts, old, sizeof(*exts) * nr);
5307 if (old != *extents)
5311 exts[nr].disk_bytenr =
5312 btrfs_file_extent_disk_bytenr(leaf, fi);
5313 exts[nr].disk_num_bytes =
5314 btrfs_file_extent_disk_num_bytes(leaf, fi);
5315 exts[nr].offset = btrfs_file_extent_offset(leaf, fi);
5316 exts[nr].num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
5317 exts[nr].ram_bytes = btrfs_file_extent_ram_bytes(leaf, fi);
5318 exts[nr].compression = btrfs_file_extent_compression(leaf, fi);
5319 exts[nr].encryption = btrfs_file_extent_encryption(leaf, fi);
5320 exts[nr].other_encoding = btrfs_file_extent_other_encoding(leaf,
5322 BUG_ON(exts[nr].offset > 0);
5323 BUG_ON(exts[nr].compression || exts[nr].encryption);
5324 BUG_ON(exts[nr].num_bytes != exts[nr].disk_num_bytes);
5326 cur_pos += exts[nr].num_bytes;
5329 if (cur_pos + offset >= last_byte)
5339 BUG_ON(cur_pos + offset > last_byte);
5340 if (cur_pos + offset < last_byte) {
5346 btrfs_free_path(path);
5348 if (exts != *extents)
5357 static noinline int replace_one_extent(struct btrfs_trans_handle *trans,
5358 struct btrfs_root *root,
5359 struct btrfs_path *path,
5360 struct btrfs_key *extent_key,
5361 struct btrfs_key *leaf_key,
5362 struct btrfs_ref_path *ref_path,
5363 struct disk_extent *new_extents,
5366 struct extent_buffer *leaf;
5367 struct btrfs_file_extent_item *fi;
5368 struct inode *inode = NULL;
5369 struct btrfs_key key;
5374 u64 search_end = (u64)-1;
5377 int extent_locked = 0;
5381 memcpy(&key, leaf_key, sizeof(key));
5382 if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
5383 if (key.objectid < ref_path->owner_objectid ||
5384 (key.objectid == ref_path->owner_objectid &&
5385 key.type < BTRFS_EXTENT_DATA_KEY)) {
5386 key.objectid = ref_path->owner_objectid;
5387 key.type = BTRFS_EXTENT_DATA_KEY;
5393 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
5397 leaf = path->nodes[0];
5398 nritems = btrfs_header_nritems(leaf);
5400 if (extent_locked && ret > 0) {
5402 * the file extent item was modified by someone
5403 * before the extent got locked.
5405 unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
5406 lock_end, GFP_NOFS);
5410 if (path->slots[0] >= nritems) {
5411 if (++nr_scaned > 2)
5414 BUG_ON(extent_locked);
5415 ret = btrfs_next_leaf(root, path);
5420 leaf = path->nodes[0];
5421 nritems = btrfs_header_nritems(leaf);
5424 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
5426 if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
5427 if ((key.objectid > ref_path->owner_objectid) ||
5428 (key.objectid == ref_path->owner_objectid &&
5429 key.type > BTRFS_EXTENT_DATA_KEY) ||
5430 key.offset >= search_end)
5434 if (inode && key.objectid != inode->i_ino) {
5435 BUG_ON(extent_locked);
5436 btrfs_release_path(root, path);
5437 mutex_unlock(&inode->i_mutex);
5443 if (key.type != BTRFS_EXTENT_DATA_KEY) {
5448 fi = btrfs_item_ptr(leaf, path->slots[0],
5449 struct btrfs_file_extent_item);
5450 extent_type = btrfs_file_extent_type(leaf, fi);
5451 if ((extent_type != BTRFS_FILE_EXTENT_REG &&
5452 extent_type != BTRFS_FILE_EXTENT_PREALLOC) ||
5453 (btrfs_file_extent_disk_bytenr(leaf, fi) !=
5454 extent_key->objectid)) {
5460 num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
5461 ext_offset = btrfs_file_extent_offset(leaf, fi);
5463 if (search_end == (u64)-1) {
5464 search_end = key.offset - ext_offset +
5465 btrfs_file_extent_ram_bytes(leaf, fi);
5468 if (!extent_locked) {
5469 lock_start = key.offset;
5470 lock_end = lock_start + num_bytes - 1;
5472 if (lock_start > key.offset ||
5473 lock_end + 1 < key.offset + num_bytes) {
5474 unlock_extent(&BTRFS_I(inode)->io_tree,
5475 lock_start, lock_end, GFP_NOFS);
5481 btrfs_release_path(root, path);
5483 inode = btrfs_iget_locked(root->fs_info->sb,
5484 key.objectid, root);
5485 if (inode->i_state & I_NEW) {
5486 BTRFS_I(inode)->root = root;
5487 BTRFS_I(inode)->location.objectid =
5489 BTRFS_I(inode)->location.type =
5490 BTRFS_INODE_ITEM_KEY;
5491 BTRFS_I(inode)->location.offset = 0;
5492 btrfs_read_locked_inode(inode);
5493 unlock_new_inode(inode);
5496 * some code call btrfs_commit_transaction while
5497 * holding the i_mutex, so we can't use mutex_lock
5500 if (is_bad_inode(inode) ||
5501 !mutex_trylock(&inode->i_mutex)) {
5504 key.offset = (u64)-1;
5509 if (!extent_locked) {
5510 struct btrfs_ordered_extent *ordered;
5512 btrfs_release_path(root, path);
5514 lock_extent(&BTRFS_I(inode)->io_tree, lock_start,
5515 lock_end, GFP_NOFS);
5516 ordered = btrfs_lookup_first_ordered_extent(inode,
5519 ordered->file_offset <= lock_end &&
5520 ordered->file_offset + ordered->len > lock_start) {
5521 unlock_extent(&BTRFS_I(inode)->io_tree,
5522 lock_start, lock_end, GFP_NOFS);
5523 btrfs_start_ordered_extent(inode, ordered, 1);
5524 btrfs_put_ordered_extent(ordered);
5525 key.offset += num_bytes;
5529 btrfs_put_ordered_extent(ordered);
5535 if (nr_extents == 1) {
5536 /* update extent pointer in place */
5537 btrfs_set_file_extent_disk_bytenr(leaf, fi,
5538 new_extents[0].disk_bytenr);
5539 btrfs_set_file_extent_disk_num_bytes(leaf, fi,
5540 new_extents[0].disk_num_bytes);
5541 btrfs_mark_buffer_dirty(leaf);
5543 btrfs_drop_extent_cache(inode, key.offset,
5544 key.offset + num_bytes - 1, 0);
5546 ret = btrfs_inc_extent_ref(trans, root,
5547 new_extents[0].disk_bytenr,
5548 new_extents[0].disk_num_bytes,
5550 root->root_key.objectid,
5555 ret = btrfs_free_extent(trans, root,
5556 extent_key->objectid,
5559 btrfs_header_owner(leaf),
5560 btrfs_header_generation(leaf),
5564 btrfs_release_path(root, path);
5565 key.offset += num_bytes;
5573 * drop old extent pointer at first, then insert the
5574 * new pointers one bye one
5576 btrfs_release_path(root, path);
5577 ret = btrfs_drop_extents(trans, root, inode, key.offset,
5578 key.offset + num_bytes,
5579 key.offset, &alloc_hint);
5582 for (i = 0; i < nr_extents; i++) {
5583 if (ext_offset >= new_extents[i].num_bytes) {
5584 ext_offset -= new_extents[i].num_bytes;
5587 extent_len = min(new_extents[i].num_bytes -
5588 ext_offset, num_bytes);
5590 ret = btrfs_insert_empty_item(trans, root,
5595 leaf = path->nodes[0];
5596 fi = btrfs_item_ptr(leaf, path->slots[0],
5597 struct btrfs_file_extent_item);
5598 btrfs_set_file_extent_generation(leaf, fi,
5600 btrfs_set_file_extent_type(leaf, fi,
5601 BTRFS_FILE_EXTENT_REG);
5602 btrfs_set_file_extent_disk_bytenr(leaf, fi,
5603 new_extents[i].disk_bytenr);
5604 btrfs_set_file_extent_disk_num_bytes(leaf, fi,
5605 new_extents[i].disk_num_bytes);
5606 btrfs_set_file_extent_ram_bytes(leaf, fi,
5607 new_extents[i].ram_bytes);
5609 btrfs_set_file_extent_compression(leaf, fi,
5610 new_extents[i].compression);
5611 btrfs_set_file_extent_encryption(leaf, fi,
5612 new_extents[i].encryption);
5613 btrfs_set_file_extent_other_encoding(leaf, fi,
5614 new_extents[i].other_encoding);
5616 btrfs_set_file_extent_num_bytes(leaf, fi,
5618 ext_offset += new_extents[i].offset;
5619 btrfs_set_file_extent_offset(leaf, fi,
5621 btrfs_mark_buffer_dirty(leaf);
5623 btrfs_drop_extent_cache(inode, key.offset,
5624 key.offset + extent_len - 1, 0);
5626 ret = btrfs_inc_extent_ref(trans, root,
5627 new_extents[i].disk_bytenr,
5628 new_extents[i].disk_num_bytes,
5630 root->root_key.objectid,
5631 trans->transid, key.objectid);
5633 btrfs_release_path(root, path);
5635 inode_add_bytes(inode, extent_len);
5638 num_bytes -= extent_len;
5639 key.offset += extent_len;
5644 BUG_ON(i >= nr_extents);
5648 if (extent_locked) {
5649 unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
5650 lock_end, GFP_NOFS);
5654 if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS &&
5655 key.offset >= search_end)
5662 btrfs_release_path(root, path);
5664 mutex_unlock(&inode->i_mutex);
5665 if (extent_locked) {
5666 unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
5667 lock_end, GFP_NOFS);
5674 int btrfs_reloc_tree_cache_ref(struct btrfs_trans_handle *trans,
5675 struct btrfs_root *root,
5676 struct extent_buffer *buf, u64 orig_start)
5681 BUG_ON(btrfs_header_generation(buf) != trans->transid);
5682 BUG_ON(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID);
5684 level = btrfs_header_level(buf);
5686 struct btrfs_leaf_ref *ref;
5687 struct btrfs_leaf_ref *orig_ref;
5689 orig_ref = btrfs_lookup_leaf_ref(root, orig_start);
5693 ref = btrfs_alloc_leaf_ref(root, orig_ref->nritems);
5695 btrfs_free_leaf_ref(root, orig_ref);
5699 ref->nritems = orig_ref->nritems;
5700 memcpy(ref->extents, orig_ref->extents,
5701 sizeof(ref->extents[0]) * ref->nritems);
5703 btrfs_free_leaf_ref(root, orig_ref);
5705 ref->root_gen = trans->transid;
5706 ref->bytenr = buf->start;
5707 ref->owner = btrfs_header_owner(buf);
5708 ref->generation = btrfs_header_generation(buf);
5710 ret = btrfs_add_leaf_ref(root, ref, 0);
5712 btrfs_free_leaf_ref(root, ref);
5717 static noinline int invalidate_extent_cache(struct btrfs_root *root,
5718 struct extent_buffer *leaf,
5719 struct btrfs_block_group_cache *group,
5720 struct btrfs_root *target_root)
5722 struct btrfs_key key;
5723 struct inode *inode = NULL;
5724 struct btrfs_file_extent_item *fi;
5726 u64 skip_objectid = 0;
5730 nritems = btrfs_header_nritems(leaf);
5731 for (i = 0; i < nritems; i++) {
5732 btrfs_item_key_to_cpu(leaf, &key, i);
5733 if (key.objectid == skip_objectid ||
5734 key.type != BTRFS_EXTENT_DATA_KEY)
5736 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
5737 if (btrfs_file_extent_type(leaf, fi) ==
5738 BTRFS_FILE_EXTENT_INLINE)
5740 if (btrfs_file_extent_disk_bytenr(leaf, fi) == 0)
5742 if (!inode || inode->i_ino != key.objectid) {
5744 inode = btrfs_ilookup(target_root->fs_info->sb,
5745 key.objectid, target_root, 1);
5748 skip_objectid = key.objectid;
5751 num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
5753 lock_extent(&BTRFS_I(inode)->io_tree, key.offset,
5754 key.offset + num_bytes - 1, GFP_NOFS);
5755 btrfs_drop_extent_cache(inode, key.offset,
5756 key.offset + num_bytes - 1, 1);
5757 unlock_extent(&BTRFS_I(inode)->io_tree, key.offset,
5758 key.offset + num_bytes - 1, GFP_NOFS);
5765 static noinline int replace_extents_in_leaf(struct btrfs_trans_handle *trans,
5766 struct btrfs_root *root,
5767 struct extent_buffer *leaf,
5768 struct btrfs_block_group_cache *group,
5769 struct inode *reloc_inode)
5771 struct btrfs_key key;
5772 struct btrfs_key extent_key;
5773 struct btrfs_file_extent_item *fi;
5774 struct btrfs_leaf_ref *ref;
5775 struct disk_extent *new_extent;
5784 new_extent = kmalloc(sizeof(*new_extent), GFP_NOFS);
5785 BUG_ON(!new_extent);
5787 ref = btrfs_lookup_leaf_ref(root, leaf->start);
5791 nritems = btrfs_header_nritems(leaf);
5792 for (i = 0; i < nritems; i++) {
5793 btrfs_item_key_to_cpu(leaf, &key, i);
5794 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
5796 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
5797 if (btrfs_file_extent_type(leaf, fi) ==
5798 BTRFS_FILE_EXTENT_INLINE)
5800 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
5801 num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
5806 if (bytenr >= group->key.objectid + group->key.offset ||
5807 bytenr + num_bytes <= group->key.objectid)
5810 extent_key.objectid = bytenr;
5811 extent_key.offset = num_bytes;
5812 extent_key.type = BTRFS_EXTENT_ITEM_KEY;
5814 ret = get_new_locations(reloc_inode, &extent_key,
5815 group->key.objectid, 1,
5816 &new_extent, &nr_extent);
5821 BUG_ON(ref->extents[ext_index].bytenr != bytenr);
5822 BUG_ON(ref->extents[ext_index].num_bytes != num_bytes);
5823 ref->extents[ext_index].bytenr = new_extent->disk_bytenr;
5824 ref->extents[ext_index].num_bytes = new_extent->disk_num_bytes;
5826 btrfs_set_file_extent_disk_bytenr(leaf, fi,
5827 new_extent->disk_bytenr);
5828 btrfs_set_file_extent_disk_num_bytes(leaf, fi,
5829 new_extent->disk_num_bytes);
5830 btrfs_mark_buffer_dirty(leaf);
5832 ret = btrfs_inc_extent_ref(trans, root,
5833 new_extent->disk_bytenr,
5834 new_extent->disk_num_bytes,
5836 root->root_key.objectid,
5837 trans->transid, key.objectid);
5840 ret = btrfs_free_extent(trans, root,
5841 bytenr, num_bytes, leaf->start,
5842 btrfs_header_owner(leaf),
5843 btrfs_header_generation(leaf),
5849 BUG_ON(ext_index + 1 != ref->nritems);
5850 btrfs_free_leaf_ref(root, ref);
5854 int btrfs_free_reloc_root(struct btrfs_trans_handle *trans,
5855 struct btrfs_root *root)
5857 struct btrfs_root *reloc_root;
5860 if (root->reloc_root) {
5861 reloc_root = root->reloc_root;
5862 root->reloc_root = NULL;
5863 list_add(&reloc_root->dead_list,
5864 &root->fs_info->dead_reloc_roots);
5866 btrfs_set_root_bytenr(&reloc_root->root_item,
5867 reloc_root->node->start);
5868 btrfs_set_root_level(&root->root_item,
5869 btrfs_header_level(reloc_root->node));
5870 memset(&reloc_root->root_item.drop_progress, 0,
5871 sizeof(struct btrfs_disk_key));
5872 reloc_root->root_item.drop_level = 0;
5874 ret = btrfs_update_root(trans, root->fs_info->tree_root,
5875 &reloc_root->root_key,
5876 &reloc_root->root_item);
5882 int btrfs_drop_dead_reloc_roots(struct btrfs_root *root)
5884 struct btrfs_trans_handle *trans;
5885 struct btrfs_root *reloc_root;
5886 struct btrfs_root *prev_root = NULL;
5887 struct list_head dead_roots;
5891 INIT_LIST_HEAD(&dead_roots);
5892 list_splice_init(&root->fs_info->dead_reloc_roots, &dead_roots);
5894 while (!list_empty(&dead_roots)) {
5895 reloc_root = list_entry(dead_roots.prev,
5896 struct btrfs_root, dead_list);
5897 list_del_init(&reloc_root->dead_list);
5899 BUG_ON(reloc_root->commit_root != NULL);
5901 trans = btrfs_join_transaction(root, 1);
5904 mutex_lock(&root->fs_info->drop_mutex);
5905 ret = btrfs_drop_snapshot(trans, reloc_root);
5908 mutex_unlock(&root->fs_info->drop_mutex);
5910 nr = trans->blocks_used;
5911 ret = btrfs_end_transaction(trans, root);
5913 btrfs_btree_balance_dirty(root, nr);
5916 free_extent_buffer(reloc_root->node);
5918 ret = btrfs_del_root(trans, root->fs_info->tree_root,
5919 &reloc_root->root_key);
5921 mutex_unlock(&root->fs_info->drop_mutex);
5923 nr = trans->blocks_used;
5924 ret = btrfs_end_transaction(trans, root);
5926 btrfs_btree_balance_dirty(root, nr);
5929 prev_root = reloc_root;
5932 btrfs_remove_leaf_refs(prev_root, (u64)-1, 0);
5938 int btrfs_add_dead_reloc_root(struct btrfs_root *root)
5940 list_add(&root->dead_list, &root->fs_info->dead_reloc_roots);
5944 int btrfs_cleanup_reloc_trees(struct btrfs_root *root)
5946 struct btrfs_root *reloc_root;
5947 struct btrfs_trans_handle *trans;
5948 struct btrfs_key location;
5952 mutex_lock(&root->fs_info->tree_reloc_mutex);
5953 ret = btrfs_find_dead_roots(root, BTRFS_TREE_RELOC_OBJECTID, NULL);
5955 found = !list_empty(&root->fs_info->dead_reloc_roots);
5956 mutex_unlock(&root->fs_info->tree_reloc_mutex);
5959 trans = btrfs_start_transaction(root, 1);
5961 ret = btrfs_commit_transaction(trans, root);
5965 location.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
5966 location.offset = (u64)-1;
5967 location.type = BTRFS_ROOT_ITEM_KEY;
5969 reloc_root = btrfs_read_fs_root_no_name(root->fs_info, &location);
5970 BUG_ON(!reloc_root);
5971 btrfs_orphan_cleanup(reloc_root);
5975 static noinline int init_reloc_tree(struct btrfs_trans_handle *trans,
5976 struct btrfs_root *root)
5978 struct btrfs_root *reloc_root;
5979 struct extent_buffer *eb;
5980 struct btrfs_root_item *root_item;
5981 struct btrfs_key root_key;
5984 BUG_ON(!root->ref_cows);
5985 if (root->reloc_root)
5988 root_item = kmalloc(sizeof(*root_item), GFP_NOFS);
5991 ret = btrfs_copy_root(trans, root, root->commit_root,
5992 &eb, BTRFS_TREE_RELOC_OBJECTID);
5995 root_key.objectid = BTRFS_TREE_RELOC_OBJECTID;
5996 root_key.offset = root->root_key.objectid;
5997 root_key.type = BTRFS_ROOT_ITEM_KEY;
5999 memcpy(root_item, &root->root_item, sizeof(root_item));
6000 btrfs_set_root_refs(root_item, 0);
6001 btrfs_set_root_bytenr(root_item, eb->start);
6002 btrfs_set_root_level(root_item, btrfs_header_level(eb));
6003 btrfs_set_root_generation(root_item, trans->transid);
6005 btrfs_tree_unlock(eb);
6006 free_extent_buffer(eb);
6008 ret = btrfs_insert_root(trans, root->fs_info->tree_root,
6009 &root_key, root_item);
6013 reloc_root = btrfs_read_fs_root_no_radix(root->fs_info->tree_root,
6015 BUG_ON(!reloc_root);
6016 reloc_root->last_trans = trans->transid;
6017 reloc_root->commit_root = NULL;
6018 reloc_root->ref_tree = &root->fs_info->reloc_ref_tree;
6020 root->reloc_root = reloc_root;
6025 * Core function of space balance.
6027 * The idea is using reloc trees to relocate tree blocks in reference
6028 * counted roots. There is one reloc tree for each subvol, and all
6029 * reloc trees share same root key objectid. Reloc trees are snapshots
6030 * of the latest committed roots of subvols (root->commit_root).
6032 * To relocate a tree block referenced by a subvol, there are two steps.
6033 * COW the block through subvol's reloc tree, then update block pointer
6034 * in the subvol to point to the new block. Since all reloc trees share
6035 * same root key objectid, doing special handing for tree blocks owned
6036 * by them is easy. Once a tree block has been COWed in one reloc tree,
6037 * we can use the resulting new block directly when the same block is
6038 * required to COW again through other reloc trees. By this way, relocated
6039 * tree blocks are shared between reloc trees, so they are also shared
6042 static noinline int relocate_one_path(struct btrfs_trans_handle *trans,
6043 struct btrfs_root *root,
6044 struct btrfs_path *path,
6045 struct btrfs_key *first_key,
6046 struct btrfs_ref_path *ref_path,
6047 struct btrfs_block_group_cache *group,
6048 struct inode *reloc_inode)
6050 struct btrfs_root *reloc_root;
6051 struct extent_buffer *eb = NULL;
6052 struct btrfs_key *keys;
6056 int lowest_level = 0;
6059 if (ref_path->owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
6060 lowest_level = ref_path->owner_objectid;
6062 if (!root->ref_cows) {
6063 path->lowest_level = lowest_level;
6064 ret = btrfs_search_slot(trans, root, first_key, path, 0, 1);
6066 path->lowest_level = 0;
6067 btrfs_release_path(root, path);
6071 mutex_lock(&root->fs_info->tree_reloc_mutex);
6072 ret = init_reloc_tree(trans, root);
6074 reloc_root = root->reloc_root;
6076 shared_level = ref_path->shared_level;
6077 ref_path->shared_level = BTRFS_MAX_LEVEL - 1;
6079 keys = ref_path->node_keys;
6080 nodes = ref_path->new_nodes;
6081 memset(&keys[shared_level + 1], 0,
6082 sizeof(*keys) * (BTRFS_MAX_LEVEL - shared_level - 1));
6083 memset(&nodes[shared_level + 1], 0,
6084 sizeof(*nodes) * (BTRFS_MAX_LEVEL - shared_level - 1));
6086 if (nodes[lowest_level] == 0) {
6087 path->lowest_level = lowest_level;
6088 ret = btrfs_search_slot(trans, reloc_root, first_key, path,
6091 for (level = lowest_level; level < BTRFS_MAX_LEVEL; level++) {
6092 eb = path->nodes[level];
6093 if (!eb || eb == reloc_root->node)
6095 nodes[level] = eb->start;
6097 btrfs_item_key_to_cpu(eb, &keys[level], 0);
6099 btrfs_node_key_to_cpu(eb, &keys[level], 0);
6102 ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
6103 eb = path->nodes[0];
6104 ret = replace_extents_in_leaf(trans, reloc_root, eb,
6105 group, reloc_inode);
6108 btrfs_release_path(reloc_root, path);
6110 ret = btrfs_merge_path(trans, reloc_root, keys, nodes,
6116 * replace tree blocks in the fs tree with tree blocks in
6119 ret = btrfs_merge_path(trans, root, keys, nodes, lowest_level);
6122 if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
6123 ret = btrfs_search_slot(trans, reloc_root, first_key, path,
6126 extent_buffer_get(path->nodes[0]);
6127 eb = path->nodes[0];
6128 btrfs_release_path(reloc_root, path);
6129 ret = invalidate_extent_cache(reloc_root, eb, group, root);
6131 free_extent_buffer(eb);
6134 mutex_unlock(&root->fs_info->tree_reloc_mutex);
6135 path->lowest_level = 0;
6139 static noinline int relocate_tree_block(struct btrfs_trans_handle *trans,
6140 struct btrfs_root *root,
6141 struct btrfs_path *path,
6142 struct btrfs_key *first_key,
6143 struct btrfs_ref_path *ref_path)
6147 ret = relocate_one_path(trans, root, path, first_key,
6148 ref_path, NULL, NULL);
6154 static noinline int del_extent_zero(struct btrfs_trans_handle *trans,
6155 struct btrfs_root *extent_root,
6156 struct btrfs_path *path,
6157 struct btrfs_key *extent_key)
6161 ret = btrfs_search_slot(trans, extent_root, extent_key, path, -1, 1);
6164 ret = btrfs_del_item(trans, extent_root, path);
6166 btrfs_release_path(extent_root, path);
6170 static noinline struct btrfs_root *read_ref_root(struct btrfs_fs_info *fs_info,
6171 struct btrfs_ref_path *ref_path)
6173 struct btrfs_key root_key;
6175 root_key.objectid = ref_path->root_objectid;
6176 root_key.type = BTRFS_ROOT_ITEM_KEY;
6177 if (is_cowonly_root(ref_path->root_objectid))
6178 root_key.offset = 0;
6180 root_key.offset = (u64)-1;
6182 return btrfs_read_fs_root_no_name(fs_info, &root_key);
6185 static noinline int relocate_one_extent(struct btrfs_root *extent_root,
6186 struct btrfs_path *path,
6187 struct btrfs_key *extent_key,
6188 struct btrfs_block_group_cache *group,
6189 struct inode *reloc_inode, int pass)
6191 struct btrfs_trans_handle *trans;
6192 struct btrfs_root *found_root;
6193 struct btrfs_ref_path *ref_path = NULL;
6194 struct disk_extent *new_extents = NULL;
6199 struct btrfs_key first_key;
6203 trans = btrfs_start_transaction(extent_root, 1);
6206 if (extent_key->objectid == 0) {
6207 ret = del_extent_zero(trans, extent_root, path, extent_key);
6211 ref_path = kmalloc(sizeof(*ref_path), GFP_NOFS);
6217 for (loops = 0; ; loops++) {
6219 ret = btrfs_first_ref_path(trans, extent_root, ref_path,
6220 extent_key->objectid);
6222 ret = btrfs_next_ref_path(trans, extent_root, ref_path);
6229 if (ref_path->root_objectid == BTRFS_TREE_LOG_OBJECTID ||
6230 ref_path->root_objectid == BTRFS_TREE_RELOC_OBJECTID)
6233 found_root = read_ref_root(extent_root->fs_info, ref_path);
6234 BUG_ON(!found_root);
6236 * for reference counted tree, only process reference paths
6237 * rooted at the latest committed root.
6239 if (found_root->ref_cows &&
6240 ref_path->root_generation != found_root->root_key.offset)
6243 if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
6246 * copy data extents to new locations
6248 u64 group_start = group->key.objectid;
6249 ret = relocate_data_extent(reloc_inode,
6258 level = ref_path->owner_objectid;
6261 if (prev_block != ref_path->nodes[level]) {
6262 struct extent_buffer *eb;
6263 u64 block_start = ref_path->nodes[level];
6264 u64 block_size = btrfs_level_size(found_root, level);
6266 eb = read_tree_block(found_root, block_start,
6268 btrfs_tree_lock(eb);
6269 BUG_ON(level != btrfs_header_level(eb));
6272 btrfs_item_key_to_cpu(eb, &first_key, 0);
6274 btrfs_node_key_to_cpu(eb, &first_key, 0);
6276 btrfs_tree_unlock(eb);
6277 free_extent_buffer(eb);
6278 prev_block = block_start;
6281 mutex_lock(&extent_root->fs_info->trans_mutex);
6282 btrfs_record_root_in_trans(found_root);
6283 mutex_unlock(&extent_root->fs_info->trans_mutex);
6284 if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
6286 * try to update data extent references while
6287 * keeping metadata shared between snapshots.
6290 ret = relocate_one_path(trans, found_root,
6291 path, &first_key, ref_path,
6292 group, reloc_inode);
6298 * use fallback method to process the remaining
6302 u64 group_start = group->key.objectid;
6303 new_extents = kmalloc(sizeof(*new_extents),
6306 ret = get_new_locations(reloc_inode,
6314 ret = replace_one_extent(trans, found_root,
6316 &first_key, ref_path,
6317 new_extents, nr_extents);
6319 ret = relocate_tree_block(trans, found_root, path,
6320 &first_key, ref_path);
6327 btrfs_end_transaction(trans, extent_root);
6334 static u64 update_block_group_flags(struct btrfs_root *root, u64 flags)
6337 u64 stripped = BTRFS_BLOCK_GROUP_RAID0 |
6338 BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID10;
6340 num_devices = root->fs_info->fs_devices->rw_devices;
6341 if (num_devices == 1) {
6342 stripped |= BTRFS_BLOCK_GROUP_DUP;
6343 stripped = flags & ~stripped;
6345 /* turn raid0 into single device chunks */
6346 if (flags & BTRFS_BLOCK_GROUP_RAID0)
6349 /* turn mirroring into duplication */
6350 if (flags & (BTRFS_BLOCK_GROUP_RAID1 |
6351 BTRFS_BLOCK_GROUP_RAID10))
6352 return stripped | BTRFS_BLOCK_GROUP_DUP;
6355 /* they already had raid on here, just return */
6356 if (flags & stripped)
6359 stripped |= BTRFS_BLOCK_GROUP_DUP;
6360 stripped = flags & ~stripped;
6362 /* switch duplicated blocks with raid1 */
6363 if (flags & BTRFS_BLOCK_GROUP_DUP)
6364 return stripped | BTRFS_BLOCK_GROUP_RAID1;
6366 /* turn single device chunks into raid0 */
6367 return stripped | BTRFS_BLOCK_GROUP_RAID0;
6372 static int __alloc_chunk_for_shrink(struct btrfs_root *root,
6373 struct btrfs_block_group_cache *shrink_block_group,
6376 struct btrfs_trans_handle *trans;
6377 u64 new_alloc_flags;
6380 spin_lock(&shrink_block_group->lock);
6381 if (btrfs_block_group_used(&shrink_block_group->item) +
6382 shrink_block_group->reserved > 0) {
6383 spin_unlock(&shrink_block_group->lock);
6385 trans = btrfs_start_transaction(root, 1);
6386 spin_lock(&shrink_block_group->lock);
6388 new_alloc_flags = update_block_group_flags(root,
6389 shrink_block_group->flags);
6390 if (new_alloc_flags != shrink_block_group->flags) {
6392 btrfs_block_group_used(&shrink_block_group->item);
6394 calc = shrink_block_group->key.offset;
6396 spin_unlock(&shrink_block_group->lock);
6398 do_chunk_alloc(trans, root->fs_info->extent_root,
6399 calc + 2 * 1024 * 1024, new_alloc_flags, force);
6401 btrfs_end_transaction(trans, root);
6403 spin_unlock(&shrink_block_group->lock);
6408 int btrfs_prepare_block_group_relocation(struct btrfs_root *root,
6409 struct btrfs_block_group_cache *group)
6412 __alloc_chunk_for_shrink(root, group, 1);
6413 set_block_group_readonly(group);
6418 static int __insert_orphan_inode(struct btrfs_trans_handle *trans,
6419 struct btrfs_root *root,
6420 u64 objectid, u64 size)
6422 struct btrfs_path *path;
6423 struct btrfs_inode_item *item;
6424 struct extent_buffer *leaf;
6427 path = btrfs_alloc_path();
6431 path->leave_spinning = 1;
6432 ret = btrfs_insert_empty_inode(trans, root, path, objectid);
6436 leaf = path->nodes[0];
6437 item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_inode_item);
6438 memset_extent_buffer(leaf, 0, (unsigned long)item, sizeof(*item));
6439 btrfs_set_inode_generation(leaf, item, 1);
6440 btrfs_set_inode_size(leaf, item, size);
6441 btrfs_set_inode_mode(leaf, item, S_IFREG | 0600);
6442 btrfs_set_inode_flags(leaf, item, BTRFS_INODE_NOCOMPRESS);
6443 btrfs_mark_buffer_dirty(leaf);
6444 btrfs_release_path(root, path);
6446 btrfs_free_path(path);
6450 static noinline struct inode *create_reloc_inode(struct btrfs_fs_info *fs_info,
6451 struct btrfs_block_group_cache *group)
6453 struct inode *inode = NULL;
6454 struct btrfs_trans_handle *trans;
6455 struct btrfs_root *root;
6456 struct btrfs_key root_key;
6457 u64 objectid = BTRFS_FIRST_FREE_OBJECTID;
6460 root_key.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
6461 root_key.type = BTRFS_ROOT_ITEM_KEY;
6462 root_key.offset = (u64)-1;
6463 root = btrfs_read_fs_root_no_name(fs_info, &root_key);
6465 return ERR_CAST(root);
6467 trans = btrfs_start_transaction(root, 1);
6470 err = btrfs_find_free_objectid(trans, root, objectid, &objectid);
6474 err = __insert_orphan_inode(trans, root, objectid, group->key.offset);
6477 err = btrfs_insert_file_extent(trans, root, objectid, 0, 0, 0,
6478 group->key.offset, 0, group->key.offset,
6482 inode = btrfs_iget_locked(root->fs_info->sb, objectid, root);
6483 if (inode->i_state & I_NEW) {
6484 BTRFS_I(inode)->root = root;
6485 BTRFS_I(inode)->location.objectid = objectid;
6486 BTRFS_I(inode)->location.type = BTRFS_INODE_ITEM_KEY;
6487 BTRFS_I(inode)->location.offset = 0;
6488 btrfs_read_locked_inode(inode);
6489 unlock_new_inode(inode);
6490 BUG_ON(is_bad_inode(inode));
6494 BTRFS_I(inode)->index_cnt = group->key.objectid;
6496 err = btrfs_orphan_add(trans, inode);
6498 btrfs_end_transaction(trans, root);
6502 inode = ERR_PTR(err);
6507 int btrfs_reloc_clone_csums(struct inode *inode, u64 file_pos, u64 len)
6510 struct btrfs_ordered_sum *sums;
6511 struct btrfs_sector_sum *sector_sum;
6512 struct btrfs_ordered_extent *ordered;
6513 struct btrfs_root *root = BTRFS_I(inode)->root;
6514 struct list_head list;
6519 INIT_LIST_HEAD(&list);
6521 ordered = btrfs_lookup_ordered_extent(inode, file_pos);
6522 BUG_ON(ordered->file_offset != file_pos || ordered->len != len);
6524 disk_bytenr = file_pos + BTRFS_I(inode)->index_cnt;
6525 ret = btrfs_lookup_csums_range(root->fs_info->csum_root, disk_bytenr,
6526 disk_bytenr + len - 1, &list);
6528 while (!list_empty(&list)) {
6529 sums = list_entry(list.next, struct btrfs_ordered_sum, list);
6530 list_del_init(&sums->list);
6532 sector_sum = sums->sums;
6533 sums->bytenr = ordered->start;
6536 while (offset < sums->len) {
6537 sector_sum->bytenr += ordered->start - disk_bytenr;
6539 offset += root->sectorsize;
6542 btrfs_add_ordered_sum(inode, ordered, sums);
6544 btrfs_put_ordered_extent(ordered);
6548 int btrfs_relocate_block_group(struct btrfs_root *root, u64 group_start)
6550 struct btrfs_trans_handle *trans;
6551 struct btrfs_path *path;
6552 struct btrfs_fs_info *info = root->fs_info;
6553 struct extent_buffer *leaf;
6554 struct inode *reloc_inode;
6555 struct btrfs_block_group_cache *block_group;
6556 struct btrfs_key key;
6565 root = root->fs_info->extent_root;
6567 block_group = btrfs_lookup_block_group(info, group_start);
6568 BUG_ON(!block_group);
6570 printk(KERN_INFO "btrfs relocating block group %llu flags %llu\n",
6571 (unsigned long long)block_group->key.objectid,
6572 (unsigned long long)block_group->flags);
6574 path = btrfs_alloc_path();
6577 reloc_inode = create_reloc_inode(info, block_group);
6578 BUG_ON(IS_ERR(reloc_inode));
6580 __alloc_chunk_for_shrink(root, block_group, 1);
6581 set_block_group_readonly(block_group);
6583 btrfs_start_delalloc_inodes(info->tree_root);
6584 btrfs_wait_ordered_extents(info->tree_root, 0);
6589 key.objectid = block_group->key.objectid;
6592 cur_byte = key.objectid;
6594 trans = btrfs_start_transaction(info->tree_root, 1);
6595 btrfs_commit_transaction(trans, info->tree_root);
6597 mutex_lock(&root->fs_info->cleaner_mutex);
6598 btrfs_clean_old_snapshots(info->tree_root);
6599 btrfs_remove_leaf_refs(info->tree_root, (u64)-1, 1);
6600 mutex_unlock(&root->fs_info->cleaner_mutex);
6602 trans = btrfs_start_transaction(info->tree_root, 1);
6603 btrfs_commit_transaction(trans, info->tree_root);
6606 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
6610 leaf = path->nodes[0];
6611 nritems = btrfs_header_nritems(leaf);
6612 if (path->slots[0] >= nritems) {
6613 ret = btrfs_next_leaf(root, path);
6620 leaf = path->nodes[0];
6621 nritems = btrfs_header_nritems(leaf);
6624 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
6626 if (key.objectid >= block_group->key.objectid +
6627 block_group->key.offset)
6630 if (progress && need_resched()) {
6631 btrfs_release_path(root, path);
6638 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY ||
6639 key.objectid + key.offset <= cur_byte) {
6645 cur_byte = key.objectid + key.offset;
6646 btrfs_release_path(root, path);
6648 __alloc_chunk_for_shrink(root, block_group, 0);
6649 ret = relocate_one_extent(root, path, &key, block_group,
6655 key.objectid = cur_byte;
6660 btrfs_release_path(root, path);
6663 btrfs_wait_ordered_range(reloc_inode, 0, (u64)-1);
6664 invalidate_mapping_pages(reloc_inode->i_mapping, 0, -1);
6667 if (total_found > 0) {
6668 printk(KERN_INFO "btrfs found %llu extents in pass %d\n",
6669 (unsigned long long)total_found, pass);
6671 if (total_found == skipped && pass > 2) {
6673 reloc_inode = create_reloc_inode(info, block_group);
6679 /* delete reloc_inode */
6682 /* unpin extents in this range */
6683 trans = btrfs_start_transaction(info->tree_root, 1);
6684 btrfs_commit_transaction(trans, info->tree_root);
6686 spin_lock(&block_group->lock);
6687 WARN_ON(block_group->pinned > 0);
6688 WARN_ON(block_group->reserved > 0);
6689 WARN_ON(btrfs_block_group_used(&block_group->item) > 0);
6690 spin_unlock(&block_group->lock);
6691 btrfs_put_block_group(block_group);
6694 btrfs_free_path(path);
6699 static int find_first_block_group(struct btrfs_root *root,
6700 struct btrfs_path *path, struct btrfs_key *key)
6703 struct btrfs_key found_key;
6704 struct extent_buffer *leaf;
6707 ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
6712 slot = path->slots[0];
6713 leaf = path->nodes[0];
6714 if (slot >= btrfs_header_nritems(leaf)) {
6715 ret = btrfs_next_leaf(root, path);
6722 btrfs_item_key_to_cpu(leaf, &found_key, slot);
6724 if (found_key.objectid >= key->objectid &&
6725 found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
6736 int btrfs_free_block_groups(struct btrfs_fs_info *info)
6738 struct btrfs_block_group_cache *block_group;
6739 struct btrfs_space_info *space_info;
6742 spin_lock(&info->block_group_cache_lock);
6743 while ((n = rb_last(&info->block_group_cache_tree)) != NULL) {
6744 block_group = rb_entry(n, struct btrfs_block_group_cache,
6746 rb_erase(&block_group->cache_node,
6747 &info->block_group_cache_tree);
6748 spin_unlock(&info->block_group_cache_lock);
6750 btrfs_remove_free_space_cache(block_group);
6751 down_write(&block_group->space_info->groups_sem);
6752 list_del(&block_group->list);
6753 up_write(&block_group->space_info->groups_sem);
6755 WARN_ON(atomic_read(&block_group->count) != 1);
6758 spin_lock(&info->block_group_cache_lock);
6760 spin_unlock(&info->block_group_cache_lock);
6762 /* now that all the block groups are freed, go through and
6763 * free all the space_info structs. This is only called during
6764 * the final stages of unmount, and so we know nobody is
6765 * using them. We call synchronize_rcu() once before we start,
6766 * just to be on the safe side.
6770 while(!list_empty(&info->space_info)) {
6771 space_info = list_entry(info->space_info.next,
6772 struct btrfs_space_info,
6775 list_del(&space_info->list);
6781 int btrfs_read_block_groups(struct btrfs_root *root)
6783 struct btrfs_path *path;
6785 struct btrfs_block_group_cache *cache;
6786 struct btrfs_fs_info *info = root->fs_info;
6787 struct btrfs_space_info *space_info;
6788 struct btrfs_key key;
6789 struct btrfs_key found_key;
6790 struct extent_buffer *leaf;
6792 root = info->extent_root;
6795 btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
6796 path = btrfs_alloc_path();
6801 ret = find_first_block_group(root, path, &key);
6809 leaf = path->nodes[0];
6810 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
6811 cache = kzalloc(sizeof(*cache), GFP_NOFS);
6817 atomic_set(&cache->count, 1);
6818 spin_lock_init(&cache->lock);
6819 spin_lock_init(&cache->tree_lock);
6820 mutex_init(&cache->cache_mutex);
6821 INIT_LIST_HEAD(&cache->list);
6822 INIT_LIST_HEAD(&cache->cluster_list);
6823 read_extent_buffer(leaf, &cache->item,
6824 btrfs_item_ptr_offset(leaf, path->slots[0]),
6825 sizeof(cache->item));
6826 memcpy(&cache->key, &found_key, sizeof(found_key));
6828 key.objectid = found_key.objectid + found_key.offset;
6829 btrfs_release_path(root, path);
6830 cache->flags = btrfs_block_group_flags(&cache->item);
6832 ret = update_space_info(info, cache->flags, found_key.offset,
6833 btrfs_block_group_used(&cache->item),
6836 cache->space_info = space_info;
6837 down_write(&space_info->groups_sem);
6838 list_add_tail(&cache->list, &space_info->block_groups);
6839 up_write(&space_info->groups_sem);
6841 ret = btrfs_add_block_group_cache(root->fs_info, cache);
6844 set_avail_alloc_bits(root->fs_info, cache->flags);
6845 if (btrfs_chunk_readonly(root, cache->key.objectid))
6846 set_block_group_readonly(cache);
6850 btrfs_free_path(path);
6854 int btrfs_make_block_group(struct btrfs_trans_handle *trans,
6855 struct btrfs_root *root, u64 bytes_used,
6856 u64 type, u64 chunk_objectid, u64 chunk_offset,
6860 struct btrfs_root *extent_root;
6861 struct btrfs_block_group_cache *cache;
6863 extent_root = root->fs_info->extent_root;
6865 root->fs_info->last_trans_log_full_commit = trans->transid;
6867 cache = kzalloc(sizeof(*cache), GFP_NOFS);
6871 cache->key.objectid = chunk_offset;
6872 cache->key.offset = size;
6873 cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
6874 atomic_set(&cache->count, 1);
6875 spin_lock_init(&cache->lock);
6876 spin_lock_init(&cache->tree_lock);
6877 mutex_init(&cache->cache_mutex);
6878 INIT_LIST_HEAD(&cache->list);
6879 INIT_LIST_HEAD(&cache->cluster_list);
6881 btrfs_set_block_group_used(&cache->item, bytes_used);
6882 btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
6883 cache->flags = type;
6884 btrfs_set_block_group_flags(&cache->item, type);
6886 ret = update_space_info(root->fs_info, cache->flags, size, bytes_used,
6887 &cache->space_info);
6889 down_write(&cache->space_info->groups_sem);
6890 list_add_tail(&cache->list, &cache->space_info->block_groups);
6891 up_write(&cache->space_info->groups_sem);
6893 ret = btrfs_add_block_group_cache(root->fs_info, cache);
6896 ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
6897 sizeof(cache->item));
6900 set_avail_alloc_bits(extent_root->fs_info, type);
6905 int btrfs_remove_block_group(struct btrfs_trans_handle *trans,
6906 struct btrfs_root *root, u64 group_start)
6908 struct btrfs_path *path;
6909 struct btrfs_block_group_cache *block_group;
6910 struct btrfs_free_cluster *cluster;
6911 struct btrfs_key key;
6914 root = root->fs_info->extent_root;
6916 block_group = btrfs_lookup_block_group(root->fs_info, group_start);
6917 BUG_ON(!block_group);
6918 BUG_ON(!block_group->ro);
6920 memcpy(&key, &block_group->key, sizeof(key));
6922 /* make sure this block group isn't part of an allocation cluster */
6923 cluster = &root->fs_info->data_alloc_cluster;
6924 spin_lock(&cluster->refill_lock);
6925 btrfs_return_cluster_to_free_space(block_group, cluster);
6926 spin_unlock(&cluster->refill_lock);
6929 * make sure this block group isn't part of a metadata
6930 * allocation cluster
6932 cluster = &root->fs_info->meta_alloc_cluster;
6933 spin_lock(&cluster->refill_lock);
6934 btrfs_return_cluster_to_free_space(block_group, cluster);
6935 spin_unlock(&cluster->refill_lock);
6937 path = btrfs_alloc_path();
6940 spin_lock(&root->fs_info->block_group_cache_lock);
6941 rb_erase(&block_group->cache_node,
6942 &root->fs_info->block_group_cache_tree);
6943 spin_unlock(&root->fs_info->block_group_cache_lock);
6944 btrfs_remove_free_space_cache(block_group);
6945 down_write(&block_group->space_info->groups_sem);
6947 * we must use list_del_init so people can check to see if they
6948 * are still on the list after taking the semaphore
6950 list_del_init(&block_group->list);
6951 up_write(&block_group->space_info->groups_sem);
6953 spin_lock(&block_group->space_info->lock);
6954 block_group->space_info->total_bytes -= block_group->key.offset;
6955 block_group->space_info->bytes_readonly -= block_group->key.offset;
6956 spin_unlock(&block_group->space_info->lock);
6957 block_group->space_info->full = 0;
6959 btrfs_put_block_group(block_group);
6960 btrfs_put_block_group(block_group);
6962 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
6968 ret = btrfs_del_item(trans, root, path);
6970 btrfs_free_path(path);