Btrfs: Mixed back reference (FORWARD ROLLING FORMAT CHANGE)

This commit introduces a new kind of back reference for btrfs metadata.
Once a filesystem has been mounted with this commit, IT WILL NO LONGER
BE MOUNTABLE BY OLDER KERNELS.

When a tree block in subvolume tree is cow'd, the reference counts of all
extents it points to are increased by one.  At transaction commit time,
the old root of the subvolume is recorded in a "dead root" data structure,
and the btree it points to is later walked, dropping reference counts
and freeing any blocks where the reference count goes to 0.

The increments done during cow and decrements done after commit cancel out,
and the walk is a very expensive way to go about freeing the blocks that
are no longer referenced by the new btree root.  This commit reduces the
transaction overhead by avoiding the need for dead root records.

When a non-shared tree block is cow'd, we free the old block at once, and the
new block inherits old block's references. When a tree block with reference
count > 1 is cow'd, we increase the reference counts of all extents
the new block points to by one, and decrease the old block's reference count by
one.

This dead tree avoidance code removes the need to modify the reference
counts of lower level extents when a non-shared tree block is cow'd.
But we still need to update back ref for all pointers in the block.
This is because the location of the block is recorded in the back ref
item.

We can solve this by introducing a new type of back ref. The new
back ref provides information about pointer's key, level and in which
tree the pointer lives. This information allow us to find the pointer
by searching the tree. The shortcoming of the new back ref is that it
only works for pointers in tree blocks referenced by their owner trees.

This is mostly a problem for snapshots, where resolving one of these
fuzzy back references would be O(number_of_snapshots) and quite slow.
The solution used here is to use the fuzzy back references in the common
case where a given tree block is only referenced by one root,
and use the full back references when multiple roots have a reference
on a given block.

This commit adds per subvolume red-black tree to keep trace of cached
inodes. The red-black tree helps the balancing code to find cached
inodes whose inode numbers within a given range.

This commit improves the balancing code by introducing several data
structures to keep the state of balancing. The most important one
is the back ref cache. It caches how the upper level tree blocks are
referenced. This greatly reduce the overhead of checking back ref.

The improved balancing code scales significantly better with a large
number of snapshots.

This is a very large commit and was written in a number of
pieces.  But, they depend heavily on the disk format change and were
squashed together to make sure git bisect didn't end up in a
bad state wrt space balancing or the format change.

Signed-off-by: Yan Zheng <zheng.yan@oracle.com>
Signed-off-by: Chris Mason <chris.mason@oracle.com>

1 files changed, 203 insertions, 105 deletions

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 4414a5d9983a..ce3ab4e13064 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -45,6 +45,8 @@ struct btrfs_ordered_sum;
 
 #define BTRFS_MAX_LEVEL 8
 
+#define BTRFS_COMPAT_EXTENT_TREE_V0
+
 /*
  * files bigger than this get some pre-flushing when they are added
  * to the ordered operations list.  That way we limit the total
@@ -267,7 +269,18 @@ static inline unsigned long btrfs_chunk_item_size(int num_stripes)
 }
 
 #define BTRFS_FSID_SIZE 16
-#define BTRFS_HEADER_FLAG_WRITTEN (1 << 0)
+#define BTRFS_HEADER_FLAG_WRITTEN       (1ULL << 0)
+#define BTRFS_HEADER_FLAG_RELOC         (1ULL << 1)
+#define BTRFS_SUPER_FLAG_SEEDING        (1ULL << 32)
+#define BTRFS_SUPER_FLAG_METADUMP       (1ULL << 33)
+
+#define BTRFS_BACKREF_REV_MAX           256
+#define BTRFS_BACKREF_REV_SHIFT         56
+#define BTRFS_BACKREF_REV_MASK          (((u64)BTRFS_BACKREF_REV_MAX - 1) << \
+                                         BTRFS_BACKREF_REV_SHIFT)
+
+#define BTRFS_OLD_BACKREF_REV           0
+#define BTRFS_MIXED_BACKREF_REV         1
 
 /*
  * every tree block (leaf or node) starts with this header.
@@ -296,7 +309,6 @@ struct btrfs_header {
                                         sizeof(struct btrfs_item) - \
                                         sizeof(struct btrfs_file_extent_item))
 
-#define BTRFS_SUPER_FLAG_SEEDING (1ULL << 32)
 
 /*
  * this is a very generous portion of the super block, giving us
@@ -355,9 +367,12 @@ struct btrfs_super_block {
  * Compat flags that we support.  If any incompat flags are set other than the
  * ones specified below then we will fail to mount
  */
-#define BTRFS_FEATURE_COMPAT_SUPP       0x0
-#define BTRFS_FEATURE_COMPAT_RO_SUPP    0x0
-#define BTRFS_FEATURE_INCOMPAT_SUPP     0x0
+#define BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF    (1ULL << 0)
+
+#define BTRFS_FEATURE_COMPAT_SUPP               0ULL
+#define BTRFS_FEATURE_COMPAT_RO_SUPP            0ULL
+#define BTRFS_FEATURE_INCOMPAT_SUPP             \
+        BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF
 
 /*
  * A leaf is full of items. offset and size tell us where to find
@@ -421,23 +436,65 @@ struct btrfs_path {
         unsigned int keep_locks:1;
         unsigned int skip_locking:1;
         unsigned int leave_spinning:1;
+        unsigned int search_commit_root:1;
 };
 
 /*
  * items in the extent btree are used to record the objectid of the
  * owner of the block and the number of references
  */
+
 struct btrfs_extent_item {
+        __le64 refs;
+        __le64 generation;
+        __le64 flags;
+} __attribute__ ((__packed__));
+
+struct btrfs_extent_item_v0 {
         __le32 refs;
 } __attribute__ ((__packed__));
 
-struct btrfs_extent_ref {
+#define BTRFS_MAX_EXTENT_ITEM_SIZE(r) ((BTRFS_LEAF_DATA_SIZE(r) >> 4) - \
+                                        sizeof(struct btrfs_item))
+
+#define BTRFS_EXTENT_FLAG_DATA          (1ULL << 0)
+#define BTRFS_EXTENT_FLAG_TREE_BLOCK    (1ULL << 1)
+
+/* following flags only apply to tree blocks */
+
+/* use full backrefs for extent pointers in the block */
+#define BTRFS_BLOCK_FLAG_FULL_BACKREF   (1ULL << 8)
+
+struct btrfs_tree_block_info {
+        struct btrfs_disk_key key;
+        u8 level;
+} __attribute__ ((__packed__));
+
+struct btrfs_extent_data_ref {
+        __le64 root;
+        __le64 objectid;
+        __le64 offset;
+        __le32 count;
+} __attribute__ ((__packed__));
+
+struct btrfs_shared_data_ref {
+        __le32 count;
+} __attribute__ ((__packed__));
+
+struct btrfs_extent_inline_ref {
+        u8 type;
+        u64 offset;
+} __attribute__ ((__packed__));
+
+/* old style backrefs item */
+struct btrfs_extent_ref_v0 {
         __le64 root;
         __le64 generation;
         __le64 objectid;
-        __le32 num_refs;
+        __le32 count;
 } __attribute__ ((__packed__));
 
+
 /* dev extents record free space on individual devices.  The owner
  * field points back to the chunk allocation mapping tree that allocated
  * the extent.  The chunk tree uuid field is a way to double check the owner
@@ -695,12 +752,7 @@ struct btrfs_block_group_cache {
         struct list_head cluster_list;
 };
 
-struct btrfs_leaf_ref_tree {
-        struct rb_root root;
-        struct list_head list;
-        spinlock_t lock;
-};
-
+struct reloc_control;
 struct btrfs_device;
 struct btrfs_fs_devices;
 struct btrfs_fs_info {
@@ -831,18 +883,11 @@ struct btrfs_fs_info {
         struct task_struct *cleaner_kthread;
         int thread_pool_size;
 
-        /* tree relocation relocated fields */
-        struct list_head dead_reloc_roots;
-        struct btrfs_leaf_ref_tree reloc_ref_tree;
-        struct btrfs_leaf_ref_tree shared_ref_tree;
-
         struct kobject super_kobj;
         struct completion kobj_unregister;
         int do_barriers;
         int closing;
         int log_root_recovering;
-        atomic_t throttles;
-        atomic_t throttle_gen;
 
         u64 total_pinned;
 
@@ -861,6 +906,8 @@ struct btrfs_fs_info {
          */
         struct list_head space_info;
 
+        struct reloc_control *reloc_ctl;
+
         spinlock_t delalloc_lock;
         spinlock_t new_trans_lock;
         u64 delalloc_bytes;
@@ -891,7 +938,6 @@ struct btrfs_fs_info {
  * in ram representation of the tree.  extent_root is used for all allocations
  * and for the extent tree extent_root root.
  */
-struct btrfs_dirty_root;
 struct btrfs_root {
         struct extent_buffer *node;
 
@@ -899,9 +945,6 @@ struct btrfs_root {
         spinlock_t node_lock;
 
         struct extent_buffer *commit_root;
-        struct btrfs_leaf_ref_tree *ref_tree;
-        struct btrfs_leaf_ref_tree ref_tree_struct;
-        struct btrfs_dirty_root *dirty_root;
         struct btrfs_root *log_root;
         struct btrfs_root *reloc_root;
 
@@ -952,10 +995,15 @@ struct btrfs_root {
         /* the dirty list is only used by non-reference counted roots */
         struct list_head dirty_list;
 
+        struct list_head root_list;
+
         spinlock_t list_lock;
-        struct list_head dead_list;
         struct list_head orphan_list;
 
+        spinlock_t inode_lock;
+        /* red-black tree that keeps track of in-memory inodes */
+        struct rb_root inode_tree;
+
         /*
          * right now this just gets used so that a root has its own devid
          * for stat.  It may be used for more later
@@ -1017,7 +1065,16 @@ struct btrfs_root {
  * are used, and how many references there are to each block
  */
 #define BTRFS_EXTENT_ITEM_KEY   168
-#define BTRFS_EXTENT_REF_KEY    180
+
+#define BTRFS_TREE_BLOCK_REF_KEY        176
+
+#define BTRFS_EXTENT_DATA_REF_KEY       178
+
+#define BTRFS_EXTENT_REF_V0_KEY         180
+
+#define BTRFS_SHARED_BLOCK_REF_KEY      182
+
+#define BTRFS_SHARED_DATA_REF_KEY       184
 
 /*
  * block groups give us hints into the extent allocation trees.  Which
@@ -1317,24 +1374,67 @@ static inline u8 *btrfs_dev_extent_chunk_tree_uuid(struct btrfs_dev_extent *dev)
         return (u8 *)((unsigned long)dev + ptr);
 }
 
-/* struct btrfs_extent_ref */
-BTRFS_SETGET_FUNCS(ref_root, struct btrfs_extent_ref, root, 64);
-BTRFS_SETGET_FUNCS(ref_generation, struct btrfs_extent_ref, generation, 64);
-BTRFS_SETGET_FUNCS(ref_objectid, struct btrfs_extent_ref, objectid, 64);
-BTRFS_SETGET_FUNCS(ref_num_refs, struct btrfs_extent_ref, num_refs, 32);
+BTRFS_SETGET_FUNCS(extent_refs, struct btrfs_extent_item, refs, 64);
+BTRFS_SETGET_FUNCS(extent_generation, struct btrfs_extent_item,
+                   generation, 64);
+BTRFS_SETGET_FUNCS(extent_flags, struct btrfs_extent_item, flags, 64);
 
-BTRFS_SETGET_STACK_FUNCS(stack_ref_root, struct btrfs_extent_ref, root, 64);
-BTRFS_SETGET_STACK_FUNCS(stack_ref_generation, struct btrfs_extent_ref,
-                         generation, 64);
-BTRFS_SETGET_STACK_FUNCS(stack_ref_objectid, struct btrfs_extent_ref,
-                         objectid, 64);
-BTRFS_SETGET_STACK_FUNCS(stack_ref_num_refs, struct btrfs_extent_ref,
-                         num_refs, 32);
+BTRFS_SETGET_FUNCS(extent_refs_v0, struct btrfs_extent_item_v0, refs, 32);
+
+
+BTRFS_SETGET_FUNCS(tree_block_level, struct btrfs_tree_block_info, level, 8);
+
+static inline void btrfs_tree_block_key(struct extent_buffer *eb,
+                                        struct btrfs_tree_block_info *item,
+                                        struct btrfs_disk_key *key)
+{
+        read_eb_member(eb, item, struct btrfs_tree_block_info, key, key);
+}
+
+static inline void btrfs_set_tree_block_key(struct extent_buffer *eb,
+                                            struct btrfs_tree_block_info *item,
+                                            struct btrfs_disk_key *key)
+{
+        write_eb_member(eb, item, struct btrfs_tree_block_info, key, key);
+}
 
-/* struct btrfs_extent_item */
-BTRFS_SETGET_FUNCS(extent_refs, struct btrfs_extent_item, refs, 32);
-BTRFS_SETGET_STACK_FUNCS(stack_extent_refs, struct btrfs_extent_item,
-                         refs, 32);
+BTRFS_SETGET_FUNCS(extent_data_ref_root, struct btrfs_extent_data_ref,
+                   root, 64);
+BTRFS_SETGET_FUNCS(extent_data_ref_objectid, struct btrfs_extent_data_ref,
+                   objectid, 64);
+BTRFS_SETGET_FUNCS(extent_data_ref_offset, struct btrfs_extent_data_ref,
+                   offset, 64);
+BTRFS_SETGET_FUNCS(extent_data_ref_count, struct btrfs_extent_data_ref,
+                   count, 32);
+
+BTRFS_SETGET_FUNCS(shared_data_ref_count, struct btrfs_shared_data_ref,
+                   count, 32);
+
+BTRFS_SETGET_FUNCS(extent_inline_ref_type, struct btrfs_extent_inline_ref,
+                   type, 8);
+BTRFS_SETGET_FUNCS(extent_inline_ref_offset, struct btrfs_extent_inline_ref,
+                   offset, 64);
+
+static inline u32 btrfs_extent_inline_ref_size(int type)
+{
+        if (type == BTRFS_TREE_BLOCK_REF_KEY ||
+            type == BTRFS_SHARED_BLOCK_REF_KEY)
+                return sizeof(struct btrfs_extent_inline_ref);
+        if (type == BTRFS_SHARED_DATA_REF_KEY)
+                return sizeof(struct btrfs_shared_data_ref) +
+                       sizeof(struct btrfs_extent_inline_ref);
+        if (type == BTRFS_EXTENT_DATA_REF_KEY)
+                return sizeof(struct btrfs_extent_data_ref) +
+                       offsetof(struct btrfs_extent_inline_ref, offset);
+        BUG();
+        return 0;
+}
+
+BTRFS_SETGET_FUNCS(ref_root_v0, struct btrfs_extent_ref_v0, root, 64);
+BTRFS_SETGET_FUNCS(ref_generation_v0, struct btrfs_extent_ref_v0,
+                   generation, 64);
+BTRFS_SETGET_FUNCS(ref_objectid_v0, struct btrfs_extent_ref_v0, objectid, 64);
+BTRFS_SETGET_FUNCS(ref_count_v0, struct btrfs_extent_ref_v0, count, 32);
 
 /* struct btrfs_node */
 BTRFS_SETGET_FUNCS(key_blockptr, struct btrfs_key_ptr, blockptr, 64);
@@ -1558,6 +1658,21 @@ static inline int btrfs_clear_header_flag(struct extent_buffer *eb, u64 flag)
         return (flags & flag) == flag;
 }
 
+static inline int btrfs_header_backref_rev(struct extent_buffer *eb)
+{
+        u64 flags = btrfs_header_flags(eb);
+        return flags >> BTRFS_BACKREF_REV_SHIFT;
+}
+
+static inline void btrfs_set_header_backref_rev(struct extent_buffer *eb,
+                                                int rev)
+{
+        u64 flags = btrfs_header_flags(eb);
+        flags &= ~BTRFS_BACKREF_REV_MASK;
+        flags |= (u64)rev << BTRFS_BACKREF_REV_SHIFT;
+        btrfs_set_header_flags(eb, flags);
+}
+
 static inline u8 *btrfs_header_fsid(struct extent_buffer *eb)
 {
         unsigned long ptr = offsetof(struct btrfs_header, fsid);
@@ -1790,39 +1905,32 @@ int btrfs_update_pinned_extents(struct btrfs_root *root,
 int btrfs_drop_leaf_ref(struct btrfs_trans_handle *trans,
                         struct btrfs_root *root, struct extent_buffer *leaf);
 int btrfs_cross_ref_exist(struct btrfs_trans_handle *trans,
-                          struct btrfs_root *root, u64 objectid, u64 bytenr);
+                          struct btrfs_root *root,
+                          u64 objectid, u64 offset, u64 bytenr);
 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy);
 struct btrfs_block_group_cache *btrfs_lookup_block_group(
                                                  struct btrfs_fs_info *info,
                                                  u64 bytenr);
+void btrfs_put_block_group(struct btrfs_block_group_cache *cache);
 u64 btrfs_find_block_group(struct btrfs_root *root,
                            u64 search_start, u64 search_hint, int owner);
 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
-                                             struct btrfs_root *root,
-                                             u32 blocksize, u64 parent,
-                                             u64 root_objectid,
-                                             u64 ref_generation,
-                                             int level,
-                                             u64 hint,
-                                             u64 empty_size);
+                                        struct btrfs_root *root, u32 blocksize,
+                                        u64 parent, u64 root_objectid,
+                                        struct btrfs_disk_key *key, int level,
+                                        u64 hint, u64 empty_size);
 struct extent_buffer *btrfs_init_new_buffer(struct btrfs_trans_handle *trans,
                                             struct btrfs_root *root,
                                             u64 bytenr, u32 blocksize,
                                             int level);
-int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
-                       struct btrfs_root *root,
-                       u64 num_bytes, u64 parent, u64 min_bytes,
-                       u64 root_objectid, u64 ref_generation,
-                       u64 owner, u64 empty_size, u64 hint_byte,
-                       u64 search_end, struct btrfs_key *ins, u64 data);
-int btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
-                                struct btrfs_root *root, u64 parent,
-                                u64 root_objectid, u64 ref_generation,
-                                u64 owner, struct btrfs_key *ins);
-int btrfs_alloc_logged_extent(struct btrfs_trans_handle *trans,
-                                struct btrfs_root *root, u64 parent,
-                                u64 root_objectid, u64 ref_generation,
-                                u64 owner, struct btrfs_key *ins);
+int btrfs_alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
+                                     struct btrfs_root *root,
+                                     u64 root_objectid, u64 owner,
+                                     u64 offset, struct btrfs_key *ins);
+int btrfs_alloc_logged_file_extent(struct btrfs_trans_handle *trans,
+                                   struct btrfs_root *root,
+                                   u64 root_objectid, u64 owner, u64 offset,
+                                   struct btrfs_key *ins);
 int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
                                   struct btrfs_root *root,
                                   u64 num_bytes, u64 min_alloc_size,
@@ -1830,18 +1938,18 @@ int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
                                   u64 search_end, struct btrfs_key *ins,
                                   u64 data);
 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
-                  struct extent_buffer *orig_buf, struct extent_buffer *buf,
-                  u32 *nr_extents);
-int btrfs_cache_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
-                    struct extent_buffer *buf, u32 nr_extents);
-int btrfs_update_ref(struct btrfs_trans_handle *trans,
-                     struct btrfs_root *root, struct extent_buffer *orig_buf,
-                     struct extent_buffer *buf, int start_slot, int nr);
+                  struct extent_buffer *buf, int full_backref);
+int btrfs_dec_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
+                  struct extent_buffer *buf, int full_backref);
+int btrfs_set_disk_extent_flags(struct btrfs_trans_handle *trans,
+                                struct btrfs_root *root,
+                                u64 bytenr, u64 num_bytes, u64 flags,
+                                int is_data);
 int btrfs_free_extent(struct btrfs_trans_handle *trans,
                       struct btrfs_root *root,
                       u64 bytenr, u64 num_bytes, u64 parent,
-                      u64 root_objectid, u64 ref_generation,
-                      u64 owner_objectid, int pin);
+                      u64 root_objectid, u64 owner, u64 offset);
+
 int btrfs_free_reserved_extent(struct btrfs_root *root, u64 start, u64 len);
 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
                                struct btrfs_root *root,
@@ -1849,13 +1957,8 @@ int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
                          struct btrfs_root *root,
                          u64 bytenr, u64 num_bytes, u64 parent,
-                         u64 root_objectid, u64 ref_generation,
-                         u64 owner_objectid);
-int btrfs_update_extent_ref(struct btrfs_trans_handle *trans,
-                            struct btrfs_root *root, u64 bytenr, u64 num_bytes,
-                            u64 orig_parent, u64 parent,
-                            u64 root_objectid, u64 ref_generation,
-                            u64 owner_objectid);
+                         u64 root_objectid, u64 owner, u64 offset);
+
 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
                                     struct btrfs_root *root);
 int btrfs_extent_readonly(struct btrfs_root *root, u64 bytenr);
@@ -1867,16 +1970,9 @@ int btrfs_make_block_group(struct btrfs_trans_handle *trans,
                            u64 size);
 int btrfs_remove_block_group(struct btrfs_trans_handle *trans,
                              struct btrfs_root *root, u64 group_start);
-int btrfs_relocate_block_group(struct btrfs_root *root, u64 group_start);
-int btrfs_free_reloc_root(struct btrfs_trans_handle *trans,
-                          struct btrfs_root *root);
-int btrfs_drop_dead_reloc_roots(struct btrfs_root *root);
-int btrfs_reloc_tree_cache_ref(struct btrfs_trans_handle *trans,
-                               struct btrfs_root *root,
-                               struct extent_buffer *buf, u64 orig_start);
-int btrfs_add_dead_reloc_root(struct btrfs_root *root);
-int btrfs_cleanup_reloc_trees(struct btrfs_root *root);
-int btrfs_reloc_clone_csums(struct inode *inode, u64 file_pos, u64 len);
+int btrfs_prepare_block_group_relocation(struct btrfs_root *root,
+                                struct btrfs_block_group_cache *group);
+
 u64 btrfs_reduce_alloc_profile(struct btrfs_root *root, u64 flags);
 void btrfs_set_inode_space_info(struct btrfs_root *root, struct inode *ionde);
 void btrfs_clear_space_info_full(struct btrfs_fs_info *info);
@@ -1891,13 +1987,12 @@ void btrfs_delalloc_reserve_space(struct btrfs_root *root, struct inode *inode,
 void btrfs_delalloc_free_space(struct btrfs_root *root, struct inode *inode,
                               u64 bytes);
 /* ctree.c */
+int btrfs_bin_search(struct extent_buffer *eb, struct btrfs_key *key,
+                     int level, int *slot);
+int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2);
 int btrfs_previous_item(struct btrfs_root *root,
                         struct btrfs_path *path, u64 min_objectid,
                         int type);
-int btrfs_merge_path(struct btrfs_trans_handle *trans,
-                     struct btrfs_root *root,
-                     struct btrfs_key *node_keys,
-                     u64 *nodes, int lowest_level);
 int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
                             struct btrfs_root *root, struct btrfs_path *path,
                             struct btrfs_key *new_key);
@@ -1918,6 +2013,8 @@ int btrfs_copy_root(struct btrfs_trans_handle *trans,
                       struct btrfs_root *root,
                       struct extent_buffer *buf,
                       struct extent_buffer **cow_ret, u64 new_root_objectid);
+int btrfs_block_can_be_shared(struct btrfs_root *root,
+                              struct extent_buffer *buf);
 int btrfs_extend_item(struct btrfs_trans_handle *trans, struct btrfs_root
                       *root, struct btrfs_path *path, u32 data_size);
 int btrfs_truncate_item(struct btrfs_trans_handle *trans,
@@ -1944,9 +2041,6 @@ void btrfs_unlock_up_safe(struct btrfs_path *p, int level);
 
 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
                    struct btrfs_path *path, int slot, int nr);
-int btrfs_del_leaf(struct btrfs_trans_handle *trans,
-                            struct btrfs_root *root,
-                            struct btrfs_path *path, u64 bytenr);
 static inline int btrfs_del_item(struct btrfs_trans_handle *trans,
                                  struct btrfs_root *root,
                                  struct btrfs_path *path)
@@ -2005,8 +2099,9 @@ int btrfs_find_last_root(struct btrfs_root *root, u64 objectid, struct
                          btrfs_root_item *item, struct btrfs_key *key);
 int btrfs_search_root(struct btrfs_root *root, u64 search_start,
                       u64 *found_objectid);
-int btrfs_find_dead_roots(struct btrfs_root *root, u64 objectid,
-                          struct btrfs_root *latest_root);
+int btrfs_find_dead_roots(struct btrfs_root *root, u64 objectid);
+int btrfs_set_root_node(struct btrfs_root_item *item,
+                        struct extent_buffer *node);
 /* dir-item.c */
 int btrfs_insert_dir_item(struct btrfs_trans_handle *trans,
                           struct btrfs_root *root, const char *name,
@@ -2139,7 +2234,6 @@ int btrfs_page_mkwrite(struct vm_area_struct *vma, struct vm_fault *vmf);
 int btrfs_readpage(struct file *file, struct page *page);
 void btrfs_delete_inode(struct inode *inode);
 void btrfs_put_inode(struct inode *inode);
-void btrfs_read_locked_inode(struct inode *inode);
 int btrfs_write_inode(struct inode *inode, int wait);
 void btrfs_dirty_inode(struct inode *inode);
 struct inode *btrfs_alloc_inode(struct super_block *sb);
@@ -2147,12 +2241,8 @@ void btrfs_destroy_inode(struct inode *inode);
 int btrfs_init_cachep(void);
 void btrfs_destroy_cachep(void);
 long btrfs_ioctl_trans_end(struct file *file);
-struct inode *btrfs_ilookup(struct super_block *s, u64 objectid,
-                            struct btrfs_root *root, int wait);
-struct inode *btrfs_iget_locked(struct super_block *s, u64 objectid,
-                                struct btrfs_root *root);
 struct inode *btrfs_iget(struct super_block *s, struct btrfs_key *location,
-                         struct btrfs_root *root, int *is_new);
+                         struct btrfs_root *root);
 int btrfs_commit_write(struct file *file, struct page *page,
                        unsigned from, unsigned to);
 struct extent_map *btrfs_get_extent(struct inode *inode, struct page *page,
@@ -2209,4 +2299,12 @@ int btrfs_check_acl(struct inode *inode, int mask);
 int btrfs_init_acl(struct inode *inode, struct inode *dir);
 int btrfs_acl_chmod(struct inode *inode);
 
+/* relocation.c */
+int btrfs_relocate_block_group(struct btrfs_root *root, u64 group_start);
+int btrfs_init_reloc_root(struct btrfs_trans_handle *trans,
+                          struct btrfs_root *root);
+int btrfs_update_reloc_root(struct btrfs_trans_handle *trans,
+                            struct btrfs_root *root);
+int btrfs_recover_relocation(struct btrfs_root *root);
+int btrfs_reloc_clone_csums(struct inode *inode, u64 file_pos, u64 len);
 #endif