Btrfs: introduce a tree for UUID to subvol ID mapping

PATCH Superseded Stefan Behrens 1 participant 9 messages May 16, 2013 Btrfs file system

Share & tools

Stefan Behrens

author

2013-05-16 14:45 UTC #0 lore raw

v3 cover Btrfs: introduce a tree for UUID to subvol ID mapping

Mapping UUIDs to subvolume IDs is an operation with a high effort today. Today, the algorithm even has quadratic effort (based on the number of existing subvolumes), which means, that it takes minutes to send/receive a single subvolume if 10,000 subvolumes exist. But even linear effort would be too much since it is a waste. And these data structures to allow mapping UUIDs to subvolume IDs are created every time a btrfs send/receive instance is started.

So the issue to address is that Btrfs send / receive does not work as it is today when a high number of subvolumes exist.

The table below shows the time it takes on my testbox to send _one_ empty subvolume depending on the number of subvolume that exist in the filesystem.

# of subvols  | without    | with
in filesystem | UUID tree  | UUID tree
--------------+------------+----------
            2 |  0m00.004s | 0m00.003s
         1000 |  0m07.010s | 0m00.004s
         2000 |  0m28.210s | 0m00.004s
         3000 |  1m04.872s | 0m00.004s
         4000 |  1m56.059s | 0m00.004s
         5000 |  3m00.489s | 0m00.004s
         6000 |  4m27.376s | 0m00.004s
         7000 |  6m08.938s | 0m00.004s
         8000 |  7m54.020s | 0m00.004s
         9000 | 10m05.108s | 0m00.004s
        10000 | 12m47.406s | 0m00.004s
        11000 | 15m05.800s | 0m00.004s
        12000 | 18m00.170s | 0m00.004s
        13000 | 21m39.438s | 0m00.004s
        14000 | 24m54.681s | 0m00.004s
        15000 | 28m09.096s | 0m00.004s
        16000 | 33m08.856s | 0m00.004s
        17000 | 37m10.562s | 0m00.004s
        18000 | 41m44.727s | 0m00.004s
        19000 | 46m14.335s | 0m00.004s
        20000 | 51m55.100s | 0m00.004s
        21000 | 56m54.346s | 0m00.004s
        22000 | 62m53.466s | 0m00.004s
        23000 | 66m57.328s | 0m00.004s
        24000 | 73m59.687s | 0m00.004s
        25000 | 81m24.476s | 0m00.004s
        26000 | 87m11.478s | 0m00.004s
        27000 | 92m59.225s | 0m00.004s

Or as a chart:
http://btrfs.giantdisaster.de/Btrfs-send-recv-perf.pdf

It is much more efficient to maintain a searchable persistent data structure in the filesystem, one that is updated whenever a subvolume/snapshot is created and deleted, and when the received subvolume UUID is set by the btrfs-receive tool.

Therefore kernel code is added that is able to maintain data structures in the filesystem that allow to quickly search for a given UUID and to retrieve the subvol ID.

Now follows the lengthy justification, why a new tree was added instead of using the existing root tree:

The first approach was to not create another tree that holds UUID items. Instead, the items should just go into the top root tree. Unfortunately this confused the algorithm to assign the objectid of subvolumes and snapshots. The reason is that btrfs_find_free_objectid() calls btrfs_find_highest_objectid() for the first created subvol or snapshot after mounting a filesystem, and this function simply searches for the largest used objectid in the root tree keys to pick the next objectid to assign. Of course, the UUID keys have always been the ones with the highest offset value, and the next assigned subvol ID was wastefully huge.

To use any other existing tree did not look proper. To apply a workaround such as setting the objectid to zero in the UUID item key and to implement collision handling would either add limitations (in case of a btrfs_extend_item() approach to handle the collisions) or a lot of complexity and source code (in case a key would be looked up that is free of collisions). Adding new code that introduces limitations is not good, and adding code that is complex and lengthy for no good reason is also not good. That's the justification why a completely new tree was introduced.

v1 -> v2:
- All review comments from David Sterba, Josef Bacik and Jan Schmidt are addressed.
The hugest change was to add a mechanism that handles the case that the filesystem is mounted with an older kernel. Now that case is detected when the filesystem is mounted with a newer kernel again, and the UUID tree is updated in the background.

v2 -> v3:
- All review comments from Liu Bo are addressed:
- shrinked the size of the uuid_item.
- fixed the issue that the uuid-tree was not using the transaction block reserve.

Stefan Behrens (8):
Btrfs: introduce a tree for items that map UUIDs to something
Btrfs: support printing UUID tree elements
Btrfs: create UUID tree if required
Btrfs: maintain subvolume items in the UUID tree
Btrfs: fill UUID tree initially
Btrfs: introduce uuid-tree-gen field
Btrfs: check UUID tree during mount if required
Btrfs: add mount option to force UUID tree checking

 fs/btrfs/Makefile      |   3 +-
 fs/btrfs/ctree.h       |  65 ++++-
 fs/btrfs/disk-io.c     |  62 ++++-
 fs/btrfs/extent-tree.c |   3 +
 fs/btrfs/ioctl.c       |  74 +++++-
 fs/btrfs/print-tree.c  |  81 +++++++
 fs/btrfs/super.c       |   8 +-
 fs/btrfs/transaction.c |  21 +-
 fs/btrfs/uuid-tree.c   | 636 +++++++++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/volumes.c     | 257 ++++++++++++++++++++
 fs/btrfs/volumes.h     |   2 +
 11 files changed, 1197 insertions(+), 15 deletions(-)
 create mode 100644 fs/btrfs/uuid-tree.c

Signature · 1 line

1.8.2.3

Stefan Behrens

author

2013-05-16 14:45 UTC #1 lore raw

PATCH v3 1/8 Btrfs: introduce a tree for items that map UUIDs to something

Therefore kernel code is added with this commit that is able to maintain data structures in the filesystem that allow to quickly search for a given UUID and to retrieve data that is assigned to this UUID, like which subvolume ID is related to this UUID.

This commit adds a new tree to hold UUID-to-data mapping items. The key of the items is the full UUID plus the key type BTRFS_UUID_KEY. Multiple data blocks can be stored for a given UUID, a type/length/ value scheme is used.

Now follows the lengthy justification, why a new tree was added instead of using the existing root tree:

Signed-off-by Stefan Behrens <[email protected]>

---
 fs/btrfs/Makefile    |   3 +-
 fs/btrfs/ctree.h     |  50 ++++++
 fs/btrfs/uuid-tree.c | 480 +++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 532 insertions(+), 1 deletion(-)

fs/btrfs/Makefile +2 -1

index 3932224..a550dfc 100644
@@ -8,7 +8,8 @@ btrfs-y += super.o ctree.o extent-tree.o print-tree.o root-tree.o dir-item.o \
 	   extent_io.o volumes.o async-thread.o ioctl.o locking.o orphan.o \
 	   export.o tree-log.o free-space-cache.o zlib.o lzo.o \
 	   compression.o delayed-ref.o relocation.o delayed-inode.o scrub.o \
-	   reada.o backref.o ulist.o qgroup.o send.o dev-replace.o raid56.o
+	   reada.o backref.o ulist.o qgroup.o send.o dev-replace.o raid56.o \
+	   uuid-tree.o
 
 btrfs-$(CONFIG_BTRFS_FS_POSIX_ACL) += acl.o
 btrfs-$(CONFIG_BTRFS_FS_CHECK_INTEGRITY) += check-integrity.o

fs/btrfs/ctree.h +50 -0

80 lines not on this page · raw message

fs/btrfs/uuid-tree.c new file +480 -0

480 lines not on this page · raw message

Signature · 1 line

1.8.2.3

Stefan Behrens

author

2013-05-16 14:45 UTC #2 lore raw

PATCH v3 2/8 Btrfs: support printing UUID tree elements

In reply to Stefan Behrens

This commit adds support to print UUID tree elements to print-tree.c.

Signed-off-by Stefan Behrens <[email protected]>

---
 fs/btrfs/print-tree.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 81 insertions(+)

fs/btrfs/print-tree.c +81 -0

index dc0024f..c27f08b 100644
@@ -155,6 +155,81 @@ static void print_extent_ref_v0(struct extent_buffer *eb, int slot)
 }
 #endif
 
+static void print_uuid_item(struct extent_buffer *l,
+			    struct btrfs_uuid_item *ptr,
+			    u32 item_size)
+{
+	do {
+		u16 sub_item_type;
+		u64 sub_item_len;
+		u64 subvol_id;
+		unsigned long offset;
+
+		if (item_size < sizeof(*ptr)) {
+			printk(KERN_INFO
+			       "btrfs: uuid item too short (%lu < %d)!\n",
+			       (unsigned long)item_size, (int)sizeof(*ptr));
+			return;
+		}
+		sub_item_type = btrfs_uuid_type(l, ptr);
+		sub_item_len = btrfs_uuid_len(l, ptr);
+		ptr++;
+		item_size -= sizeof(*ptr);
+
+		if (sub_item_len * sizeof(u64) > item_size) {
+			printk(KERN_INFO
+			       "btrfs: uuid item too short (%llu > %lu)!\n",
+			       (unsigned long long)(sub_item_len * sizeof(u64)),
+			       (unsigned long)item_size);
+			return;
+		}
+
+		offset = (unsigned long)ptr;
+		ptr = (struct btrfs_uuid_item *)
+			(((char *)ptr) + sub_item_len * sizeof(u64));
+		item_size -= sub_item_len * sizeof(u64);
+		switch (sub_item_type) {
+		case BTRFS_UUID_ITEM_TYPE_SUBVOL:
+			while (sub_item_len) {
+				read_extent_buffer(l, &subvol_id, offset,
+						   sizeof(u64));
+				printk(KERN_INFO "\t\tsubvol_id %llu\n",
+				       (unsigned long long)
+					le64_to_cpu(subvol_id));
+				sub_item_len--;
+				offset += sizeof(u64);
+			}
+			break;
+		case BTRFS_UUID_ITEM_TYPE_RECEIVED_SUBVOL:
+			while (sub_item_len) {
+				read_extent_buffer(l, &subvol_id, offset,
+						   sizeof(u64));
+				printk(KERN_INFO
+				       "\t\treceived_subvol_id %llu\n",
+				       (unsigned long long)
+					le64_to_cpu(subvol_id));
+				sub_item_len--;
+				offset += sizeof(u64);
+			}
+			break;
+		default:
+			printk(KERN_INFO "\t\tunknown type=%llu, len=8*%llu\n",
+			       (unsigned long long)sub_item_type,
+			       (unsigned long long)sub_item_len);
+			while (sub_item_len) {
+				read_extent_buffer(l, &subvol_id, offset,
+						   sizeof(u64));
+				printk(KERN_INFO "\t\tid %llu\n",
+				       (unsigned long long)
+					le64_to_cpu(subvol_id));
+				sub_item_len--;
+				offset += sizeof(u64);
+			}
+			break;
+		}
+	} while (item_size);
+}
+
 void btrfs_print_leaf(struct btrfs_root *root, struct extent_buffer *l)
 {
 	int i;

@@ -168,6 +243,7 @@ void btrfs_print_leaf(struct btrfs_root *root, struct extent_buffer *l)
 	struct btrfs_extent_data_ref *dref;
 	struct btrfs_shared_data_ref *sref;
 	struct btrfs_dev_extent *dev_extent;
+	struct btrfs_uuid_item *uuid_item;
 	struct btrfs_key key;
 	struct btrfs_key found_key;

@@ -301,6 +377,11 @@ void btrfs_print_leaf(struct btrfs_root *root, struct extent_buffer *l)
 		case BTRFS_DEV_REPLACE_KEY:
 			printk(KERN_INFO "\t\tdev replace\n");
 			break;
+		case BTRFS_UUID_KEY:
+			uuid_item = btrfs_item_ptr(l, i,
+						   struct btrfs_uuid_item);
+			print_uuid_item(l, uuid_item, btrfs_item_size_nr(l, i));
+			break;
 		};
 	}
 }

Signature · 1 line

1.8.2.3

Stefan Behrens

author

2013-05-16 14:45 UTC #3 lore raw

PATCH v3 3/8 Btrfs: create UUID tree if required

In reply to Stefan Behrens

This tree is not created by mkfs.btrfs. Therefore when a filesystem is mounted writable and the UUID tree does not exist, this tree is created if required. The tree is also added to the fs_info structure and initialized, but this commit does not yet read or write UUID tree elements.

Signed-off-by Stefan Behrens <[email protected]>

---
 fs/btrfs/ctree.h       |  1 +
 fs/btrfs/disk-io.c     | 40 +++++++++++++++++++++++++++++++++++++++-
 fs/btrfs/extent-tree.c |  3 +++
 fs/btrfs/volumes.c     | 26 ++++++++++++++++++++++++++
 fs/btrfs/volumes.h     |  1 +
 5 files changed, 70 insertions(+), 1 deletion(-)

fs/btrfs/ctree.h +1 -0

index 500fc0f..3b25087 100644
@@ -1305,6 +1305,7 @@ struct btrfs_fs_info {
 	struct btrfs_root *fs_root;
 	struct btrfs_root *csum_root;
 	struct btrfs_root *quota_root;
+	struct btrfs_root *uuid_root;
 
 	/* the log root tree is a directory of all the other log roots */
 	struct btrfs_root *log_root_tree;

fs/btrfs/disk-io.c +39 -1

index 4904d7f..3c2bf74 100644
@@ -1499,6 +1499,9 @@ struct btrfs_root *btrfs_read_fs_root_no_name(struct btrfs_fs_info *fs_info,
 	if (location->objectid == BTRFS_QUOTA_TREE_OBJECTID)
 		return fs_info->quota_root ? fs_info->quota_root :
 					     ERR_PTR(-ENOENT);
+	if (location->objectid == BTRFS_UUID_TREE_OBJECTID)
+		return fs_info->uuid_root ? fs_info->uuid_root :
+					    ERR_PTR(-ENOENT);
 again:
 	spin_lock(&fs_info->fs_roots_radix_lock);
 	root = radix_tree_lookup(&fs_info->fs_roots_radix,

@@ -1955,6 +1958,10 @@ static void free_root_pointers(struct btrfs_fs_info *info, int chunk_root)
 		free_extent_buffer(info->quota_root->node);
 		free_extent_buffer(info->quota_root->commit_root);
 	}
+	if (info->uuid_root) {
+		free_extent_buffer(info->uuid_root->node);
+		free_extent_buffer(info->uuid_root->commit_root);
+	}
 
 	info->tree_root->node = NULL;
 	info->tree_root->commit_root = NULL;

@@ -1968,6 +1975,10 @@ static void free_root_pointers(struct btrfs_fs_info *info, int chunk_root)
 		info->quota_root->node = NULL;
 		info->quota_root->commit_root = NULL;
 	}
+	if (info->uuid_root) {
+		info->uuid_root->node = NULL;
+		info->uuid_root->commit_root = NULL;
+	}
 
 	if (chunk_root) {
 		free_extent_buffer(info->chunk_root->node);

@@ -2029,11 +2040,13 @@ int open_ctree(struct super_block *sb,
 	struct btrfs_root *chunk_root;
 	struct btrfs_root *dev_root;
 	struct btrfs_root *quota_root;
+	struct btrfs_root *uuid_root;
 	struct btrfs_root *log_tree_root;
 	int ret;
 	int err = -EINVAL;
 	int num_backups_tried = 0;
 	int backup_index = 0;
+	bool create_uuid_tree = false;
 
 	tree_root = fs_info->tree_root = btrfs_alloc_root(fs_info);
 	extent_root = fs_info->extent_root = btrfs_alloc_root(fs_info);

@@ -2041,9 +2054,10 @@ int open_ctree(struct super_block *sb,
 	chunk_root = fs_info->chunk_root = btrfs_alloc_root(fs_info);
 	dev_root = fs_info->dev_root = btrfs_alloc_root(fs_info);
 	quota_root = fs_info->quota_root = btrfs_alloc_root(fs_info);
+	uuid_root = fs_info->uuid_root = btrfs_alloc_root(fs_info);
 
 	if (!tree_root || !extent_root || !csum_root ||
-	    !chunk_root || !dev_root || !quota_root) {
+	    !chunk_root || !dev_root || !quota_root || !uuid_root) {
 		err = -ENOMEM;
 		goto fail;
 	}

@@ -2604,6 +2618,19 @@ retry_root_backup:
 		fs_info->pending_quota_state = 1;
 	}
 
+	ret = find_and_setup_root(tree_root, fs_info,
+				  BTRFS_UUID_TREE_OBJECTID, uuid_root);
+	if (ret) {
+		if (ret != -ENOENT)
+			goto recovery_tree_root;
+
+		kfree(uuid_root);
+		uuid_root = fs_info->uuid_root = NULL;
+		create_uuid_tree = true;
+	} else {
+		uuid_root->track_dirty = 1;
+	}
+
 	fs_info->generation = generation;
 	fs_info->last_trans_committed = generation;

@@ -2788,6 +2815,17 @@ retry_root_backup:
 		return ret;
 	}
 
+	if (create_uuid_tree) {
+		pr_info("btrfs: creating UUID tree\n");
+		ret = btrfs_create_uuid_tree(fs_info);
+		if (ret) {
+			pr_warn("btrfs: failed to create the UUID tree %d\n",
+				ret);
+			close_ctree(tree_root);
+			return ret;
+		}
+	}
+
 	return 0;
 
 fail_qgroup:

fs/btrfs/extent-tree.c +3 -0

index 6dfb239..af1cdfc 100644
@@ -4259,6 +4259,9 @@ static struct btrfs_block_rsv *get_block_rsv(
 	if (root == root->fs_info->csum_root && trans->adding_csums)
 		block_rsv = trans->block_rsv;
 
+	if (root == root->fs_info->uuid_root)
+		block_rsv = trans->block_rsv;
+
 	if (!block_rsv)
 		block_rsv = root->block_rsv;

fs/btrfs/volumes.c +26 -0

index a191bac..1006820 100644
@@ -3427,6 +3427,32 @@ int btrfs_cancel_balance(struct btrfs_fs_info *fs_info)
 	return 0;
 }
 
+int btrfs_create_uuid_tree(struct btrfs_fs_info *fs_info)
+{
+	struct btrfs_trans_handle *trans;
+	struct btrfs_root *tree_root = fs_info->tree_root;
+	struct btrfs_root *uuid_root;
+
+	/*
+	 * 1 - root node
+	 * 1 - root item
+	 */
+	trans = btrfs_start_transaction(tree_root, 2);
+	if (IS_ERR(trans))
+		return PTR_ERR(trans);
+
+	uuid_root = btrfs_create_tree(trans, fs_info,
+				      BTRFS_UUID_TREE_OBJECTID);
+	if (IS_ERR(uuid_root)) {
+		btrfs_abort_transaction(trans, tree_root,
+					PTR_ERR(uuid_root));
+		return PTR_ERR(uuid_root);
+	}
+
+	fs_info->uuid_root = uuid_root;
+
+	return btrfs_commit_transaction(trans, tree_root);
+}
 /*
  * shrinking a device means finding all of the device extents past
  * the new size, and then following the back refs to the chunks.

fs/btrfs/volumes.h +1 -0

index 845ccbb..3479532 100644
@@ -295,6 +295,7 @@ int btrfs_resume_balance_async(struct btrfs_fs_info *fs_info);
 int btrfs_recover_balance(struct btrfs_fs_info *fs_info);
 int btrfs_pause_balance(struct btrfs_fs_info *fs_info);
 int btrfs_cancel_balance(struct btrfs_fs_info *fs_info);
+int btrfs_create_uuid_tree(struct btrfs_fs_info *fs_info);
 int btrfs_chunk_readonly(struct btrfs_root *root, u64 chunk_offset);
 int find_free_dev_extent(struct btrfs_device *device, u64 num_bytes,
 			 u64 *start, u64 *max_avail);

Signature · 1 line

1.8.2.3

Stefan Behrens

author

2013-05-16 14:45 UTC #4 lore raw

PATCH v3 4/8 Btrfs: maintain subvolume items in the UUID tree

In reply to Stefan Behrens

When a new subvolume or snapshot is created, a new UUID item is added to the UUID tree. Such items are removed when the subvolume is deleted. The ioctl to set the received subvolume UUID is also touched and will now also add this received UUID into the UUID tree together with the ID of the subvolume. The latter is also done when read-only snapshots are created which inherit all the send/receive information from the parent subvolume.

User mode programs use the BTRFS_IOC_TREE_SEARCH ioctl to search and read in the UUID tree.

Signed-off-by Stefan Behrens <[email protected]>

---
 fs/btrfs/ctree.h       |  1 +
 fs/btrfs/ioctl.c       | 74 +++++++++++++++++++++++++++++++++++++++++++-------
 fs/btrfs/transaction.c | 19 ++++++++++++-
 3 files changed, 83 insertions(+), 11 deletions(-)

fs/btrfs/ctree.h +1 -0

index 3b25087..d128940 100644
@@ -3634,6 +3634,7 @@ extern const struct dentry_operations btrfs_dentry_operations;
 long btrfs_ioctl(struct file *file, unsigned int cmd, unsigned long arg);
 void btrfs_update_iflags(struct inode *inode);
 void btrfs_inherit_iflags(struct inode *inode, struct inode *dir);
+int btrfs_is_empty_uuid(u8 *uuid);
 int btrfs_defrag_file(struct inode *inode, struct file *file,
 		      struct btrfs_ioctl_defrag_range_args *range,
 		      u64 newer_than, unsigned long max_pages);

fs/btrfs/ioctl.c +64 ~~-10~~

146 lines not on this page · raw message

fs/btrfs/transaction.c +18 -1

index 0544587..a3d92b3 100644
@@ -1263,8 +1263,25 @@ static noinline int create_pending_snapshot(struct btrfs_trans_handle *trans,
 					 dentry->d_name.len * 2);
 	parent_inode->i_mtime = parent_inode->i_ctime = CURRENT_TIME;
 	ret = btrfs_update_inode_fallback(trans, parent_root, parent_inode);
-	if (ret)
+	if (ret) {
+		btrfs_abort_transaction(trans, root, ret);
+		goto fail;
+	}
+	ret = btrfs_insert_uuid_subvol_item(trans, fs_info->uuid_root,
+					    new_uuid.b, objectid);
+	if (ret) {
 		btrfs_abort_transaction(trans, root, ret);
+		goto fail;
+	}
+	if (!btrfs_is_empty_uuid(new_root_item->received_uuid)) {
+		ret = btrfs_insert_uuid_received_subvol_item(
+			trans, fs_info->uuid_root, new_root_item->received_uuid,
+			objectid);
+		if (ret && ret != -EEXIST) {
+			btrfs_abort_transaction(trans, root, ret);
+			goto fail;
+		}
+	}
 fail:
 	pending->error = ret;
 dir_item_existed:

Signature · 1 line

1.8.2.3

Stefan Behrens

author

2013-05-16 14:45 UTC #5 lore raw

PATCH v3 5/8 Btrfs: fill UUID tree initially

In reply to Stefan Behrens

When the UUID tree is initially created, a task is spawned that walks through the root tree. For each found subvolume root_item, the uuid and received_uuid entries in the UUID tree are added. This is such a quick operation so that in case somebody wants to unmount the filesystem while the task is still running, the unmount is delayed until the UUID tree building task is finished.

Signed-off-by Stefan Behrens <[email protected]>

---
 fs/btrfs/ctree.h   |   3 ++
 fs/btrfs/disk-io.c |   5 ++
 fs/btrfs/volumes.c | 150 ++++++++++++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 157 insertions(+), 1 deletion(-)

fs/btrfs/ctree.h +3 -0

index d128940..ddcef0f 100644
@@ -23,6 +23,7 @@
 #include <linux/highmem.h>
 #include <linux/fs.h>
 #include <linux/rwsem.h>
+#include <linux/semaphore.h>
 #include <linux/completion.h>
 #include <linux/backing-dev.h>
 #include <linux/wait.h>

@@ -1649,6 +1650,8 @@ struct btrfs_fs_info {
 	struct btrfs_dev_replace dev_replace;
 
 	atomic_t mutually_exclusive_operation_running;
+
+	struct semaphore uuid_scan_sem;
 };
 
 /*

fs/btrfs/disk-io.c +5 -0

index 3c2bf74..e99514e 100644
@@ -31,6 +31,7 @@
 #include <linux/migrate.h>
 #include <linux/ratelimit.h>
 #include <linux/uuid.h>
+#include <linux/semaphore.h>
 #include <asm/unaligned.h>
 #include "compat.h"
 #include "ctree.h"

@@ -2230,6 +2231,7 @@ int open_ctree(struct super_block *sb,
 	init_rwsem(&fs_info->extent_commit_sem);
 	init_rwsem(&fs_info->cleanup_work_sem);
 	init_rwsem(&fs_info->subvol_sem);
+	sema_init(&fs_info->uuid_scan_sem, 1);
 	fs_info->dev_replace.lock_owner = 0;
 	atomic_set(&fs_info->dev_replace.nesting_level, 0);
 	mutex_init(&fs_info->dev_replace.lock_finishing_cancel_unmount);

@@ -3447,6 +3449,9 @@ int close_ctree(struct btrfs_root *root)
 	fs_info->closing = 1;
 	smp_mb();
 
+	/* wait for the uuid_scan task to finish */
+	down(&fs_info->uuid_scan_sem);
+
 	/* pause restriper - we want to resume on mount */
 	btrfs_pause_balance(fs_info);

fs/btrfs/volumes.c +149 -1

174 lines not on this page · raw message

Signature · 1 line

1.8.2.3

Stefan Behrens

author

2013-05-16 14:45 UTC #6 lore raw

PATCH v3 6/8 Btrfs: introduce uuid-tree-gen field

In reply to Stefan Behrens

In order to be able to detect the case that a filesystem is mounted with an old kernel, add a uuid-tree-gen field like the free space cache is doing it. It is part of the super block and written with each commit. Old kernels do not know this field and don't update it.

Signed-off-by Stefan Behrens <[email protected]>

---
 fs/btrfs/ctree.h       | 5 ++++-
 fs/btrfs/transaction.c | 1 +
 2 files changed, 5 insertions(+), 1 deletion(-)

fs/btrfs/ctree.h +4 -1

index ddcef0f..b3662d7 100644
@@ -482,9 +482,10 @@ struct btrfs_super_block {
 	char label[BTRFS_LABEL_SIZE];
 
 	__le64 cache_generation;
+	__le64 uuid_tree_generation;
 
 	/* future expansion */
-	__le64 reserved[31];
+	__le64 reserved[30];
 	u8 sys_chunk_array[BTRFS_SYSTEM_CHUNK_ARRAY_SIZE];
 	struct btrfs_root_backup super_roots[BTRFS_NUM_BACKUP_ROOTS];
 } __attribute__ ((__packed__));

@@ -2827,6 +2828,8 @@ BTRFS_SETGET_STACK_FUNCS(super_csum_type, struct btrfs_super_block,
 			 csum_type, 16);
 BTRFS_SETGET_STACK_FUNCS(super_cache_generation, struct btrfs_super_block,
 			 cache_generation, 64);
+BTRFS_SETGET_STACK_FUNCS(super_uuid_tree_generation, struct btrfs_super_block,
+			 uuid_tree_generation, 64);
 
 static inline int btrfs_super_csum_size(struct btrfs_super_block *s)
 {

fs/btrfs/transaction.c +1 -0

index a3d92b3..eed52bb 100644
@@ -1331,6 +1331,7 @@ static void update_super_roots(struct btrfs_root *root)
 	super->root_level = root_item->level;
 	if (btrfs_test_opt(root, SPACE_CACHE))
 		super->cache_generation = root_item->generation;
+	super->uuid_tree_generation = root_item->generation;
 }
 
 int btrfs_transaction_in_commit(struct btrfs_fs_info *info)

Signature · 1 line

1.8.2.3

Stefan Behrens

author

2013-05-16 14:45 UTC #7 lore raw

PATCH v3 7/8 Btrfs: check UUID tree during mount if required

In reply to Stefan Behrens

If the filesystem was mounted with an old kernel that was not aware of the UUID tree, this is detected by looking at the uuid_tree_generation field of the superblock (similar to how the free space cache is doing it). If a mismatch is detected at mount time, a thread is started that does two things:
1. Iterate through the UUID tree, check each entry, delete those entries that are not valid anymore (i.e., the subvol does not exist anymore or the value changed).
2. Iterate through the root tree, for each found subvolume, add the UUID tree entries for the subvolume (if they are not already there).

This mechanism is also used to handle and repair errors that happened during the initial creation and filling of the tree. The update of the uuid_tree_generation field (which indicates that the state of the UUID tree is up to date) is blocked until all create and repair operations are successfully completed.

Signed-off-by Stefan Behrens <[email protected]>

---
 fs/btrfs/ctree.h       |   4 ++
 fs/btrfs/disk-io.c     |  18 +++++-
 fs/btrfs/transaction.c |   3 +-
 fs/btrfs/uuid-tree.c   | 156 +++++++++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/volumes.c     |  83 ++++++++++++++++++++++++++
 fs/btrfs/volumes.h     |   1 +
 6 files changed, 263 insertions(+), 2 deletions(-)

fs/btrfs/ctree.h +4 -0

index b3662d7..7efe25c 100644
@@ -1653,6 +1653,7 @@ struct btrfs_fs_info {
 	atomic_t mutually_exclusive_operation_running;
 
 	struct semaphore uuid_scan_sem;
+	unsigned int update_uuid_tree_gen:1;
 };
 
 /*

@@ -3412,6 +3413,9 @@ void btrfs_update_root_times(struct btrfs_trans_handle *trans,
 			     struct btrfs_root *root);
 
 /* uuid-tree.c */
+int btrfs_uuid_tree_iterate(struct btrfs_fs_info *fs_info,
+			    int (*check_func)(struct btrfs_fs_info *, u8 *, u16,
+					      u64));
 int btrfs_lookup_uuid_subvol_item(struct btrfs_root *uuid_root, u8 *uuid,
 				  u64 *subvol_id);
 int btrfs_insert_uuid_subvol_item(struct btrfs_trans_handle *trans,

fs/btrfs/disk-io.c +17 -1

index e99514e..30513c1 100644
@@ -2047,7 +2047,8 @@ int open_ctree(struct super_block *sb,
 	int err = -EINVAL;
 	int num_backups_tried = 0;
 	int backup_index = 0;
-	bool create_uuid_tree = false;
+	bool create_uuid_tree;
+	bool check_uuid_tree;
 
 	tree_root = fs_info->tree_root = btrfs_alloc_root(fs_info);
 	extent_root = fs_info->extent_root = btrfs_alloc_root(fs_info);

@@ -2629,8 +2630,12 @@ retry_root_backup:
 		kfree(uuid_root);
 		uuid_root = fs_info->uuid_root = NULL;
 		create_uuid_tree = true;
+		check_uuid_tree = false;
 	} else {
 		uuid_root->track_dirty = 1;
+		create_uuid_tree = false;
+		check_uuid_tree =
+		    generation != btrfs_super_uuid_tree_generation(disk_super);
 	}
 
 	fs_info->generation = generation;

@@ -2826,6 +2831,17 @@ retry_root_backup:
 			close_ctree(tree_root);
 			return ret;
 		}
+	} else if (check_uuid_tree) {
+		pr_info("btrfs: checking UUID tree\n");
+		ret = btrfs_check_uuid_tree(fs_info);
+		if (ret) {
+			pr_warn("btrfs: failed to check the UUID tree %d\n",
+				ret);
+			close_ctree(tree_root);
+			return ret;
+		}
+	} else {
+		fs_info->update_uuid_tree_gen = 1;
 	}
 
 	return 0;

fs/btrfs/transaction.c +2 -1

index eed52bb..0c3f0d3 100644
@@ -1331,7 +1331,8 @@ static void update_super_roots(struct btrfs_root *root)
 	super->root_level = root_item->level;
 	if (btrfs_test_opt(root, SPACE_CACHE))
 		super->cache_generation = root_item->generation;
-	super->uuid_tree_generation = root_item->generation;
+	if (root->fs_info->update_uuid_tree_gen)
+		super->uuid_tree_generation = root_item->generation;
 }
 
 int btrfs_transaction_in_commit(struct btrfs_fs_info *info)

fs/btrfs/uuid-tree.c +156 -0

162 lines not on this page · raw message

fs/btrfs/volumes.c +83 -0

105 lines not on this page · raw message

fs/btrfs/volumes.h +1 -0

index 3479532..b0ce9a1 100644
@@ -296,6 +296,7 @@ int btrfs_recover_balance(struct btrfs_fs_info *fs_info);
 int btrfs_pause_balance(struct btrfs_fs_info *fs_info);
 int btrfs_cancel_balance(struct btrfs_fs_info *fs_info);
 int btrfs_create_uuid_tree(struct btrfs_fs_info *fs_info);
+int btrfs_check_uuid_tree(struct btrfs_fs_info *fs_info);
 int btrfs_chunk_readonly(struct btrfs_root *root, u64 chunk_offset);
 int find_free_dev_extent(struct btrfs_device *device, u64 num_bytes,
 			 u64 *start, u64 *max_avail);

Signature · 1 line

1.8.2.3

Stefan Behrens

author

2013-05-16 14:45 UTC #8 lore raw

PATCH v3 8/8 Btrfs: add mount option to force UUID tree checking

In reply to Stefan Behrens

This should never be needed, but since all functions are there to check and rebuild the UUID tree, a mount option is added that allows to force this check and rebuild procedure.

Signed-off-by Stefan Behrens <[email protected]>

---
 fs/btrfs/ctree.h   | 1 +
 fs/btrfs/disk-io.c | 3 ++-
 fs/btrfs/super.c   | 8 +++++++-
 3 files changed, 10 insertions(+), 2 deletions(-)

fs/btrfs/ctree.h +1 -0

index 7efe25c..026646a 100644
@@ -1966,6 +1966,7 @@ struct btrfs_ioctl_defrag_range_args {
 #define BTRFS_MOUNT_CHECK_INTEGRITY	(1 << 20)
 #define BTRFS_MOUNT_CHECK_INTEGRITY_INCLUDING_EXTENT_DATA (1 << 21)
 #define BTRFS_MOUNT_PANIC_ON_FATAL_ERROR	(1 << 22)
+#define BTRFS_MOUNT_RESCAN_UUID_TREE	(1 << 23)
 
 #define btrfs_clear_opt(o, opt)		((o) &= ~BTRFS_MOUNT_##opt)
 #define btrfs_set_opt(o, opt)		((o) |= BTRFS_MOUNT_##opt)

fs/btrfs/disk-io.c +2 -1

index 30513c1..2e94b1a 100644
@@ -2831,7 +2831,8 @@ retry_root_backup:
 			close_ctree(tree_root);
 			return ret;
 		}
-	} else if (check_uuid_tree) {
+	} else if (check_uuid_tree ||
+		   btrfs_test_opt(tree_root, RESCAN_UUID_TREE)) {
 		pr_info("btrfs: checking UUID tree\n");
 		ret = btrfs_check_uuid_tree(fs_info);
 		if (ret) {

fs/btrfs/super.c +7 -1

index b6af7d3..4602c6a 100644
@@ -317,7 +317,7 @@ enum {
 	Opt_enospc_debug, Opt_subvolrootid, Opt_defrag, Opt_inode_cache,
 	Opt_no_space_cache, Opt_recovery, Opt_skip_balance,
 	Opt_check_integrity, Opt_check_integrity_including_extent_data,
-	Opt_check_integrity_print_mask, Opt_fatal_errors,
+	Opt_check_integrity_print_mask, Opt_fatal_errors, Opt_rescan_uuid_tree,
 	Opt_err,
 };

@@ -357,6 +357,7 @@ static match_table_t tokens = {
 	{Opt_check_integrity, "check_int"},
 	{Opt_check_integrity_including_extent_data, "check_int_data"},
 	{Opt_check_integrity_print_mask, "check_int_print_mask=%d"},
+	{Opt_rescan_uuid_tree, "rescan_uuid_tree"},
 	{Opt_fatal_errors, "fatal_errors=%s"},
 	{Opt_err, NULL},
 };

@@ -551,6 +552,9 @@ int btrfs_parse_options(struct btrfs_root *root, char *options)
 		case Opt_space_cache:
 			btrfs_set_opt(info->mount_opt, SPACE_CACHE);
 			break;
+		case Opt_rescan_uuid_tree:
+			btrfs_set_opt(info->mount_opt, RESCAN_UUID_TREE);
+			break;
 		case Opt_no_space_cache:
 			printk(KERN_INFO "btrfs: disabling disk space caching\n");
 			btrfs_clear_opt(info->mount_opt, SPACE_CACHE);

@@ -925,6 +929,8 @@ static int btrfs_show_options(struct seq_file *seq, struct dentry *dentry)
 		seq_puts(seq, ",space_cache");
 	else
 		seq_puts(seq, ",nospace_cache");
+	if (btrfs_test_opt(root, RESCAN_UUID_TREE))
+		seq_puts(seq, ",rescan_uuid_tree");
 	if (btrfs_test_opt(root, CLEAR_CACHE))
 		seq_puts(seq, ",clear_cache");
 	if (btrfs_test_opt(root, USER_SUBVOL_RM_ALLOWED))

Signature · 1 line

1.8.2.3