Btrfs: Add backrefs and forward refs for subvols and snapshots

Subvols and snapshots can now be referenced from any point in the directory
tree.  We need to maintain back refs for them so we can find lost
subvols.

Forward refs are added so that we know all of the subvols and
snapshots referenced anywhere in the directory tree of a single subvol.  This
can be used to do recursive snapshotting (but they aren't yet) and it is
also used to detect and prevent directory loops when creating new snapshots.

Signed-off-by: Chris Mason <chris.mason@oracle.com>

5 files changed, 172 insertions, 32 deletions

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index b3bc65b08c6a..ad2cbe63503c 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -469,6 +469,15 @@ struct btrfs_root_item {
         u8 level;
 } __attribute__ ((__packed__));
 
+/*
+ * this is used for both forward and backward root refs
+ */
+struct btrfs_root_ref {
+        __le64 dirid;
+        __le64 sequence;
+        __le16 name_len;
+} __attribute__ ((__packed__));
+
 #define BTRFS_FILE_EXTENT_INLINE 0
 #define BTRFS_FILE_EXTENT_REG 1
 #define BTRFS_FILE_EXTENT_PREALLOC 2
@@ -814,27 +823,27 @@ struct btrfs_root {
  * the FS
  */
 #define BTRFS_INODE_ITEM_KEY            1
-#define BTRFS_INODE_REF_KEY             2
-#define BTRFS_XATTR_ITEM_KEY            8
-#define BTRFS_ORPHAN_ITEM_KEY           9
+#define BTRFS_INODE_REF_KEY             12
+#define BTRFS_XATTR_ITEM_KEY            24
+#define BTRFS_ORPHAN_ITEM_KEY           48
 /* reserve 2-15 close to the inode for later flexibility */
 
 /*
  * dir items are the name -> inode pointers in a directory.  There is one
  * for every name in a directory.
  */
-#define BTRFS_DIR_LOG_ITEM_KEY  14
-#define BTRFS_DIR_LOG_INDEX_KEY 15
-#define BTRFS_DIR_ITEM_KEY      16
-#define BTRFS_DIR_INDEX_KEY     17
+#define BTRFS_DIR_LOG_ITEM_KEY  60
+#define BTRFS_DIR_LOG_INDEX_KEY 72
+#define BTRFS_DIR_ITEM_KEY      84
+#define BTRFS_DIR_INDEX_KEY     96
 /*
  * extent data is for file data
  */
-#define BTRFS_EXTENT_DATA_KEY   18
+#define BTRFS_EXTENT_DATA_KEY   108
 /*
  * csum items have the checksums for data in the extents
  */
-#define BTRFS_CSUM_ITEM_KEY     19
+#define BTRFS_CSUM_ITEM_KEY     120
 
 
 /* reserve 21-31 for other file/dir stuff */
@@ -843,23 +852,37 @@ struct btrfs_root {
  * root items point to tree roots.  There are typically in the root
  * tree used by the super block to find all the other trees
  */
-#define BTRFS_ROOT_ITEM_KEY     32
+#define BTRFS_ROOT_ITEM_KEY     132
+
+/*
+ * root backrefs tie subvols and snapshots to the directory entries that
+ * reference them
+ */
+#define BTRFS_ROOT_BACKREF_KEY  144
+
+/*
+ * root refs make a fast index for listing all of the snapshots and
+ * subvolumes referenced by a given root.  They point directly to the
+ * directory item in the root that references the subvol
+ */
+#define BTRFS_ROOT_REF_KEY      156
+
 /*
  * extent items are in the extent map tree.  These record which blocks
  * are used, and how many references there are to each block
  */
-#define BTRFS_EXTENT_ITEM_KEY   33
-#define BTRFS_EXTENT_REF_KEY    34
+#define BTRFS_EXTENT_ITEM_KEY   168
+#define BTRFS_EXTENT_REF_KEY    180
 
 /*
  * block groups give us hints into the extent allocation trees.  Which
  * blocks are free etc etc
  */
-#define BTRFS_BLOCK_GROUP_ITEM_KEY 50
+#define BTRFS_BLOCK_GROUP_ITEM_KEY 192
 
-#define BTRFS_DEV_EXTENT_KEY    75
-#define BTRFS_DEV_ITEM_KEY      76
-#define BTRFS_CHUNK_ITEM_KEY    77
+#define BTRFS_DEV_EXTENT_KEY    204
+#define BTRFS_DEV_ITEM_KEY      216
+#define BTRFS_CHUNK_ITEM_KEY    228
 
 /*
  * string items are for debugging.  They just store a short string of
@@ -1274,6 +1297,13 @@ static inline void btrfs_set_item_key(struct extent_buffer *eb,
 
 BTRFS_SETGET_FUNCS(dir_log_end, struct btrfs_dir_log_item, end, 64);
 
+/*
+ * struct btrfs_root_ref
+ */
+BTRFS_SETGET_FUNCS(root_ref_dirid, struct btrfs_root_ref, dirid, 64);
+BTRFS_SETGET_FUNCS(root_ref_sequence, struct btrfs_root_ref, sequence, 64);
+BTRFS_SETGET_FUNCS(root_ref_name_len, struct btrfs_root_ref, name_len, 16);
+
 /* struct btrfs_dir_item */
 BTRFS_SETGET_FUNCS(dir_data_len, struct btrfs_dir_item, data_len, 16);
 BTRFS_SETGET_FUNCS(dir_type, struct btrfs_dir_item, type, 8);
@@ -1771,6 +1801,11 @@ int btrfs_drop_subtree(struct btrfs_trans_handle *trans,
                         struct extent_buffer *node,
                         struct extent_buffer *parent);
 /* root-item.c */
+int btrfs_add_root_ref(struct btrfs_trans_handle *trans,
+                       struct btrfs_root *tree_root,
+                       u64 root_id, u8 type, u64 ref_id,
+                       u64 dirid, u64 sequence,
+                       const char *name, int name_len);
 int btrfs_del_root(struct btrfs_trans_handle *trans, struct btrfs_root *root,
                    struct btrfs_key *key);
 int btrfs_insert_root(struct btrfs_trans_handle *trans, struct btrfs_root
diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c
index 7ef79ce86e25..6854bf41856a 100644
--- a/fs/btrfs/inode.c
+++ b/fs/btrfs/inode.c
@@ -4580,6 +4580,12 @@ static int btrfs_rename(struct inode * old_dir, struct dentry *old_dentry,
                 return -ENOTEMPTY;
         }
 
+        /* to rename a snapshot or subvolume, we need to juggle the
+         * backrefs.  This isn't coded yet
+         */
+        if (old_inode->i_ino == BTRFS_FIRST_FREE_OBJECTID)
+                return -EXDEV;
+
         ret = btrfs_check_free_space(root, 1, 0);
         if (ret)
                 goto out_unlock;
diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index 773db07b5f72..536ae8837801 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -145,13 +145,23 @@ static noinline int create_subvol(struct btrfs_root *root,
                                     BTRFS_FT_DIR, index);
         if (ret)
                 goto fail;
-#if 0
-        ret = btrfs_insert_inode_ref(trans, root->fs_info->tree_root,
-                             name, namelen, objectid,
-                             root->fs_info->sb->s_root->d_inode->i_ino, 0);
-        if (ret)
-                goto fail;
-#endif
+
+        /* add the backref first */
+        ret = btrfs_add_root_ref(trans, root->fs_info->tree_root,
+                                 objectid, BTRFS_ROOT_BACKREF_KEY,
+                                 root->root_key.objectid,
+                                 dir->i_ino, index, name, namelen);
+
+        BUG_ON(ret);
+
+        /* now add the forward ref */
+        ret = btrfs_add_root_ref(trans, root->fs_info->tree_root,
+                                 root->root_key.objectid, BTRFS_ROOT_REF_KEY,
+                                 objectid,
+                                 dir->i_ino, index, name, namelen);
+
+        BUG_ON(ret);
+
         ret = btrfs_commit_transaction(trans, root);
         if (ret)
                 goto fail_commit;
diff --git a/fs/btrfs/root-tree.c b/fs/btrfs/root-tree.c
index eb7f7655e9d5..e9be3abcb368 100644
--- a/fs/btrfs/root-tree.c
+++ b/fs/btrfs/root-tree.c
@@ -84,7 +84,7 @@ int btrfs_find_last_root(struct btrfs_root *root, u64 objectid,
         int slot;
 
         search_key.objectid = objectid;
-        search_key.type = (u8)-1;
+        search_key.type = BTRFS_ROOT_ITEM_KEY;
         search_key.offset = (u64)-1;
 
         path = btrfs_alloc_path();
@@ -275,3 +275,77 @@ out:
         btrfs_free_path(path);
         return ret;
 }
+
+int btrfs_del_root_ref(struct btrfs_trans_handle *trans,
+                       struct btrfs_root *tree_root,
+                       u64 root_id, u8 type, u64 ref_id)
+{
+        struct btrfs_key key;
+        int ret;
+        struct btrfs_path *path;
+
+        path = btrfs_alloc_path();
+
+        key.objectid = root_id;
+        key.type = type;
+        key.offset = ref_id;
+
+        ret = btrfs_search_slot(trans, tree_root, &key, path, -1, 1);
+        BUG_ON(ret);
+
+        ret = btrfs_del_item(trans, tree_root, path);
+        BUG_ON(ret);
+
+        btrfs_free_path(path);
+        return ret;
+}
+
+/*
+ * add a btrfs_root_ref item.  type is either BTRFS_ROOT_REF_KEY
+ * or BTRFS_ROOT_BACKREF_KEY.
+ *
+ * The dirid, sequence, name and name_len refer to the directory entry
+ * that is referencing the root.
+ *
+ * For a forward ref, the root_id is the id of the tree referencing
+ * the root and ref_id is the id of the subvol  or snapshot.
+ *
+ * For a back ref the root_id is the id of the subvol or snapshot and
+ * ref_id is the id of the tree referencing it.
+ */
+int btrfs_add_root_ref(struct btrfs_trans_handle *trans,
+                       struct btrfs_root *tree_root,
+                       u64 root_id, u8 type, u64 ref_id,
+                       u64 dirid, u64 sequence,
+                       const char *name, int name_len)
+{
+        struct btrfs_key key;
+        int ret;
+        struct btrfs_path *path;
+        struct btrfs_root_ref *ref;
+        struct extent_buffer *leaf;
+        unsigned long ptr;
+
+
+        path = btrfs_alloc_path();
+
+        key.objectid = root_id;
+        key.type = type;
+        key.offset = ref_id;
+
+        ret = btrfs_insert_empty_item(trans, tree_root, path, &key,
+                                      sizeof(*ref) + name_len);
+        BUG_ON(ret);
+
+        leaf = path->nodes[0];
+        ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_root_ref);
+        btrfs_set_root_ref_dirid(leaf, ref, dirid);
+        btrfs_set_root_ref_sequence(leaf, ref, sequence);
+        btrfs_set_root_ref_name_len(leaf, ref, name_len);
+        ptr = (unsigned long)(ref + 1);
+        write_extent_buffer(leaf, name, ptr, name_len);
+        btrfs_mark_buffer_dirty(leaf);
+
+        btrfs_free_path(path);
+        return ret;
+}
diff --git a/fs/btrfs/transaction.c b/fs/btrfs/transaction.c
index 93f23a456a36..e9c8ebeedd7e 100644
--- a/fs/btrfs/transaction.c
+++ b/fs/btrfs/transaction.c
@@ -831,28 +831,43 @@ static noinline int finish_pending_snapshot(struct btrfs_fs_info *fs_info,
         struct btrfs_trans_handle *trans;
         struct inode *parent_inode;
         struct inode *inode;
+        struct btrfs_root *parent_root;
 
         parent_inode = pending->dentry->d_parent->d_inode;
-        trans = btrfs_start_transaction(BTRFS_I(parent_inode)->root, 1);
+        parent_root = BTRFS_I(parent_inode)->root;
+        trans = btrfs_start_transaction(parent_root, 1);
 
         /*
          * insert the directory item
          */
         namelen = strlen(pending->name);
         ret = btrfs_set_inode_index(parent_inode, &index);
-        ret = btrfs_insert_dir_item(trans,
-                            BTRFS_I(parent_inode)->root,
+        ret = btrfs_insert_dir_item(trans, parent_root,
                             pending->name, namelen,
                             parent_inode->i_ino,
                             &pending->root_key, BTRFS_FT_DIR, index);
 
         if (ret)
                 goto fail;
-#if 0
-        ret = btrfs_insert_inode_ref(trans, root->fs_info->tree_root,
-                             pending->name, strlen(pending->name), objectid,
-                             root->fs_info->sb->s_root->d_inode->i_ino, 0);
-#endif
+
+        /* add the backref first */
+        ret = btrfs_add_root_ref(trans, parent_root->fs_info->tree_root,
+                                 pending->root_key.objectid,
+                                 BTRFS_ROOT_BACKREF_KEY,
+                                 parent_root->root_key.objectid,
+                                 parent_inode->i_ino, index, pending->name,
+                                 namelen);
+
+        BUG_ON(ret);
+
+        /* now add the forward ref */
+        ret = btrfs_add_root_ref(trans, parent_root->fs_info->tree_root,
+                                 parent_root->root_key.objectid,
+                                 BTRFS_ROOT_REF_KEY,
+                                 pending->root_key.objectid,
+                                 parent_inode->i_ino, index, pending->name,
+                                 namelen);
+
         inode = btrfs_lookup_dentry(parent_inode, pending->dentry);
         d_instantiate(pending->dentry, inode);
 fail: