From 0660b5af3f7ac0fac69de975914e1f4a3a586fb3 Mon Sep 17 00:00:00 2001 From: Chris Mason Date: Mon, 17 Nov 2008 20:37:39 -0500 Subject: [PATCH] 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 --- fs/btrfs/ctree.h | 67 ++++++++++++++++++++++++++++--------- fs/btrfs/inode.c | 6 ++++ fs/btrfs/ioctl.c | 24 +++++++++---- fs/btrfs/root-tree.c | 76 +++++++++++++++++++++++++++++++++++++++++- fs/btrfs/transaction.c | 31 ++++++++++++----- 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: -- 2.30.2