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: