Btrfs devel - Jun 2013 - [PATCH v5 0/8] 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.

v3 -> v4:
- Fixed a bug. A corrupted UUID tree entry could have caused an endless
  loop in the check+rescan thread.

v4 -> v5:
- On demand from multiple persons, the way was changed that a umount
  waits for the completion of the uuid tree rescan thread. Now a
  struct completion is used instead of a struct semaphore.

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       |  64 ++++-
 fs/btrfs/disk-io.c     |  56 +++++
 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     | 254 ++++++++++++++++++++
 fs/btrfs/volumes.h     |   2 +
 11 files changed, 1188 insertions(+), 14 deletions(-)
 create mode 100644 fs/btrfs/uuid-tree.c

-- 
1.8.3

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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.

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 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:

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.

Signed-off-by: Stefan Behrens <sbehrens@giantdisaster.de>
---
 fs/btrfs/Makefile    |   3 +-
 fs/btrfs/ctree.h     |  50 ++++++
 fs/btrfs/uuid-tree.c | 480 +++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 532 insertions(+), 1 deletion(-)

diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
index 3932224..a550dfc 100644
--- a/fs/btrfs/Makefile
+++ b/fs/btrfs/Makefile
@@ -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
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 76e4983..04447b6 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -91,6 +91,9 @@ struct btrfs_ordered_sum;
 /* holds quota configuration and tracking */
 #define BTRFS_QUOTA_TREE_OBJECTID 8ULL
 
+/* for storing items that use the BTRFS_UUID_KEY */
+#define BTRFS_UUID_TREE_OBJECTID 9ULL
+
 /* for storing balance parameters in the root tree */
 #define BTRFS_BALANCE_OBJECTID -4ULL
 
@@ -953,6 +956,18 @@ struct btrfs_dev_replace_item {
 	__le64 num_uncorrectable_read_errors;
 } __attribute__ ((__packed__));
 
+/* for items that use the BTRFS_UUID_KEY */
+#define BTRFS_UUID_ITEM_TYPE_SUBVOL	0 /* for UUIDs assigned to subvols */
+#define BTRFS_UUID_ITEM_TYPE_RECEIVED_SUBVOL	1 /* for UUIDs assigned to
+						   * received subvols */
+
+/* a sequence of such items is stored under the BTRFS_UUID_KEY */
+struct btrfs_uuid_item {
+	__le16 type;	/* refer to BTRFS_UUID_ITEM_TYPE* defines above */
+	__le32 len;	/* number of following 64bit values */
+	__le64 subid[0];	/* sequence of subids */
+} __attribute__ ((__packed__));
+
 /* different types of block groups (and chunks) */
 #define BTRFS_BLOCK_GROUP_DATA		(1ULL << 0)
 #define BTRFS_BLOCK_GROUP_SYSTEM	(1ULL << 1)
@@ -1922,6 +1937,17 @@ struct btrfs_ioctl_defrag_range_args {
 #define BTRFS_DEV_REPLACE_KEY	250
 
 /*
+ * Stores items that allow to quickly map UUIDs to something else.
+ * These items are part of the filesystem UUID tree.
+ * The key is built like this:
+ * (UUID_upper_64_bits, BTRFS_UUID_KEY, UUID_lower_64_bits).
+ */
+#if BTRFS_UUID_SIZE != 16
+#error "UUID items require BTRFS_UUID_SIZE == 16!"
+#endif
+#define BTRFS_UUID_KEY	251
+
+/*
  * string items are for debugging.  They just store a short string of
  * data in the FS
  */
@@ -2979,6 +3005,12 @@ BTRFS_SETGET_FUNCS(dev_replace_cursor_left, struct
btrfs_dev_replace_item,
 BTRFS_SETGET_FUNCS(dev_replace_cursor_right, struct btrfs_dev_replace_item,
 		   cursor_right, 64);
 
+/* btrfs_uuid_item */
+BTRFS_SETGET_FUNCS(uuid_type, struct btrfs_uuid_item, type, 16);
+BTRFS_SETGET_FUNCS(uuid_len, struct btrfs_uuid_item, len, 32);
+BTRFS_SETGET_STACK_FUNCS(stack_uuid_type, struct btrfs_uuid_item, type, 16);
+BTRFS_SETGET_STACK_FUNCS(stack_uuid_len, struct btrfs_uuid_item, len, 32);
+
 BTRFS_SETGET_STACK_FUNCS(stack_dev_replace_src_devid,
 			 struct btrfs_dev_replace_item, src_devid, 64);
 BTRFS_SETGET_STACK_FUNCS(stack_dev_replace_cont_reading_from_srcdev_mode,
@@ -3414,6 +3446,24 @@ void btrfs_check_and_init_root_item(struct
btrfs_root_item *item);
 void btrfs_update_root_times(struct btrfs_trans_handle *trans,
 			     struct btrfs_root *root);
 
+/* uuid-tree.c */
+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,
+				  struct btrfs_root *uuid_root, u8 *uuid,
+				  u64 subvol_id);
+int btrfs_del_uuid_subvol_item(struct btrfs_trans_handle *trans,
+			       struct btrfs_root *uuid_root, u8 *uuid,
+			       u64 subvol_id);
+int btrfs_lookup_uuid_received_subvol_item(struct btrfs_root *uuid_root,
+					   u8 *uuid, u64 *subvol_id);
+int btrfs_insert_uuid_received_subvol_item(struct btrfs_trans_handle *trans,
+					   struct btrfs_root *uuid_root,
+					   u8 *uuid, u64 subvol_id);
+int btrfs_del_uuid_received_subvol_item(struct btrfs_trans_handle *trans,
+					struct btrfs_root *uuid_root, u8 *uuid,
+					u64 subvol_id);
+
 /* dir-item.c */
 int btrfs_check_dir_item_collision(struct btrfs_root *root, u64 dir,
 			  const char *name, int name_len);
diff --git a/fs/btrfs/uuid-tree.c b/fs/btrfs/uuid-tree.c
new file mode 100644
index 0000000..3939a54
--- /dev/null
+++ b/fs/btrfs/uuid-tree.c
@@ -0,0 +1,480 @@
+/*
+ * Copyright (C) STRATO AG 2013.  All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public
+ * License v2 as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public
+ * License along with this program; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 021110-1307, USA.
+ */
+#include <linux/uuid.h>
+#include <asm/unaligned.h>
+#include "ctree.h"
+#include "transaction.h"
+#include "disk-io.h"
+#include "print-tree.h"
+
+
+/*
+ * One key is used to store a sequence of btrfs_uuid_item items.
+ * Each item in the sequence contains a type information and a sequence of
+ * ids (together with the information about the size of the sequence of ids).
+ * {[btrfs_uuid_item type0 {id0, id1, ..., idN}],
+ *  ...,
+ *  [btrfs_uuid_item typeZ {id0, id1, ..., idN}]}
+ *
+ * It is forbidden to put multiple items with the same type under the same key.
+ * Instead the sequence of ids is extended and used to store any additional
+ * ids for the same item type.
+ */
+
+static void btrfs_uuid_to_key(u8 *uuid, struct btrfs_key *key)
+{
+	key->type = BTRFS_UUID_KEY;
+	key->objectid = get_unaligned_le64(uuid);
+	key->offset = get_unaligned_le64(uuid + sizeof(u64));
+}
+
+static struct btrfs_uuid_item *btrfs_match_uuid_item_type(
+		struct btrfs_path *path, u16 type)
+{
+	struct extent_buffer *eb;
+	int slot;
+	struct btrfs_uuid_item *ptr;
+	u32 item_size;
+
+	eb = path->nodes[0];
+	slot = path->slots[0];
+	ptr = btrfs_item_ptr(eb, slot, struct btrfs_uuid_item);
+	item_size = btrfs_item_size_nr(eb, slot);
+	do {
+		u16 sub_item_type;
+		u64 sub_item_len;
+
+		if (item_size < sizeof(*ptr)) {
+			pr_warn("btrfs: uuid item too short (%lu < %d)!\n",
+				(unsigned long)item_size, (int)sizeof(*ptr));
+			return NULL;
+		}
+		item_size -= sizeof(*ptr);
+		sub_item_type = btrfs_uuid_type(eb, ptr);
+		sub_item_len = btrfs_uuid_len(eb, ptr);
+		if (sub_item_len * sizeof(u64) > item_size) {
+			pr_warn("btrfs: uuid item too short (%llu > %lu)!\n",
+				(unsigned long long)(sub_item_len *
+						     sizeof(u64)),
+				(unsigned long)item_size);
+			return NULL;
+		}
+		if (sub_item_type == type)
+			return ptr;
+		item_size -= sub_item_len * sizeof(u64);
+		ptr = 1 + (struct btrfs_uuid_item *)
+			(((char *)ptr) + (sub_item_len * sizeof(u64)));
+	} while (item_size);
+
+	return NULL;
+}
+
+static int btrfs_uuid_tree_lookup_prepare(struct btrfs_root *uuid_root,
+					  u8 *uuid, u16 type,
+					  struct btrfs_path *path,
+					  struct btrfs_uuid_item **ptr)
+{
+	int ret;
+	struct btrfs_key key;
+
+	if (!uuid_root) {
+		WARN_ON_ONCE(1);
+		ret = -ENOENT;
+		goto out;
+	}
+
+	btrfs_uuid_to_key(uuid, &key);
+
+	ret = btrfs_search_slot(NULL, uuid_root, &key, path, 0, 0);
+	if (ret < 0)
+		goto out;
+	if (ret > 0) {
+		ret = -ENOENT;
+		goto out;
+	}
+
+	*ptr = btrfs_match_uuid_item_type(path, type);
+	if (!*ptr) {
+		ret = -ENOENT;
+		goto out;
+	}
+
+	ret = 0;
+
+out:
+	return ret;
+}
+
+/* return -ENOENT for !found, < 0 for errors, or 0 if an item was found */
+static int btrfs_uuid_tree_lookup(struct btrfs_root *uuid_root, u8 *uuid,
+				  u16 type, u64 subid)
+{
+	int ret;
+	struct btrfs_path *path;
+	struct extent_buffer *eb;
+	struct btrfs_uuid_item *ptr;
+	u32 sub_item_len;
+	unsigned long offset;
+
+	path = btrfs_alloc_path();
+	if (!path) {
+		ret = -ENOMEM;
+		goto out;
+	}
+
+	ret = btrfs_uuid_tree_lookup_prepare(uuid_root, uuid, type, path, &ptr);
+	if (ret < 0)
+		goto out;
+
+	eb = path->nodes[0];
+	sub_item_len = btrfs_uuid_len(eb, ptr);
+	WARN_ON_ONCE(sub_item_len == 0);
+	ret = -ENOENT;
+	ptr++;
+	offset = (unsigned long)ptr;
+	while (sub_item_len > 0) {
+		u64 data;
+
+		read_extent_buffer(eb, &data, offset, sizeof(data));
+		data = le64_to_cpu(data);
+		if (data == subid) {
+			ret = 0;
+			break;
+		}
+		offset += sizeof(data);
+		sub_item_len--;
+	}
+
+out:
+	btrfs_free_path(path);
+	return ret;
+}
+
+/* return -ENOENT for !found, < 0 for errors, or 0 if an item was found */
+static int btrfs_uuid_tree_lookup_any(struct btrfs_root *uuid_root, u8 *uuid,
+				      u16 type, u64 *subid)
+{
+	int ret;
+	struct btrfs_path *path;
+	struct extent_buffer *eb;
+	struct btrfs_uuid_item *ptr;
+	u32 sub_item_len;
+
+	path = btrfs_alloc_path();
+	if (!path) {
+		ret = -ENOMEM;
+		goto out;
+	}
+
+	ret = btrfs_uuid_tree_lookup_prepare(uuid_root, uuid, type, path, &ptr);
+	if (ret < 0)
+		goto out;
+
+	eb = path->nodes[0];
+	sub_item_len = btrfs_uuid_len(eb, ptr);
+	WARN_ON_ONCE(sub_item_len == 0);
+	if (sub_item_len > 0) {
+		/* return first stored id */
+		read_extent_buffer(eb, subid, (unsigned long)(ptr + 1),
+				   sizeof(*subid));
+		*subid = le64_to_cpu(*subid);
+		ret = 0;
+	} else {
+		ret = -ENOENT;
+	}
+
+out:
+	btrfs_free_path(path);
+	return ret;
+}
+
+/* it is not checked whether the entry to add already exists */
+static int btrfs_uuid_tree_add(struct btrfs_trans_handle *trans,
+			       struct btrfs_root *uuid_root, u8 *uuid,
+			       u16 type, u64 subid)
+{
+	int ret;
+	struct btrfs_path *path = NULL;
+	struct btrfs_key key;
+	struct extent_buffer *eb;
+	int slot;
+	struct btrfs_uuid_item *ptr;
+	u32 item_size;
+
+	if (!uuid_root) {
+		WARN_ON_ONCE(1);
+		ret = -EINVAL;
+		goto out;
+	}
+
+	btrfs_uuid_to_key(uuid, &key);
+
+	path = btrfs_alloc_path();
+	if (!path) {
+		ret = -ENOMEM;
+		goto out;
+	}
+
+	ret = btrfs_insert_empty_item(trans, uuid_root, path, &key,
+				      sizeof(*ptr) + sizeof(subid));
+	if (ret == -EEXIST) {
+		ptr = btrfs_match_uuid_item_type(path, type);
+		if (ptr) {
+			/*
+			 * An item with that type already exists.
+			 * Extend the item and store the subid at the
+			 * location of the first id of this type.
+			 */
+			unsigned long start;
+			unsigned long move_dst;
+			unsigned long move_src;
+			unsigned long move_len;
+
+			btrfs_extend_item(uuid_root, path, sizeof(subid));
+			ptr = (struct btrfs_uuid_item *)
+				(((char *)ptr) - sizeof(subid));
+			eb = path->nodes[0];
+			slot = path->slots[0];
+			item_size = btrfs_item_size_nr(eb, slot);
+			WARN_ON(btrfs_uuid_len(eb, ptr) == 0);
+			btrfs_set_uuid_len(eb, ptr,
+					   btrfs_uuid_len(eb, ptr) + 1);
+			ptr++;
+			start = btrfs_item_ptr_offset(eb, slot);
+			move_dst = ((unsigned long)ptr) + sizeof(subid);
+			move_src = (unsigned long)ptr;
+			move_len = item_size - (move_dst - start);
+			memmove_extent_buffer(eb, move_dst, move_src, move_len);
+
+			goto write_subid;
+		} else {
+			btrfs_extend_item(uuid_root, path,
+					  sizeof(*ptr) + sizeof(subid));
+		}
+	} else if (ret < 0) {
+		pr_warn("btrfs: insert uuid item failed %d (0x%016llx, 0x%016llx) type
%lu!\n",
+			ret, (unsigned long long)key.objectid,
+			(unsigned long long)key.offset,
+			(unsigned long)type);
+		goto out;
+	}
+
+	/*
+	 * Add an item for the type for the first time. Either add it behind
+	 * items with different types, or write the very first item.
+	 */
+	eb = path->nodes[0];
+	slot = path->slots[0];
+	ptr = btrfs_item_ptr(eb, slot, struct btrfs_uuid_item);
+	item_size = btrfs_item_size_nr(eb, slot);
+	ptr = (struct btrfs_uuid_item *)
+		(((char *)ptr) + item_size - (sizeof(*ptr) + sizeof(subid)));
+	btrfs_set_uuid_type(eb, ptr, type);
+	btrfs_set_uuid_len(eb, ptr, 1);
+	ptr++;
+
+write_subid:
+	ret = 0;
+	subid = cpu_to_le64(subid);
+	write_extent_buffer(eb, &subid, (unsigned long)ptr, sizeof(subid));
+	btrfs_mark_buffer_dirty(eb);
+
+out:
+	btrfs_free_path(path);
+	return ret;
+}
+
+static int btrfs_uuid_tree_rem(struct btrfs_trans_handle *trans,
+			       struct btrfs_root *uuid_root, u8 *uuid,
+			       u16 type, u64 subid)
+{
+	int ret;
+	struct btrfs_path *path = NULL;
+	struct btrfs_key key;
+	struct extent_buffer *eb;
+	int slot;
+	struct btrfs_uuid_item *ptr_start;
+	unsigned long offset;
+	u32 item_size;
+	u32 id_index;
+	unsigned long start;
+	unsigned long move_dst;
+	unsigned long move_src;
+	unsigned long move_len;
+
+	if (!uuid_root) {
+		WARN_ON_ONCE(1);
+		ret = -EINVAL;
+		goto out;
+	}
+
+	btrfs_uuid_to_key(uuid, &key);
+
+	path = btrfs_alloc_path();
+	if (!path) {
+		ret = -ENOMEM;
+		goto out;
+	}
+
+	ret = btrfs_search_slot(trans, uuid_root, &key, path, -1, 1);
+	if (ret < 0) {
+		pr_warn("btrfs: error %d while searching for uuid item!\n",
+			ret);
+		goto out;
+	}
+	if (ret > 0) {
+		ret = -ENOENT;
+		goto out;
+	}
+
+	ptr_start = btrfs_match_uuid_item_type(path, type);
+	if (!ptr_start) {
+		/* case 1: no entry for that type is found */
+		ret = -ENOENT;
+		goto out;
+	}
+
+	eb = path->nodes[0];
+	slot = path->slots[0];
+	start = btrfs_item_ptr_offset(eb, slot);
+	item_size = btrfs_item_size_nr(eb, slot);
+	id_index = btrfs_uuid_len(eb, ptr_start);
+	offset = (unsigned long)(ptr_start + 1);
+	while (id_index > 0) {
+		u64 found_subid;
+
+		read_extent_buffer(eb, &found_subid, offset,
+				   sizeof(found_subid));
+		found_subid = le64_to_cpu(found_subid);
+		if (found_subid == subid)
+			break;
+		offset += sizeof(found_subid);
+		id_index--;
+	}
+
+	if (!id_index) {
+		/*
+		 * case 2: an entry for that type is found, but no match
+		 * for the id
+		 */
+		ret = -ENOENT;
+		goto out;
+	}
+
+	if (btrfs_uuid_len(eb, ptr_start) == 1) {
+		if (item_size == sizeof(*ptr_start) + sizeof(subid)) {
+			/*
+			 * case 3: no other types and ids are stored,
+			 * delete the full item
+			 */
+			ret = btrfs_del_item(trans, uuid_root, path);
+			goto out;
+		} else {
+			/*
+			 * case 4: No other ids for the particular type
+			 * are stored, but other types exist. Shrink the
+			 * item by the size of an id plus the size of the
+			 * item for that type.
+			 */
+			move_dst = (unsigned long)ptr_start;
+		}
+	} else {
+		/*
+		 * case 5: Other ids for that particular type are stored.
+		 * Shrink the item by the size of an id.
+		 */
+		move_dst = offset;
+		WARN_ON(btrfs_uuid_len(eb, ptr_start) == 0);
+		btrfs_set_uuid_len(eb, ptr_start,
+				   btrfs_uuid_len(eb, ptr_start) - 1);
+	}
+	move_src = offset + sizeof(subid);
+	move_len = item_size - (move_src - start);
+
+	memmove_extent_buffer(eb, move_dst, move_src, move_len);
+	btrfs_truncate_item(uuid_root, path, item_size - (move_src - move_dst),
+			    1);
+
+out:
+	btrfs_free_path(path);
+	return ret;
+}
+
+int btrfs_lookup_uuid_subvol_item(struct btrfs_root *uuid_root, u8 *uuid,
+				  u64 *subvol_id)
+{
+	return btrfs_uuid_tree_lookup_any(uuid_root, uuid,
+					  BTRFS_UUID_ITEM_TYPE_SUBVOL,
+					  subvol_id);
+}
+
+int btrfs_insert_uuid_subvol_item(struct btrfs_trans_handle *trans,
+				  struct btrfs_root *uuid_root, u8 *uuid,
+				  u64 subvol_id)
+{
+	int ret;
+
+	ret = btrfs_uuid_tree_lookup(uuid_root, uuid,
+				     BTRFS_UUID_ITEM_TYPE_SUBVOL, subvol_id);
+	if (ret == -ENOENT)
+		ret = btrfs_uuid_tree_add(trans, uuid_root, uuid,
+					  BTRFS_UUID_ITEM_TYPE_SUBVOL,
+					  subvol_id);
+	return ret;
+}
+
+int btrfs_del_uuid_subvol_item(struct btrfs_trans_handle *trans,
+			       struct btrfs_root *uuid_root, u8 *uuid,
+			       u64 subvol_id)
+{
+	return btrfs_uuid_tree_rem(trans, uuid_root, uuid,
+				   BTRFS_UUID_ITEM_TYPE_SUBVOL, subvol_id);
+}
+
+int btrfs_lookup_uuid_received_subvol_item(struct btrfs_root *uuid_root,
+					   u8 *uuid, u64 *subvol_id)
+{
+	return btrfs_uuid_tree_lookup_any(uuid_root, uuid,
+					  BTRFS_UUID_ITEM_TYPE_RECEIVED_SUBVOL,
+					  subvol_id);
+}
+
+int btrfs_insert_uuid_received_subvol_item(struct btrfs_trans_handle *trans,
+					   struct btrfs_root *uuid_root,
+					   u8 *uuid, u64 subvol_id)
+{
+	int ret;
+
+	ret = btrfs_uuid_tree_lookup(uuid_root, uuid,
+				     BTRFS_UUID_ITEM_TYPE_RECEIVED_SUBVOL,
+				     subvol_id);
+	if (ret == -ENOENT)
+		ret = btrfs_uuid_tree_add(trans, uuid_root, uuid,
+					  BTRFS_UUID_ITEM_TYPE_RECEIVED_SUBVOL,
+					  subvol_id);
+	return ret;
+}
+
+int btrfs_del_uuid_received_subvol_item(struct btrfs_trans_handle *trans,
+					struct btrfs_root *uuid_root, u8 *uuid,
+					u64 subvol_id)
+{
+	return btrfs_uuid_tree_rem(trans, uuid_root, uuid,
+				   BTRFS_UUID_ITEM_TYPE_RECEIVED_SUBVOL,
+				   subvol_id);
+}
-- 
1.8.3

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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

Signed-off-by: Stefan Behrens <sbehrens@giantdisaster.de>
---
 fs/btrfs/print-tree.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 81 insertions(+)

diff --git a/fs/btrfs/print-tree.c b/fs/btrfs/print-tree.c
index dc0024f..c27f08b 100644
--- a/fs/btrfs/print-tree.c
+++ b/fs/btrfs/print-tree.c
@@ -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;
 		};
 	}
 }
-- 
1.8.3

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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 <sbehrens@giantdisaster.de>
---
 fs/btrfs/ctree.h       |  1 +
 fs/btrfs/disk-io.c     | 34 ++++++++++++++++++++++++++++++++++
 fs/btrfs/extent-tree.c |  3 +++
 fs/btrfs/volumes.c     | 26 ++++++++++++++++++++++++++
 fs/btrfs/volumes.h     |  1 +
 5 files changed, 65 insertions(+)

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 04447b6..1dac165 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -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;
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 3c2886c..1db446a 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -1580,6 +1580,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:
 	root = btrfs_lookup_fs_root(fs_info, location->objectid);
 	if (root)
@@ -2037,6 +2040,12 @@ 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) {
+		free_extent_buffer(info->uuid_root->node);
+		free_extent_buffer(info->uuid_root->commit_root);
+		info->uuid_root->node = NULL;
+		info->uuid_root->commit_root = NULL;
+	}
 	if (chunk_root) {
 		free_extent_buffer(info->chunk_root->node);
 		free_extent_buffer(info->chunk_root->commit_root);
@@ -2097,11 +2106,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);
 	chunk_root = fs_info->chunk_root = btrfs_alloc_root(fs_info);
@@ -2695,6 +2706,18 @@ retry_root_backup:
 		fs_info->quota_root = quota_root;
 	}
 
+	location.objectid = BTRFS_UUID_TREE_OBJECTID;
+	uuid_root = btrfs_read_tree_root(tree_root, &location);
+	if (IS_ERR(uuid_root)) {
+		ret = PTR_ERR(uuid_root);
+		if (ret != -ENOENT)
+			goto recovery_tree_root;
+		create_uuid_tree = true;
+	} else {
+		uuid_root->track_dirty = 1;
+		fs_info->uuid_root = uuid_root;
+	}
+
 	fs_info->generation = generation;
 	fs_info->last_trans_committed = generation;
 
@@ -2881,6 +2904,17 @@ retry_root_backup:
 
 	btrfs_qgroup_rescan_resume(fs_info);
 
+	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:
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 6d5c5f7..1c4694a 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -4308,6 +4308,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;
 
diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c
index c58bf19..d4c7955 100644
--- a/fs/btrfs/volumes.c
+++ b/fs/btrfs/volumes.c
@@ -3411,6 +3411,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.
diff --git a/fs/btrfs/volumes.h b/fs/btrfs/volumes.h
index 857acd3..c3fcd60 100644
--- a/fs/btrfs/volumes.h
+++ b/fs/btrfs/volumes.h
@@ -315,6 +315,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);
-- 
1.8.3

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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 <sbehrens@giantdisaster.de>
---
 fs/btrfs/ctree.h       |  1 +
 fs/btrfs/ioctl.c       | 74 +++++++++++++++++++++++++++++++++++++++++++-------
 fs/btrfs/transaction.c | 19 ++++++++++++-
 3 files changed, 83 insertions(+), 11 deletions(-)

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 1dac165..f2751e7 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -3678,6 +3678,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);
diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index 0e17a30..4e0c292 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -363,6 +363,13 @@ static noinline int btrfs_ioctl_fitrim(struct file *file,
void __user *arg)
 	return 0;
 }
 
+int btrfs_is_empty_uuid(u8 *uuid)
+{
+	static char empty_uuid[BTRFS_UUID_SIZE] = {0};
+
+	return !memcmp(uuid, empty_uuid, BTRFS_UUID_SIZE);
+}
+
 static noinline int create_subvol(struct inode *dir,
 				  struct dentry *dentry,
 				  char *name, int namelen,
@@ -396,7 +403,7 @@ static noinline int create_subvol(struct inode *dir,
 	 * of create_snapshot().
 	 */
 	ret = btrfs_subvolume_reserve_metadata(root, &block_rsv,
-					       7, &qgroup_reserved);
+					       8, &qgroup_reserved);
 	if (ret)
 		return ret;
 
@@ -518,9 +525,13 @@ static noinline int create_subvol(struct inode *dir,
 	ret = btrfs_add_root_ref(trans, root->fs_info->tree_root,
 				 objectid, root->root_key.objectid,
 				 btrfs_ino(dir), index, name, namelen);
-
 	BUG_ON(ret);
 
+	ret = btrfs_insert_uuid_subvol_item(trans, root->fs_info->uuid_root,
+					    root_item.uuid, objectid);
+	if (ret)
+		btrfs_abort_transaction(trans, root, ret);
+
 fail:
 	trans->block_rsv = NULL;
 	trans->bytes_reserved = 0;
@@ -573,9 +584,10 @@ static int create_snapshot(struct btrfs_root *root, struct
inode *dir,
 	 * 1 - root item
 	 * 2 - root ref/backref
 	 * 1 - root of snapshot
+	 * 1 - UUID item
 	 */
 	ret = btrfs_subvolume_reserve_metadata(BTRFS_I(dir)->root,
-					&pending_snapshot->block_rsv, 7,
+					&pending_snapshot->block_rsv, 8,
 					&pending_snapshot->qgroup_reserved);
 	if (ret)
 		goto out;
@@ -2213,6 +2225,27 @@ static noinline int btrfs_ioctl_snap_destroy(struct file
*file,
 			goto out_end_trans;
 		}
 	}
+
+	ret = btrfs_del_uuid_subvol_item(trans, root->fs_info->uuid_root,
+					 dest->root_item.uuid,
+					 dest->root_key.objectid);
+	if (ret && ret != -ENOENT) {
+		btrfs_abort_transaction(trans, root, ret);
+		err = ret;
+		goto out_end_trans;
+	}
+	if (!btrfs_is_empty_uuid(dest->root_item.received_uuid)) {
+		ret = btrfs_del_uuid_received_subvol_item(trans,
+				root->fs_info->uuid_root,
+				dest->root_item.received_uuid,
+				dest->root_key.objectid);
+		if (ret && ret != -ENOENT) {
+			btrfs_abort_transaction(trans, root, ret);
+			err = ret;
+			goto out_end_trans;
+		}
+	}
+
 out_end_trans:
 	trans->block_rsv = NULL;
 	trans->bytes_reserved = 0;
@@ -2424,7 +2457,6 @@ static long btrfs_ioctl_dev_info(struct btrfs_root *root,
void __user *arg)
 	struct btrfs_fs_devices *fs_devices = root->fs_info->fs_devices;
 	int ret = 0;
 	char *s_uuid = NULL;
-	char empty_uuid[BTRFS_UUID_SIZE] = {0};
 
 	if (!capable(CAP_SYS_ADMIN))
 		return -EPERM;
@@ -2433,7 +2465,7 @@ static long btrfs_ioctl_dev_info(struct btrfs_root *root,
void __user *arg)
 	if (IS_ERR(di_args))
 		return PTR_ERR(di_args);
 
-	if (memcmp(empty_uuid, di_args->uuid, BTRFS_UUID_SIZE) != 0)
+	if (!btrfs_is_empty_uuid(di_args->uuid))
 		s_uuid = di_args->uuid;
 
 	mutex_lock(&fs_devices->device_list_mutex);
@@ -3967,6 +3999,7 @@ static long btrfs_ioctl_set_received_subvol(struct file
*file,
 	struct btrfs_trans_handle *trans;
 	struct timespec ct = CURRENT_TIME;
 	int ret = 0;
+	int received_uuid_changed;
 
 	ret = mnt_want_write_file(file);
 	if (ret < 0)
@@ -3996,7 +4029,11 @@ static long btrfs_ioctl_set_received_subvol(struct file
*file,
 		goto out;
 	}
 
-	trans = btrfs_start_transaction(root, 1);
+	/*
+	 * 1 - root item
+	 * 2 - uuid items (received uuid + subvol uuid)
+	 */
+	trans = btrfs_start_transaction(root, 3);
 	if (IS_ERR(trans)) {
 		ret = PTR_ERR(trans);
 		trans = NULL;
@@ -4007,6 +4044,14 @@ static long btrfs_ioctl_set_received_subvol(struct file
*file,
 	sa->rtime.sec = ct.tv_sec;
 	sa->rtime.nsec = ct.tv_nsec;
 
+	received_uuid_changed = memcmp(root_item->received_uuid, sa->uuid,
+				       BTRFS_UUID_SIZE);
+	if (received_uuid_changed &&
+	    !btrfs_is_empty_uuid(root_item->received_uuid))
+		btrfs_del_uuid_received_subvol_item(trans,
+						    root->fs_info->uuid_root,
+						    root_item->received_uuid,
+						    root->root_key.objectid);
 	memcpy(root_item->received_uuid, sa->uuid, BTRFS_UUID_SIZE);
 	btrfs_set_root_stransid(root_item, sa->stransid);
 	btrfs_set_root_rtransid(root_item, sa->rtransid);
@@ -4019,12 +4064,21 @@ static long btrfs_ioctl_set_received_subvol(struct file
*file,
 				&root->root_key, &root->root_item);
 	if (ret < 0) {
 		btrfs_end_transaction(trans, root);
-		trans = NULL;
 		goto out;
-	} else {
-		ret = btrfs_commit_transaction(trans, root);
-		if (ret < 0)
+	}
+	if (received_uuid_changed && !btrfs_is_empty_uuid(sa->uuid)) {
+		ret = btrfs_insert_uuid_received_subvol_item(
+			trans, root->fs_info->uuid_root, sa->uuid,
+			root->root_key.objectid);
+		if (ret < 0 && ret != -EEXIST) {
+			btrfs_abort_transaction(trans, root, ret);
 			goto out;
+		}
+	}
+	ret = btrfs_commit_transaction(trans, root);
+	if (ret < 0) {
+		btrfs_abort_transaction(trans, root, ret);
+		goto out;
 	}
 
 	ret = copy_to_user(arg, sa, sizeof(*sa));
diff --git a/fs/btrfs/transaction.c b/fs/btrfs/transaction.c
index bcfa32c..00ae884 100644
--- a/fs/btrfs/transaction.c
+++ b/fs/btrfs/transaction.c
@@ -1302,8 +1302,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:
-- 
1.8.3

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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 <sbehrens@giantdisaster.de>
---
 fs/btrfs/ctree.h   |   2 +
 fs/btrfs/disk-io.c |   6 +++
 fs/btrfs/volumes.c | 148 ++++++++++++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 155 insertions(+), 1 deletion(-)

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index f2751e7..89b2d78 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -1645,6 +1645,8 @@ struct btrfs_fs_info {
 	struct btrfs_dev_replace dev_replace;
 
 	atomic_t mutually_exclusive_operation_running;
+
+	struct completion uuid_tree_rescan_completion;
 };
 
 /*
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 1db446a..a52504b 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -2288,6 +2288,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);
+	init_completion(&fs_info->uuid_tree_rescan_completion);
 	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);
@@ -2913,6 +2914,8 @@ retry_root_backup:
 			close_ctree(tree_root);
 			return ret;
 		}
+	} else {
+		complete_all(&fs_info->uuid_tree_rescan_completion);
 	}
 
 	return 0;
@@ -3543,6 +3546,9 @@ int close_ctree(struct btrfs_root *root)
 	fs_info->closing = 1;
 	smp_mb();
 
+	/* wait for the uuid_scan task to finish */
+	wait_for_completion(&fs_info->uuid_tree_rescan_completion);
+
 	/* pause restriper - we want to resume on mount */
 	btrfs_pause_balance(fs_info);
 
diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c
index d4c7955..e2e2bbc 100644
--- a/fs/btrfs/volumes.c
+++ b/fs/btrfs/volumes.c
@@ -3411,11 +3411,145 @@ int btrfs_cancel_balance(struct btrfs_fs_info *fs_info)
 	return 0;
 }
 
+static int btrfs_uuid_scan_kthread(void *data)
+{
+	struct btrfs_fs_info *fs_info = data;
+	struct btrfs_root *root = fs_info->tree_root;
+	struct btrfs_key key;
+	struct btrfs_key max_key;
+	struct btrfs_path *path = NULL;
+	int ret = 0;
+	struct extent_buffer *eb;
+	int slot;
+	struct btrfs_root_item root_item;
+	u32 item_size;
+	struct btrfs_trans_handle *trans;
+
+	path = btrfs_alloc_path();
+	if (!path) {
+		ret = -ENOMEM;
+		goto out;
+	}
+
+	key.objectid = 0;
+	key.type = BTRFS_ROOT_ITEM_KEY;
+	key.offset = 0;
+
+	max_key.objectid = (u64)-1;
+	max_key.type = BTRFS_ROOT_ITEM_KEY;
+	max_key.offset = (u64)-1;
+
+	path->keep_locks = 1;
+
+	while (1) {
+		ret = btrfs_search_forward(root, &key, &max_key, path, 0);
+		if (ret) {
+			if (ret > 0)
+				ret = 0;
+			break;
+		}
+
+		if (key.type != BTRFS_ROOT_ITEM_KEY ||
+		    (key.objectid < BTRFS_FIRST_FREE_OBJECTID &&
+		     key.objectid != BTRFS_FS_TREE_OBJECTID) ||
+		    key.objectid > BTRFS_LAST_FREE_OBJECTID)
+			goto skip;
+
+		eb = path->nodes[0];
+		slot = path->slots[0];
+		item_size = btrfs_item_size_nr(eb, slot);
+		if (item_size < sizeof(root_item))
+			goto skip;
+
+		trans = NULL;
+		read_extent_buffer(eb, &root_item,
+				   btrfs_item_ptr_offset(eb, slot),
+				   (int)sizeof(root_item));
+		if (btrfs_root_refs(&root_item) == 0)
+			goto skip;
+		if (!btrfs_is_empty_uuid(root_item.uuid)) {
+			/*
+			 * 1 - subvol uuid item
+			 * 1 - received_subvol uuid item
+			 */
+			trans = btrfs_start_transaction(fs_info->uuid_root, 2);
+			if (IS_ERR(trans)) {
+				ret = PTR_ERR(trans);
+				break;
+			}
+			ret = btrfs_insert_uuid_subvol_item(trans,
+							    fs_info->uuid_root,
+							    root_item.uuid,
+							    key.objectid);
+			if (ret < 0) {
+				pr_warn("btrfs: insert_uuid_received_subvol_item failed %d\n",
+					ret);
+				btrfs_end_transaction(trans,
+						      fs_info->uuid_root);
+				break;
+			}
+		}
+
+		if (!btrfs_is_empty_uuid(root_item.received_uuid)) {
+			if (!trans) {
+				/* 1 - received_subvol uuid item */
+				trans = btrfs_start_transaction(
+						fs_info->uuid_root, 1);
+				if (IS_ERR(trans)) {
+					ret = PTR_ERR(trans);
+					break;
+				}
+			}
+			ret = btrfs_insert_uuid_received_subvol_item(
+				trans, fs_info->uuid_root,
+				root_item.received_uuid, key.objectid);
+			if (ret < 0) {
+				pr_warn("btrfs: insert_uuid_received_subvol_item failed %d\n",
+					ret);
+				btrfs_end_transaction(trans,
+						      fs_info->uuid_root);
+				break;
+			}
+		}
+
+		if (trans) {
+			ret = btrfs_end_transaction(trans, fs_info->uuid_root);
+			if (ret)
+				break;
+		}
+
+skip:
+		btrfs_release_path(path);
+		if (key.offset < (u64)-1) {
+			key.offset++;
+		} else if (key.type < BTRFS_ROOT_ITEM_KEY) {
+			key.offset = 0;
+			key.type = BTRFS_ROOT_ITEM_KEY;
+		} else if (key.objectid < (u64)-1) {
+			key.offset = 0;
+			key.type = BTRFS_ROOT_ITEM_KEY;
+			key.objectid++;
+		} else {
+			break;
+		}
+		cond_resched();
+	}
+
+out:
+	btrfs_free_path(path);
+	if (ret)
+		pr_warn("btrfs: btrfs_uuid_scan_kthread failed %d\n", ret);
+	complete_all(&fs_info->uuid_tree_rescan_completion);
+	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;
+	struct task_struct *task;
+	int ret;
 
 	/*
 	 * 1 - root node
@@ -3435,8 +3569,20 @@ int btrfs_create_uuid_tree(struct btrfs_fs_info *fs_info)
 
 	fs_info->uuid_root = uuid_root;
 
-	return btrfs_commit_transaction(trans, tree_root);
+	ret = btrfs_commit_transaction(trans, tree_root);
+	if (ret)
+		return ret;
+
+	task = kthread_run(btrfs_uuid_scan_kthread, fs_info, "btrfs-uuid");
+	if (IS_ERR(task)) {
+		pr_warn("btrfs: failed to start uuid_scan task\n");
+		complete_all(&fs_info->uuid_tree_rescan_completion);
+		return PTR_ERR(task);
+	}
+
+	return 0;
 }
+
 /*
  * shrinking a device means finding all of the device extents past
  * the new size, and then following the back refs to the chunks.
-- 
1.8.3

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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 <sbehrens@giantdisaster.de>
---
 fs/btrfs/ctree.h       | 5 ++++-
 fs/btrfs/transaction.c | 1 +
 2 files changed, 5 insertions(+), 1 deletion(-)

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 89b2d78..424c38d 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -481,9 +481,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__));
@@ -2847,6 +2848,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)
 {
diff --git a/fs/btrfs/transaction.c b/fs/btrfs/transaction.c
index 00ae884..1ae9621 100644
--- a/fs/btrfs/transaction.c
+++ b/fs/btrfs/transaction.c
@@ -1370,6 +1370,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)
-- 
1.8.3

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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 <sbehrens@giantdisaster.de>
---
 fs/btrfs/ctree.h       |   4 ++
 fs/btrfs/disk-io.c     |  17 +++++-
 fs/btrfs/transaction.c |   3 +-
 fs/btrfs/uuid-tree.c   | 156 +++++++++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/volumes.c     |  82 ++++++++++++++++++++++++++
 fs/btrfs/volumes.h     |   1 +
 6 files changed, 261 insertions(+), 2 deletions(-)

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 424c38d..817894d 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -1648,6 +1648,7 @@ struct btrfs_fs_info {
 	atomic_t mutually_exclusive_operation_running;
 
 	struct completion uuid_tree_rescan_completion;
+	unsigned int update_uuid_tree_gen:1;
 };
 
 /*
@@ -3453,6 +3454,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,
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index a52504b..7508b3a 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -2112,7 +2112,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);
 	chunk_root = fs_info->chunk_root = btrfs_alloc_root(fs_info);
@@ -2714,9 +2715,13 @@ retry_root_backup:
 		if (ret != -ENOENT)
 			goto recovery_tree_root;
 		create_uuid_tree = true;
+		check_uuid_tree = false;
 	} else {
 		uuid_root->track_dirty = 1;
 		fs_info->uuid_root = uuid_root;
+		create_uuid_tree = false;
+		check_uuid_tree +		    generation !=
btrfs_super_uuid_tree_generation(disk_super);
 	}
 
 	fs_info->generation = generation;
@@ -2914,7 +2919,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;
 		complete_all(&fs_info->uuid_tree_rescan_completion);
 	}
 
diff --git a/fs/btrfs/transaction.c b/fs/btrfs/transaction.c
index 1ae9621..cf07548 100644
--- a/fs/btrfs/transaction.c
+++ b/fs/btrfs/transaction.c
@@ -1370,7 +1370,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)
diff --git a/fs/btrfs/uuid-tree.c b/fs/btrfs/uuid-tree.c
index 3939a54..59697d1 100644
--- a/fs/btrfs/uuid-tree.c
+++ b/fs/btrfs/uuid-tree.c
@@ -415,6 +415,162 @@ out:
 	return ret;
 }
 
+static int btrfs_uuid_iter_rem(struct btrfs_root *uuid_root, u8 *uuid,
+			       u16 sub_item_type, u64 subid)
+{
+	struct btrfs_trans_handle *trans;
+	int ret;
+
+	/* 1 - for the uuid item */
+	trans = btrfs_start_transaction(uuid_root, 1);
+	if (IS_ERR(trans)) {
+		ret = PTR_ERR(trans);
+		goto out;
+	}
+
+	ret = btrfs_uuid_tree_rem(trans, uuid_root, uuid,
+				  sub_item_type, subid);
+	btrfs_end_transaction(trans, uuid_root);
+
+out:
+	return ret;
+}
+
+int btrfs_uuid_tree_iterate(struct btrfs_fs_info *fs_info,
+			    int (*check_func)(struct btrfs_fs_info *, u8 *, u16,
+					      u64))
+{
+	struct btrfs_root *root = fs_info->uuid_root;
+	struct btrfs_key key;
+	struct btrfs_key max_key;
+	struct btrfs_path *path = NULL;
+	int ret = 0;
+	struct extent_buffer *eb;
+	int slot;
+	u32 item_size;
+	struct btrfs_uuid_item *ptr;
+	u64 subid;
+	unsigned long offset;
+
+	path = btrfs_alloc_path();
+	if (!path) {
+		ret = -ENOMEM;
+		goto out;
+	}
+
+	key.objectid = 0;
+	key.type = BTRFS_UUID_KEY;
+	key.offset = 0;
+
+	max_key.objectid = (u64)-1;
+	max_key.type = BTRFS_UUID_KEY;
+	max_key.offset = (u64)-1;
+
+	path->keep_locks = 1;
+
+	while (1) {
+again:
+		cond_resched();
+		ret = btrfs_search_forward(root, &key, &max_key, path, 0);
+		if (ret) {
+			if (ret > 0)
+				ret = 0;
+			break;
+		}
+
+		if (key.type != BTRFS_UUID_KEY)
+			goto skip;
+
+		eb = path->nodes[0];
+		slot = path->slots[0];
+		ptr = btrfs_item_ptr(eb, slot, struct btrfs_uuid_item);
+		item_size = btrfs_item_size_nr(eb, slot);
+		do {
+			u16 sub_item_type;
+			u64 sub_item_len;
+
+			if (item_size < sizeof(*ptr)) {
+				pr_warn("btrfs: uuid item too short (%lu < %d)!\n",
+					(unsigned long)item_size,
+					(int)sizeof(*ptr));
+				goto skip; /* is this an old kernel? */
+			}
+			sub_item_type = btrfs_uuid_type(eb, ptr);
+			sub_item_len = btrfs_uuid_len(eb, ptr);
+			ptr++;
+			item_size -= sizeof(*ptr);
+			if (sub_item_len * sizeof(u64) > item_size) {
+				pr_warn("btrfs: uuid item too short (%llu > %lu)!\n",
+					(unsigned long long)(sub_item_len *
+							     sizeof(u64)),
+					(unsigned long)item_size);
+				goto skip;
+			}
+			offset = (unsigned long)ptr;
+			ptr = (struct btrfs_uuid_item *)
+				(((char *)ptr) + sub_item_len * sizeof(u64));
+			item_size -= sub_item_len * sizeof(u64);
+			while (sub_item_len) {
+				u8 uuid[BTRFS_UUID_SIZE];
+
+				put_unaligned_le64(key.objectid, uuid);
+				put_unaligned_le64(key.offset,
+						   uuid + sizeof(u64));
+				read_extent_buffer(eb, &subid, offset,
+						   sizeof(subid));
+				subid = le64_to_cpu(subid);
+				ret = check_func(fs_info, uuid,
+						 sub_item_type, subid);
+				if (ret < 0)
+					goto out;
+				if (ret > 0) {
+					btrfs_release_path(path);
+					ret = btrfs_uuid_iter_rem(
+						fs_info->uuid_root, uuid,
+						sub_item_type, subid);
+					if (ret == 0) {
+						/*
+						 * this might look inefficient,
+						 * but the justification is that
+						 * it is an exception that
+						 * check_func returns 1, and
+						 * that in the regular case only
+						 * one or two entries per UUID
+						 * exist.
+						 */
+						goto again;
+					}
+					if (ret < 0 && ret != -ENOENT)
+						goto out;
+				}
+				sub_item_len--;
+				offset += sizeof(u64);
+			}
+		} while (item_size);
+
+skip:
+		btrfs_release_path(path);
+		if (key.offset < (u64)-1) {
+			key.offset++;
+		} else if (key.type < BTRFS_UUID_KEY) {
+			key.offset = 0;
+			key.type = BTRFS_UUID_KEY;
+		} else if (key.objectid < (u64)-1) {
+			key.offset = 0;
+			key.type = 0;
+			key.objectid++;
+		} else {
+			break;
+		}
+	}
+
+out:
+	btrfs_free_path(path);
+	if (ret)
+		pr_warn("btrfs: btrfs_uuid_tree_iterate failed %d\n", ret);
+	return 0;
+}
+
 int btrfs_lookup_uuid_subvol_item(struct btrfs_root *uuid_root, u8 *uuid,
 				  u64 *subvol_id)
 {
diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c
index e2e2bbc..44e148f 100644
--- a/fs/btrfs/volumes.c
+++ b/fs/btrfs/volumes.c
@@ -3539,10 +3539,76 @@ out:
 	btrfs_free_path(path);
 	if (ret)
 		pr_warn("btrfs: btrfs_uuid_scan_kthread failed %d\n", ret);
+	else
+		fs_info->update_uuid_tree_gen = 1;
 	complete_all(&fs_info->uuid_tree_rescan_completion);
 	return 0;
 }
 
+/*
+ * Callback for btrfs_uuid_tree_iterate().
+ * returns:
+ * 0	check succeeded, the entry is not outdated.
+ * < 0	if an error occured.
+ * > 0	if the check failed, which means the caller shall remove the entry.
+ */
+static int btrfs_check_uuid_tree_entry(struct btrfs_fs_info *fs_info,
+				       u8 *uuid, u16 type, u64 subid)
+{
+	struct btrfs_key key;
+	int ret = 0;
+	struct btrfs_root *subvol_root;
+
+	if (type != BTRFS_UUID_ITEM_TYPE_SUBVOL &&
+	    type != BTRFS_UUID_ITEM_TYPE_RECEIVED_SUBVOL)
+		goto out;
+
+	key.objectid = subid;
+	key.type = BTRFS_ROOT_ITEM_KEY;
+	key.offset = (u64)-1;
+	subvol_root = btrfs_read_fs_root_no_name(fs_info, &key);
+	if (IS_ERR(subvol_root)) {
+		ret = PTR_ERR(subvol_root);
+		if (ret == -ENOENT)
+			ret = 1;
+		goto out;
+	}
+
+	switch (type) {
+	case BTRFS_UUID_ITEM_TYPE_SUBVOL:
+		if (memcmp(uuid, subvol_root->root_item.uuid, BTRFS_UUID_SIZE))
+			ret = 1;
+		break;
+	case BTRFS_UUID_ITEM_TYPE_RECEIVED_SUBVOL:
+		if (memcmp(uuid, subvol_root->root_item.received_uuid,
+			   BTRFS_UUID_SIZE))
+			ret = 1;
+		break;
+	}
+
+out:
+	return ret;
+}
+
+static int btrfs_uuid_rescan_kthread(void *data)
+{
+	struct btrfs_fs_info *fs_info = (struct btrfs_fs_info *)data;
+	int ret;
+
+	/*
+	 * 1st step is to iterate through the existing UUID tree and
+	 * to delete all entries that contain outdated data.
+	 * 2nd step is to add all missing entries to the UUID tree.
+	 */
+	ret = btrfs_uuid_tree_iterate(fs_info, btrfs_check_uuid_tree_entry);
+	if (ret < 0) {
+		pr_warn("btrfs: iterating uuid_tree failed %d\n", ret);
+		complete_all(&fs_info->uuid_tree_rescan_completion);
+		return ret;
+	}
+	return btrfs_uuid_scan_kthread(data);
+}
+
 int btrfs_create_uuid_tree(struct btrfs_fs_info *fs_info)
 {
 	struct btrfs_trans_handle *trans;
@@ -3575,6 +3641,7 @@ int btrfs_create_uuid_tree(struct btrfs_fs_info *fs_info)
 
 	task = kthread_run(btrfs_uuid_scan_kthread, fs_info, "btrfs-uuid");
 	if (IS_ERR(task)) {
+		/* fs_info->update_uuid_tree_gen remains 0 in all error case */
 		pr_warn("btrfs: failed to start uuid_scan task\n");
 		complete_all(&fs_info->uuid_tree_rescan_completion);
 		return PTR_ERR(task);
@@ -3583,6 +3650,21 @@ int btrfs_create_uuid_tree(struct btrfs_fs_info *fs_info)
 	return 0;
 }
 
+int btrfs_check_uuid_tree(struct btrfs_fs_info *fs_info)
+{
+	struct task_struct *task;
+
+	task = kthread_run(btrfs_uuid_rescan_kthread, fs_info,
"btrfs-uuid");
+	if (IS_ERR(task)) {
+		/* fs_info->update_uuid_tree_gen remains 0 in all error case */
+		pr_warn("btrfs: failed to start uuid_rescan task\n");
+		complete_all(&fs_info->uuid_tree_rescan_completion);
+		return PTR_ERR(task);
+	}
+
+	return 0;
+}
+
 /*
  * shrinking a device means finding all of the device extents past
  * the new size, and then following the back refs to the chunks.
diff --git a/fs/btrfs/volumes.h b/fs/btrfs/volumes.h
index c3fcd60..3a6a0fd 100644
--- a/fs/btrfs/volumes.h
+++ b/fs/btrfs/volumes.h
@@ -316,6 +316,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);
-- 
1.8.3

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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 <sbehrens@giantdisaster.de>
---
 fs/btrfs/ctree.h   | 1 +
 fs/btrfs/disk-io.c | 3 ++-
 fs/btrfs/super.c   | 8 +++++++-
 3 files changed, 10 insertions(+), 2 deletions(-)

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 817894d..ea1adf6 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -1986,6 +1986,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)
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 7508b3a..e76554b 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -2919,7 +2919,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) {
diff --git a/fs/btrfs/super.c b/fs/btrfs/super.c
index 8eb6191..191f281 100644
--- a/fs/btrfs/super.c
+++ b/fs/btrfs/super.c
@@ -320,7 +320,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,
 };
 
@@ -360,6 +360,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},
 };
@@ -554,6 +555,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);
@@ -928,6 +932,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))
-- 
1.8.3

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

> +/* for items that use the BTRFS_UUID_KEY */
> +#define BTRFS_UUID_ITEM_TYPE_SUBVOL	0 /* for UUIDs assigned to subvols */
> +#define BTRFS_UUID_ITEM_TYPE_RECEIVED_SUBVOL	1 /* for UUIDs assigned to
> +						   * received subvols */
> +
> +/* a sequence of such items is stored under the BTRFS_UUID_KEY */
> +struct btrfs_uuid_item {
> +	__le16 type;	/* refer to BTRFS_UUID_ITEM_TYPE* defines above */
> +	__le32 len;	/* number of following 64bit values */
> +	__le64 subid[0];	/* sequence of subids */
> +} __attribute__ ((__packed__));
> +
[...]
>  /*
> + * Stores items that allow to quickly map UUIDs to something else.
> + * These items are part of the filesystem UUID tree.
> + * The key is built like this:
> + * (UUID_upper_64_bits, BTRFS_UUID_KEY, UUID_lower_64_bits).
> + */
> +#if BTRFS_UUID_SIZE != 16
> +#error "UUID items require BTRFS_UUID_SIZE == 16!"
> +#endif
> +#define BTRFS_UUID_KEY	251
Why do we need this btrfs_uuid_item structure?  Why not set the key type
to either _SUBVOL or _RECEIVED_SUBVOL instead of embedding structs with
those types under items with the constant BTRFS_UUID_KEY.  Then use the
item size to determine the number of u64 subids.  Then the item has a
simple array of u64s in the data which will be a lot easier to work
with.
> +/* btrfs_uuid_item */
> +BTRFS_SETGET_FUNCS(uuid_type, struct btrfs_uuid_item, type, 16);
> +BTRFS_SETGET_FUNCS(uuid_len, struct btrfs_uuid_item, len, 32);
> +BTRFS_SETGET_STACK_FUNCS(stack_uuid_type, struct btrfs_uuid_item, type,
16);
> +BTRFS_SETGET_STACK_FUNCS(stack_uuid_len, struct btrfs_uuid_item, len, 32);
This would all go away.
> +/*
> + * One key is used to store a sequence of btrfs_uuid_item items.
> + * Each item in the sequence contains a type information and a sequence of
> + * ids (together with the information about the size of the sequence of
ids).
> + * {[btrfs_uuid_item type0 {id0, id1, ..., idN}],
> + *  ...,
> + *  [btrfs_uuid_item typeZ {id0, id1, ..., idN}]}
> + *
> + * It is forbidden to put multiple items with the same type under the same
key.
> + * Instead the sequence of ids is extended and used to store any
additional
> + * ids for the same item type.
This constraint, and the cost of ensuring it and repairing violations,
would go away.
> +static struct btrfs_uuid_item *btrfs_match_uuid_item_type(
> +		struct btrfs_path *path, u16 type)
> +{
> +	struct extent_buffer *eb;
> +	int slot;
> +	struct btrfs_uuid_item *ptr;
> +	u32 item_size;
> +
> +	eb = path->nodes[0];
> +	slot = path->slots[0];
> +	ptr = btrfs_item_ptr(eb, slot, struct btrfs_uuid_item);
> +	item_size = btrfs_item_size_nr(eb, slot);
> +	do {
> +		u16 sub_item_type;
> +		u64 sub_item_len;
> +
> +		if (item_size < sizeof(*ptr)) {
> +			pr_warn("btrfs: uuid item too short (%lu < %d)!\n",
> +				(unsigned long)item_size, (int)sizeof(*ptr));
> +			return NULL;
> +		}
> +		item_size -= sizeof(*ptr);
> +		sub_item_type = btrfs_uuid_type(eb, ptr);
> +		sub_item_len = btrfs_uuid_len(eb, ptr);
> +		if (sub_item_len * sizeof(u64) > item_size) {
> +			pr_warn("btrfs: uuid item too short (%llu > %lu)!\n",
> +				(unsigned long long)(sub_item_len *
> +						     sizeof(u64)),
> +				(unsigned long)item_size);
> +			return NULL;
> +		}
> +		if (sub_item_type == type)
> +			return ptr;
> +		item_size -= sub_item_len * sizeof(u64);
> +		ptr = 1 + (struct btrfs_uuid_item *)
> +			(((char *)ptr) + (sub_item_len * sizeof(u64)));
> +	} while (item_size);
>
> +static int btrfs_uuid_tree_lookup_prepare(struct btrfs_root *uuid_root,
> +					  u8 *uuid, u16 type,
> +					  struct btrfs_path *path,
> +					  struct btrfs_uuid_item **ptr)
> +{
> +	int ret;
> +	struct btrfs_key key;
> +
> +	if (!uuid_root) {
> +		WARN_ON_ONCE(1);
> +		ret = -ENOENT;
> +		goto out;
> +	}
> +
> +	btrfs_uuid_to_key(uuid, &key);
> +
> +	ret = btrfs_search_slot(NULL, uuid_root, &key, path, 0, 0);
> +	if (ret < 0)
> +		goto out;
> +	if (ret > 0) {
> +		ret = -ENOENT;
> +		goto out;
> +	}
> +
> +	*ptr = btrfs_match_uuid_item_type(path, type);
> +	if (!*ptr) {
> +		ret = -ENOENT;
> +		goto out;
> +	}
> +
> +	ret = 0;
> +
> +out:
> +	return ret;
> +}
All of this is replaced with the simple search_slot in the caller.
> +	offset = (unsigned long)ptr;
> +	while (sub_item_len > 0) {
> +		u64 data;
> +
> +		read_extent_buffer(eb, &data, offset, sizeof(data));
> +		data = le64_to_cpu(data);
> +		if (data == subid) {
> +			ret = 0;
> +			break;
> +		}
> +		offset += sizeof(data);
> +		sub_item_len--;
> +	}
This could be cleaned up a bit by comparing an on-stack little-endian
input subid with each little-endian subid in the item with
memcmp_extent_buffer().
> +	ret = btrfs_insert_empty_item(trans, uuid_root, path, &key,
> +				      sizeof(*ptr) + sizeof(subid));
> +	if (ret == -EEXIST) {
> +		ptr = btrfs_match_uuid_item_type(path, type);
> +		if (ptr) {
[...]
> +			btrfs_extend_item(uuid_root, path, sizeof(subid));
How does this extension avoid the BUG when the leaf containing the item
doesn''t have room for the new subid?

- z
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

> +	key.objectid = 0;
> +	key.type = BTRFS_UUID_KEY;
> +	key.offset = 0;
> +
> +	max_key.objectid = (u64)-1;
> +	max_key.type = BTRFS_UUID_KEY;
> +	max_key.offset = (u64)-1;
> +		if (key.offset < (u64)-1) {
> +			key.offset++;
> +		} else if (key.type < BTRFS_UUID_KEY) {
> +			key.offset = 0;
> +			key.type = BTRFS_UUID_KEY;
> +		} else if (key.objectid < (u64)-1) {
> +			key.offset = 0;
> +			key.type = 0;
> +			key.objectid++;
> +		} else {
> +			break;
> +		}
> +	}
Presumably all of this isn''t needed now that the uuid items are in
their
own tree?  Just iterate over all the items in the tree?

- z
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

On Thu, 20 Jun 2013 12:47:04 -0700, Zach Brown wrote:
> 
>> +/* for items that use the BTRFS_UUID_KEY */
>> +#define BTRFS_UUID_ITEM_TYPE_SUBVOL	0 /* for UUIDs assigned to subvols
*/
>> +#define BTRFS_UUID_ITEM_TYPE_RECEIVED_SUBVOL	1 /* for UUIDs assigned
to
>> +						   * received subvols */
>> +
>> +/* a sequence of such items is stored under the BTRFS_UUID_KEY */
>> +struct btrfs_uuid_item {
>> +	__le16 type;	/* refer to BTRFS_UUID_ITEM_TYPE* defines above */
>> +	__le32 len;	/* number of following 64bit values */
>> +	__le64 subid[0];	/* sequence of subids */
>> +} __attribute__ ((__packed__));
>> +
> 
> [...]
> 
>>  /*
>> + * Stores items that allow to quickly map UUIDs to something else.
>> + * These items are part of the filesystem UUID tree.
>> + * The key is built like this:
>> + * (UUID_upper_64_bits, BTRFS_UUID_KEY, UUID_lower_64_bits).
>> + */
>> +#if BTRFS_UUID_SIZE != 16
>> +#error "UUID items require BTRFS_UUID_SIZE == 16!"
>> +#endif
>> +#define BTRFS_UUID_KEY	251
> 
> Why do we need this btrfs_uuid_item structure?  Why not set the key type
> to either _SUBVOL or _RECEIVED_SUBVOL instead of embedding structs with
> those types under items with the constant BTRFS_UUID_KEY.  Then use the
> item size to determine the number of u64 subids.  Then the item has a
> simple array of u64s in the data which will be a lot easier to work
> with.
Maintaining a 16 bit uuid_type field inside the item is done in order to
avoid wasting type values for the key. The type field in the key has a
width of 8 bits, so far 34 type values are defined in ctree.h.

As long as such items are in separated trees, their type value could be
reused in the future when the 8 bit type field is exhausted.

There was some discussion in #btrfs about this topic on 2013-04-26.
There are pros and cons. The uuid_type field in the item allows to use
the uuid items generically outside of the uuid tree since it occupies
only one type value in the 8 bit type field. On the other hand, if the 8
bit type field in the key is exhausted, it saves lines of codes and
avoids complexity to implement a common way to expand this field instead
of implementing multiplexing layers at multiple places, although maybe
with some added performance penalty.

Anybody else with an opinion for this topic?

>> +/* btrfs_uuid_item */
>> +BTRFS_SETGET_FUNCS(uuid_type, struct btrfs_uuid_item, type, 16);
>> +BTRFS_SETGET_FUNCS(uuid_len, struct btrfs_uuid_item, len, 32);
>> +BTRFS_SETGET_STACK_FUNCS(stack_uuid_type, struct btrfs_uuid_item,
type, 16);
>> +BTRFS_SETGET_STACK_FUNCS(stack_uuid_len, struct btrfs_uuid_item, len,
32);
> 
> This would all go away.
> 
>> +/*
>> + * One key is used to store a sequence of btrfs_uuid_item items.
>> + * Each item in the sequence contains a type information and a
sequence of
>> + * ids (together with the information about the size of the sequence
of ids).
>> + * {[btrfs_uuid_item type0 {id0, id1, ..., idN}],
>> + *  ...,
>> + *  [btrfs_uuid_item typeZ {id0, id1, ..., idN}]}
>> + *
>> + * It is forbidden to put multiple items with the same type under the
same key.
>> + * Instead the sequence of ids is extended and used to store any
additional
>> + * ids for the same item type.
> 
> This constraint, and the cost of ensuring it and repairing violations,
> would go away.
> 
>> +static struct btrfs_uuid_item *btrfs_match_uuid_item_type(
>> +		struct btrfs_path *path, u16 type)
>> +{
>> +	struct extent_buffer *eb;
>> +	int slot;
>> +	struct btrfs_uuid_item *ptr;
>> +	u32 item_size;
>> +
>> +	eb = path->nodes[0];
>> +	slot = path->slots[0];
>> +	ptr = btrfs_item_ptr(eb, slot, struct btrfs_uuid_item);
>> +	item_size = btrfs_item_size_nr(eb, slot);
>> +	do {
>> +		u16 sub_item_type;
>> +		u64 sub_item_len;
>> +
>> +		if (item_size < sizeof(*ptr)) {
>> +			pr_warn("btrfs: uuid item too short (%lu < %d)!\n",
>> +				(unsigned long)item_size, (int)sizeof(*ptr));
>> +			return NULL;
>> +		}
>> +		item_size -= sizeof(*ptr);
>> +		sub_item_type = btrfs_uuid_type(eb, ptr);
>> +		sub_item_len = btrfs_uuid_len(eb, ptr);
>> +		if (sub_item_len * sizeof(u64) > item_size) {
>> +			pr_warn("btrfs: uuid item too short (%llu > %lu)!\n",
>> +				(unsigned long long)(sub_item_len *
>> +						     sizeof(u64)),
>> +				(unsigned long)item_size);
>> +			return NULL;
>> +		}
>> +		if (sub_item_type == type)
>> +			return ptr;
>> +		item_size -= sub_item_len * sizeof(u64);
>> +		ptr = 1 + (struct btrfs_uuid_item *)
>> +			(((char *)ptr) + (sub_item_len * sizeof(u64)));
>> +	} while (item_size);
>>
>> +static int btrfs_uuid_tree_lookup_prepare(struct btrfs_root
*uuid_root,
>> +					  u8 *uuid, u16 type,
>> +					  struct btrfs_path *path,
>> +					  struct btrfs_uuid_item **ptr)
>> +{
>> +	int ret;
>> +	struct btrfs_key key;
>> +
>> +	if (!uuid_root) {
>> +		WARN_ON_ONCE(1);
>> +		ret = -ENOENT;
>> +		goto out;
>> +	}
>> +
>> +	btrfs_uuid_to_key(uuid, &key);
>> +
>> +	ret = btrfs_search_slot(NULL, uuid_root, &key, path, 0, 0);
>> +	if (ret < 0)
>> +		goto out;
>> +	if (ret > 0) {
>> +		ret = -ENOENT;
>> +		goto out;
>> +	}
>> +
>> +	*ptr = btrfs_match_uuid_item_type(path, type);
>> +	if (!*ptr) {
>> +		ret = -ENOENT;
>> +		goto out;
>> +	}
>> +
>> +	ret = 0;
>> +
>> +out:
>> +	return ret;
>> +}
> 
> All of this is replaced with the simple search_slot in the caller.
> 
>> +	offset = (unsigned long)ptr;
>> +	while (sub_item_len > 0) {
>> +		u64 data;
>> +
>> +		read_extent_buffer(eb, &data, offset, sizeof(data));
>> +		data = le64_to_cpu(data);
>> +		if (data == subid) {
>> +			ret = 0;
>> +			break;
>> +		}
>> +		offset += sizeof(data);
>> +		sub_item_len--;
>> +	}
> 
> This could be cleaned up a bit by comparing an on-stack little-endian
> input subid with each little-endian subid in the item with
> memcmp_extent_buffer().
This would save some CPU cycles for the repeated le64_to_cpu() and for
the memcpy(). The number of lines of code is equal for both ways. The
read_extent_buffer() way is more straight forward and readable IMO.

>> +	ret = btrfs_insert_empty_item(trans, uuid_root, path, &key,
>> +				      sizeof(*ptr) + sizeof(subid));
>> +	if (ret == -EEXIST) {
>> +		ptr = btrfs_match_uuid_item_type(path, type);
>> +		if (ptr) {
> [...]
>> +			btrfs_extend_item(uuid_root, path, sizeof(subid));
> 
> How does this extension avoid the BUG when the leaf containing the item
> doesn''t have room for the new subid?
btrfs_extend_item() does not BUG() when you have called
btrfs_search_slot() before with ins_len > 0.

btrfs_search_slot() calls split_leaf(), and split_leaf() checks whether
the requested additional data will fit, and return EOVERFLOW if this is
not the case.

The call chain is:
btrfs_insert_empty_item() -> btrfs_search_slot() -> split_leaf()

Thanks for your review comments.

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

> > Why do we need this btrfs_uuid_item structure?  Why not set the key
type
> > to either _SUBVOL or _RECEIVED_SUBVOL instead of embedding structs
with
> > those types under items with the constant BTRFS_UUID_KEY.  Then use
the
> > item size to determine the number of u64 subids.  Then the item has a
> > simple array of u64s in the data which will be a lot easier to work
> > with.
> 
> Maintaining a 16 bit uuid_type field inside the item is done in order to
> avoid wasting type values for the key. The type field in the key has a
> width of 8 bits, so far 34 type values are defined in ctree.h.
> 
> As long as such items are in separated trees, their type value could be
> reused in the future when the 8 bit type field is exhausted.
> 
> There was some discussion in #btrfs about this topic on 2013-04-26.
> There are pros and cons. The uuid_type field in the item allows to use
> the uuid items generically outside of the uuid tree since it occupies
> only one type value in the 8 bit type field. On the other hand, if the 8
> bit type field in the key is exhausted, it saves lines of codes and
> avoids complexity to implement a common way to expand this field instead
> of implementing multiplexing layers at multiple places, although maybe
> with some added performance penalty.
> 
> Anybody else with an opinion for this topic?
Perhaps obviously, I''m strongly in favour of not rolling another layer
of indirection inside the items, especially when the code to implement
it is full of fragile pointer math.
> >> +	offset = (unsigned long)ptr;
> >> +	while (sub_item_len > 0) {
> >> +		u64 data;
> >> +
> >> +		read_extent_buffer(eb, &data, offset, sizeof(data));
> >> +		data = le64_to_cpu(data);
> >> +		if (data == subid) {
> >> +			ret = 0;
> >> +			break;
> >> +		}
> >> +		offset += sizeof(data);
> >> +		sub_item_len--;
> >> +	}
> > 
> > This could be cleaned up a bit by comparing an on-stack little-endian
> > input subid with each little-endian subid in the item with
> > memcmp_extent_buffer().
> 
> This would save some CPU cycles for the repeated le64_to_cpu() and for
> the memcpy(). The number of lines of code is equal for both ways.
Hmm?  It would be many fewer lines of code.
> read_extent_buffer() way is more straight forward and readable IMO.
> > How does this extension avoid the BUG when the leaf containing the
item
> > doesn''t have room for the new subid?
> 
> btrfs_extend_item() does not BUG() when you have called
> btrfs_search_slot() before with ins_len > 0.
Ah, got it.  Thanks.

- z
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Quoting Stefan Behrens (2013-06-21 04:47:20)
> On Thu, 20 Jun 2013 12:47:04 -0700, Zach Brown wrote:
> > 
> >> +/* for items that use the BTRFS_UUID_KEY */
> >> +#define BTRFS_UUID_ITEM_TYPE_SUBVOL 0 /* for UUIDs assigned to
subvols */
> >> +#define BTRFS_UUID_ITEM_TYPE_RECEIVED_SUBVOL        1 /* for
UUIDs assigned to
> >> +                                               * received subvols
*/
> >> +
> >> +/* a sequence of such items is stored under the BTRFS_UUID_KEY */
> >> +struct btrfs_uuid_item {
> >> +    __le16 type;    /* refer to BTRFS_UUID_ITEM_TYPE* defines
above */
> >> +    __le32 len;     /* number of following 64bit values */
> >> +    __le64 subid[0];        /* sequence of subids */
> >> +} __attribute__ ((__packed__));
> >> +
> > 
> > [...]
> > 
> >>  /*
> >> + * Stores items that allow to quickly map UUIDs to something
else.
> >> + * These items are part of the filesystem UUID tree.
> >> + * The key is built like this:
> >> + * (UUID_upper_64_bits, BTRFS_UUID_KEY, UUID_lower_64_bits).
> >> + */
> >> +#if BTRFS_UUID_SIZE != 16
> >> +#error "UUID items require BTRFS_UUID_SIZE == 16!"
> >> +#endif
> >> +#define BTRFS_UUID_KEY      251
> > 
> > Why do we need this btrfs_uuid_item structure?  Why not set the key
type
> > to either _SUBVOL or _RECEIVED_SUBVOL instead of embedding structs
with
> > those types under items with the constant BTRFS_UUID_KEY.  Then use
the
> > item size to determine the number of u64 subids.  Then the item has a
> > simple array of u64s in the data which will be a lot easier to work
> > with.
> 
> Maintaining a 16 bit uuid_type field inside the item is done in order to
> avoid wasting type values for the key. The type field in the key has a
> width of 8 bits, so far 34 type values are defined in ctree.h.
> 
> As long as such items are in separated trees, their type value could be
> reused in the future when the 8 bit type field is exhausted.
> 
> There was some discussion in #btrfs about this topic on 2013-04-26.
> There are pros and cons. The uuid_type field in the item allows to use
> the uuid items generically outside of the uuid tree since it occupies
> only one type value in the 8 bit type field. On the other hand, if the 8
> bit type field in the key is exhausted, it saves lines of codes and
> avoids complexity to implement a common way to expand this field instead
> of implementing multiplexing layers at multiple places, although maybe
> with some added performance penalty.
> 
> Anybody else with an opinion for this topic?
I''ve been thinking about this, and while I clearly did not have this
use
of uuids in mind originally, they have become a key part of the FS.  They
deserve their own bits in the type field.

I know this is not an easy thing to redo, but long term it really looks
worth it to me.

-chris
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

On Fri, 21 Jun 2013 09:11:38 -0700, Zach Brown wrote:
>>>> +	offset = (unsigned long)ptr;
>>>> +	while (sub_item_len > 0) {
>>>> +		u64 data;
>>>> +
>>>> +		read_extent_buffer(eb, &data, offset, sizeof(data));
>>>> +		data = le64_to_cpu(data);
>>>> +		if (data == subid) {
>>>> +			ret = 0;
>>>> +			break;
>>>> +		}
>>>> +		offset += sizeof(data);
>>>> +		sub_item_len--;
>>>> +	}
>>>
>>> This could be cleaned up a bit by comparing an on-stack
little-endian
>>> input subid with each little-endian subid in the item with
>>> memcmp_extent_buffer().
>>
>> This would save some CPU cycles for the repeated le64_to_cpu() and for
>> the memcpy(). The number of lines of code is equal for both ways.
> 
> Hmm?  It would be many fewer lines of code.
Are you thinking of something shorter than the following?

offset = (unsigned long)ptr;
subid = cpu_to_le64(subid);
while (sub_item_len > 0) {
	if (memcmp_extent_buffer(eb, &subid, offset,
				 sizeof(subid)) == 0) {
		ret = 0;
		break;
	}
	offset += sizeof(subid);
	sub_item_len--;
}

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

> >> This would save some CPU cycles for the repeated le64_to_cpu() and
for
> >> the memcpy(). The number of lines of code is equal for both ways.
> > 
> > Hmm?  It would be many fewer lines of code.
> 
> Are you thinking of something shorter than the following?
That''s better, yeah, but there''s still some room left to go. 
Almost all
of the remaining code is boiler-plate iteration that could be done with
a for(;;).

This could be a mini OCC contest! :)
> offset = (unsigned long)ptr;
> subid = cpu_to_le64(subid);
> while (sub_item_len > 0) {
> 	if (memcmp_extent_buffer(eb, &subid, offset,
> 				 sizeof(subid)) == 0) {
> 		ret = 0;
> 		break;
> 	}
> 	offset += sizeof(subid);
> 	sub_item_len--;
> }
roughly:

unsigned long end = offset + sub_item_len;

for (ret = 1; offset < end && ret; offset += sizeof(subid))
	ret = !!memcmp_extent_buffer(eb, &subid, offset,
				     sizeof(subid));

- z
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html