Skip to contentSkip to conversation

Btrfs: free space B-tree

PATCH Superseded Omar Sandoval 4 participants 18 messages Sep 14, 2015 – Sep 15, 2015

Subsystems (3)

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

v3 cover Btrfs: free space B-tree

Hi, everyone,

I went back and fixed the issues that came up since v2. Changes below. I removed Josef's Reviewed-by on patch 9 because it was completely rewritten to change the mount options like Dave suggested. These are still based on 4.2

Thanks!

Changes from v2->v3:

- Fixed a warning in the free space tree sanity tests caught by Zhao Lei.
- Moved the addition of a block group to the free space tree to occur either on the first attempt to modify the free space for the block group or in btrfs_create_pending_block_groups(), whichever happens first. This avoids a deadlock (lock recursion) when modifying the free space tree requires allocating a new block group. In order to do this, it was simpler to change the on-disk semantics: the superblock stripes will now appear to be free space according to the free space tree, but load_free_space_tree() will still exclude them when building the in-memory free space cache.
- Changed the free_space_tree option to space_cache=v2 and made clear_cache clear the free space tree. If the free space tree has been created, the mount will fail unless space_cache=v2 or nospace_cache,clear_cache is given because we cannot allow the free space tree to get out of date.
- Did a once-over of the code and caught a couple of error handling typos.

v2: http://www.spinics.net/lists/linux-btrfs/msg46796.html

Changes from v1->v2:

- Cleaned up a bunch of unnecessary instances of "if (ret) goto out; ret = 0"
- Added aborts in the free space tree code closer to the site the error is
encountered: where we add or remove block groups, add or remove free space, and also when we convert formats
- Moved loading of the free space tree into caching_thread() and added a new patch 3 in preparation for it
- Commented a bunch of stuff in the extent buffer bitmap operations and refactored some of the complicated logic

v1: http://www.spinics.net/lists/linux-btrfs/msg46713.html

Omar Sandoval (9):
Btrfs: add extent buffer bitmap operations
Btrfs: add extent buffer bitmap sanity tests
Btrfs: add helpers for read-only compat bits
Btrfs: refactor caching_thread()
Btrfs: introduce the free space B-tree on-disk format
Btrfs: implement the free space B-tree
Btrfs: add free space tree sanity tests
Btrfs: wire up the free space tree to the extent tree
Btrfs: add free space tree mount option

 fs/btrfs/Makefile                      |    5 +-
 fs/btrfs/ctree.h                       |  157 +++-
 fs/btrfs/disk-io.c                     |   38 +
 fs/btrfs/extent-tree.c                 |   98 +-
 fs/btrfs/extent_io.c                   |  183 +++-
 fs/btrfs/extent_io.h                   |   10 +-
 fs/btrfs/free-space-tree.c             | 1581 ++++++++++++++++++++++++++++++++
 fs/btrfs/free-space-tree.h             |   72 ++
 fs/btrfs/super.c                       |   56 +-
 fs/btrfs/tests/btrfs-tests.c           |   52 ++
 fs/btrfs/tests/btrfs-tests.h           |   10 +
 fs/btrfs/tests/extent-io-tests.c       |  138 ++-
 fs/btrfs/tests/free-space-tests.c      |   35 +-
 fs/btrfs/tests/free-space-tree-tests.c |  571 ++++++++++++
 fs/btrfs/tests/qgroup-tests.c          |   20 +-
 include/trace/events/btrfs.h           |    3 +-
 16 files changed, 2922 insertions(+), 107 deletions(-)
 create mode 100644 fs/btrfs/free-space-tree.c
 create mode 100644 fs/btrfs/free-space-tree.h
 create mode 100644 fs/btrfs/tests/free-space-tree-tests.c
Signature · 1 line
2.5.2
#1 lore raw

PATCH v3 1/9 Btrfs: add extent buffer bitmap operations

From: Omar Sandoval <[email protected]>

These are going to be used for the free space tree bitmap items.

---
 fs/btrfs/extent_io.c | 149 +++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/extent_io.h |   6 +++
 2 files changed, 155 insertions(+)
fs/btrfs/extent_io.c +149 -0
index 02d05817cbdf..eae9175ff62b 100644
@@ -5475,6 +5475,155 @@ void copy_extent_buffer(struct extent_buffer *dst, struct extent_buffer *src,
 	}
 }
 
+/*
+ * The extent buffer bitmap operations are done with byte granularity because
+ * bitmap items are not guaranteed to be aligned to a word and therefore a
+ * single word in a bitmap may straddle two pages in the extent buffer.
+ */
+#define BIT_BYTE(nr) ((nr) / BITS_PER_BYTE)
+#define BYTE_MASK ((1 << BITS_PER_BYTE) - 1)
+#define BITMAP_FIRST_BYTE_MASK(start) \
+	((BYTE_MASK << ((start) & (BITS_PER_BYTE - 1))) & BYTE_MASK)
+#define BITMAP_LAST_BYTE_MASK(nbits) \
+	(BYTE_MASK >> (-(nbits) & (BITS_PER_BYTE - 1)))
+
+/*
+ * eb_bitmap_offset() - calculate the page and offset of the byte containing the
+ * given bit number
+ * @eb: the extent buffer
+ * @start: offset of the bitmap item in the extent buffer
+ * @nr: bit number
+ * @page_index: return index of the page in the extent buffer that contains the
+ * given bit number
+ * @page_offset: return offset into the page given by page_index
+ *
+ * This helper hides the ugliness of finding the byte in an extent buffer which
+ * contains a given bit.
+ */
+static inline void eb_bitmap_offset(struct extent_buffer *eb,
+				    unsigned long start, unsigned long nr,
+				    unsigned long *page_index,
+				    size_t *page_offset)
+{
+	size_t start_offset = eb->start & ((u64)PAGE_CACHE_SIZE - 1);
+	size_t byte_offset = BIT_BYTE(nr);
+	size_t offset;
+
+	/*
+	 * The byte we want is the offset of the extent buffer + the offset of
+	 * the bitmap item in the extent buffer + the offset of the byte in the
+	 * bitmap item.
+	 */
+	offset = start_offset + start + byte_offset;
+
+	*page_index = offset >> PAGE_CACHE_SHIFT;
+	*page_offset = offset & (PAGE_CACHE_SIZE - 1);
+}
+
+/**
+ * extent_buffer_test_bit - determine whether a bit in a bitmap item is set
+ * @eb: the extent buffer
+ * @start: offset of the bitmap item in the extent buffer
+ * @nr: bit number to test
+ */
+int extent_buffer_test_bit(struct extent_buffer *eb, unsigned long start,
+			   unsigned long nr)
+{
+	char *kaddr;
+	struct page *page;
+	unsigned long i;
+	size_t offset;
+
+	eb_bitmap_offset(eb, start, nr, &i, &offset);
+	page = eb->pages[i];
+	WARN_ON(!PageUptodate(page));
+	kaddr = page_address(page);
+	return 1U & (kaddr[offset] >> (nr & (BITS_PER_BYTE - 1)));
+}
+
+/**
+ * extent_buffer_bitmap_set - set an area of a bitmap
+ * @eb: the extent buffer
+ * @start: offset of the bitmap item in the extent buffer
+ * @pos: bit number of the first bit
+ * @len: number of bits to set
+ */
+void extent_buffer_bitmap_set(struct extent_buffer *eb, unsigned long start,
+			      unsigned long pos, unsigned long len)
+{
+	char *kaddr;
+	struct page *page;
+	unsigned long i;
+	size_t offset;
+	const unsigned int size = pos + len;
+	int bits_to_set = BITS_PER_BYTE - (pos % BITS_PER_BYTE);
+	unsigned int mask_to_set = BITMAP_FIRST_BYTE_MASK(pos);
+
+	eb_bitmap_offset(eb, start, pos, &i, &offset);
+	page = eb->pages[i];
+	WARN_ON(!PageUptodate(page));
+	kaddr = page_address(page);
+
+	while (len >= bits_to_set) {
+		kaddr[offset] |= mask_to_set;
+		len -= bits_to_set;
+		bits_to_set = BITS_PER_BYTE;
+		mask_to_set = ~0U;
+		if (++offset >= PAGE_CACHE_SIZE && len > 0) {
+			offset = 0;
+			page = eb->pages[++i];
+			WARN_ON(!PageUptodate(page));
+			kaddr = page_address(page);
+		}
+	}
+	if (len) {
+		mask_to_set &= BITMAP_LAST_BYTE_MASK(size);
+		kaddr[offset] |= mask_to_set;
+	}
+}
+
+
+/**
+ * extent_buffer_bitmap_clear - clear an area of a bitmap
+ * @eb: the extent buffer
+ * @start: offset of the bitmap item in the extent buffer
+ * @pos: bit number of the first bit
+ * @len: number of bits to clear
+ */
+void extent_buffer_bitmap_clear(struct extent_buffer *eb, unsigned long start,
+				unsigned long pos, unsigned long len)
+{
+	char *kaddr;
+	struct page *page;
+	unsigned long i;
+	size_t offset;
+	const unsigned int size = pos + len;
+	int bits_to_clear = BITS_PER_BYTE - (pos % BITS_PER_BYTE);
+	unsigned int mask_to_clear = BITMAP_FIRST_BYTE_MASK(pos);
+
+	eb_bitmap_offset(eb, start, pos, &i, &offset);
+	page = eb->pages[i];
+	WARN_ON(!PageUptodate(page));
+	kaddr = page_address(page);
+
+	while (len >= bits_to_clear) {
+		kaddr[offset] &= ~mask_to_clear;
+		len -= bits_to_clear;
+		bits_to_clear = BITS_PER_BYTE;
+		mask_to_clear = ~0U;
+		if (++offset >= PAGE_CACHE_SIZE && len > 0) {
+			offset = 0;
+			page = eb->pages[++i];
+			WARN_ON(!PageUptodate(page));
+			kaddr = page_address(page);
+		}
+	}
+	if (len) {
+		mask_to_clear &= BITMAP_LAST_BYTE_MASK(size);
+		kaddr[offset] &= ~mask_to_clear;
+	}
+}
+
 static inline bool areas_overlap(unsigned long src, unsigned long dst, unsigned long len)
 {
 	unsigned long distance = (src > dst) ? src - dst : dst - src;
fs/btrfs/extent_io.h +6 -0
index c668f36898d3..9185a20081d7 100644
@@ -309,6 +309,12 @@ void memmove_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset,
 			   unsigned long src_offset, unsigned long len);
 void memset_extent_buffer(struct extent_buffer *eb, char c,
 			  unsigned long start, unsigned long len);
+int extent_buffer_test_bit(struct extent_buffer *eb, unsigned long start,
+			   unsigned long pos);
+void extent_buffer_bitmap_set(struct extent_buffer *eb, unsigned long start,
+			      unsigned long pos, unsigned long len);
+void extent_buffer_bitmap_clear(struct extent_buffer *eb, unsigned long start,
+				unsigned long pos, unsigned long len);
 void clear_extent_buffer_dirty(struct extent_buffer *eb);
 int set_extent_buffer_dirty(struct extent_buffer *eb);
 int set_extent_buffer_uptodate(struct extent_buffer *eb);
Signature · 1 line
2.5.2
#2 lore raw

PATCH v3 2/9 Btrfs: add extent buffer bitmap sanity tests

In reply to Omar Sandoval

From: Omar Sandoval <[email protected]>

Sanity test the extent buffer bitmap operations (test, set, and clear) against the equivalent standard kernel operations.

---
 fs/btrfs/extent_io.c             |  34 ++++++----
 fs/btrfs/extent_io.h             |   4 +-
 fs/btrfs/tests/extent-io-tests.c | 138 ++++++++++++++++++++++++++++++++++++++-
 3 files changed, 160 insertions(+), 16 deletions(-)
fs/btrfs/extent_io.c +21 -13
index eae9175ff62b..f875e29e10e1 100644
@@ -4678,24 +4678,14 @@ struct extent_buffer *btrfs_clone_extent_buffer(struct extent_buffer *src)
 	return new;
 }
 
-struct extent_buffer *alloc_dummy_extent_buffer(struct btrfs_fs_info *fs_info,
-						u64 start)
+struct extent_buffer *__alloc_dummy_extent_buffer(struct btrfs_fs_info *fs_info,
+						  u64 start, unsigned long len)
 {
 	struct extent_buffer *eb;
-	unsigned long len;
 	unsigned long num_pages;
 	unsigned long i;
 
-	if (!fs_info) {
-		/*
-		 * Called only from tests that don't always have a fs_info
-		 * available, but we know that nodesize is 4096
-		 */
-		len = 4096;
-	} else {
-		len = fs_info->tree_root->nodesize;
-	}
-	num_pages = num_extent_pages(0, len);
+	num_pages = num_extent_pages(start, len);
 
 	eb = __alloc_extent_buffer(fs_info, start, len);
 	if (!eb)
@@ -4718,6 +4708,24 @@ err:
 	return NULL;
 }
 
+struct extent_buffer *alloc_dummy_extent_buffer(struct btrfs_fs_info *fs_info,
+						u64 start)
+{
+	unsigned long len;
+
+	if (!fs_info) {
+		/*
+		 * Called only from tests that don't always have a fs_info
+		 * available, but we know that nodesize is 4096
+		 */
+		len = 4096;
+	} else {
+		len = fs_info->tree_root->nodesize;
+	}
+
+	return __alloc_dummy_extent_buffer(fs_info, start, len);
+}
+
 static void check_buffer_tree_ref(struct extent_buffer *eb)
 {
 	int refs;
fs/btrfs/extent_io.h +3 -1
index 9185a20081d7..9f8d7d1a7015 100644
@@ -263,8 +263,10 @@ void set_page_extent_mapped(struct page *page);
 
 struct extent_buffer *alloc_extent_buffer(struct btrfs_fs_info *fs_info,
 					  u64 start);
+struct extent_buffer *__alloc_dummy_extent_buffer(struct btrfs_fs_info *fs_info,
+						  u64 start, unsigned long len);
 struct extent_buffer *alloc_dummy_extent_buffer(struct btrfs_fs_info *fs_info,
-		u64 start);
+						u64 start);
 struct extent_buffer *btrfs_clone_extent_buffer(struct extent_buffer *src);
 struct extent_buffer *find_extent_buffer(struct btrfs_fs_info *fs_info,
 					 u64 start);
fs/btrfs/tests/extent-io-tests.c +136 -2

156 lines not on this page · raw message

Signature · 1 line
2.5.2
#3 lore raw

PATCH v3 3/9 Btrfs: add helpers for read-only compat bits

In reply to Omar Sandoval

From: Omar Sandoval <[email protected]>

We're finally going to add one of these for the free space tree, so let's add the same nice helpers that we have for the incompat bits. While we're add it, also add helpers to clear the bits.

---
 fs/btrfs/ctree.h | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 82 insertions(+)
fs/btrfs/ctree.h +82 -0
index aac314e14188..83d760378c3c 100644
@@ -4103,6 +4103,30 @@ static inline void __btrfs_set_fs_incompat(struct btrfs_fs_info *fs_info,
 	}
 }
 
+#define btrfs_clear_fs_incompat(__fs_info, opt) \
+	__btrfs_clear_fs_incompat((__fs_info), BTRFS_FEATURE_INCOMPAT_##opt)
+
+static inline void __btrfs_clear_fs_incompat(struct btrfs_fs_info *fs_info,
+					     u64 flag)
+{
+	struct btrfs_super_block *disk_super;
+	u64 features;
+
+	disk_super = fs_info->super_copy;
+	features = btrfs_super_incompat_flags(disk_super);
+	if (features & flag) {
+		spin_lock(&fs_info->super_lock);
+		features = btrfs_super_incompat_flags(disk_super);
+		if (features & flag) {
+			features &= ~flag;
+			btrfs_set_super_incompat_flags(disk_super, features);
+			btrfs_info(fs_info, "clearing %llu feature flag",
+					 flag);
+		}
+		spin_unlock(&fs_info->super_lock);
+	}
+}
+
 #define btrfs_fs_incompat(fs_info, opt) \
 	__btrfs_fs_incompat((fs_info), BTRFS_FEATURE_INCOMPAT_##opt)
 
@@ -4113,6 +4137,64 @@ static inline int __btrfs_fs_incompat(struct btrfs_fs_info *fs_info, u64 flag)
 	return !!(btrfs_super_incompat_flags(disk_super) & flag);
 }
 
+#define btrfs_set_fs_compat_ro(__fs_info, opt) \
+	__btrfs_set_fs_compat_ro((__fs_info), BTRFS_FEATURE_COMPAT_RO_##opt)
+
+static inline void __btrfs_set_fs_compat_ro(struct btrfs_fs_info *fs_info,
+					    u64 flag)
+{
+	struct btrfs_super_block *disk_super;
+	u64 features;
+
+	disk_super = fs_info->super_copy;
+	features = btrfs_super_compat_ro_flags(disk_super);
+	if (!(features & flag)) {
+		spin_lock(&fs_info->super_lock);
+		features = btrfs_super_compat_ro_flags(disk_super);
+		if (!(features & flag)) {
+			features |= flag;
+			btrfs_set_super_compat_ro_flags(disk_super, features);
+			btrfs_info(fs_info, "setting %llu ro feature flag",
+				   flag);
+		}
+		spin_unlock(&fs_info->super_lock);
+	}
+}
+
+#define btrfs_clear_fs_compat_ro(__fs_info, opt) \
+	__btrfs_clear_fs_compat_ro((__fs_info), BTRFS_FEATURE_COMPAT_RO_##opt)
+
+static inline void __btrfs_clear_fs_compat_ro(struct btrfs_fs_info *fs_info,
+					      u64 flag)
+{
+	struct btrfs_super_block *disk_super;
+	u64 features;
+
+	disk_super = fs_info->super_copy;
+	features = btrfs_super_compat_ro_flags(disk_super);
+	if (features & flag) {
+		spin_lock(&fs_info->super_lock);
+		features = btrfs_super_compat_ro_flags(disk_super);
+		if (features & flag) {
+			features &= ~flag;
+			btrfs_set_super_compat_ro_flags(disk_super, features);
+			btrfs_info(fs_info, "clearing %llu ro feature flag",
+				   flag);
+		}
+		spin_unlock(&fs_info->super_lock);
+	}
+}
+
+#define btrfs_fs_compat_ro(fs_info, opt) \
+	__btrfs_fs_compat_ro((fs_info), BTRFS_FEATURE_COMPAT_RO_##opt)
+
+static inline int __btrfs_fs_compat_ro(struct btrfs_fs_info *fs_info, u64 flag)
+{
+	struct btrfs_super_block *disk_super;
+	disk_super = fs_info->super_copy;
+	return !!(btrfs_super_compat_ro_flags(disk_super) & flag);
+}
+
 /*
  * Call btrfs_abort_transaction as early as possible when an error condition is
  * detected, that way the exact line number is reported.
Signature · 1 line
2.5.2
#4 lore raw

PATCH v3 4/9 Btrfs: refactor caching_thread()

In reply to Omar Sandoval

From: Omar Sandoval <[email protected]>

We're also going to load the free space tree from caching_thread(), so we should refactor some of the common code.

---
 fs/btrfs/ctree.h       |  3 +++
 fs/btrfs/extent-tree.c | 59 ++++++++++++++++++++++++++++----------------------
 2 files changed, 36 insertions(+), 26 deletions(-)
fs/btrfs/ctree.h +3 -0
index 83d760378c3c..7ad1bdb667db 100644
@@ -1262,6 +1262,9 @@ struct btrfs_caching_control {
 	atomic_t count;
 };
 
+/* Once caching_thread() finds this much free space, it will wake up waiters. */
+#define CACHING_CTL_WAKE_UP (1024 * 1024 * 2)
+
 struct btrfs_io_ctl {
 	void *cur, *orig;
 	struct page *page;
fs/btrfs/extent-tree.c +33 -26

119 lines not on this page · raw message

Signature · 1 line
2.5.2
#5 lore raw

PATCH v3 5/9 Btrfs: introduce the free space B-tree on-disk format

In reply to Omar Sandoval

From: Omar Sandoval <[email protected]>

The on-disk format for the free space tree is straightforward. Each block group is represented in the free space tree by a free space info item that stores accounting information: whether the free space for this block group is stored as bitmaps or extents and how many extents of free space exist for this block group (regardless of which format is being used in the tree). Extents are (start, FREE_SPACE_EXTENT, length) keys with no corresponding item, and bitmaps instead have the FREE_SPACE_BITMAP type and have a bitmap item attached, which is just an array of bytes.

---
 fs/btrfs/ctree.h             | 38 ++++++++++++++++++++++++++++++++++++++
 include/trace/events/btrfs.h |  3 ++-
 2 files changed, 40 insertions(+), 1 deletion(-)
fs/btrfs/ctree.h +38 -0
index 7ad1bdb667db..b166e5c26afe 100644
@@ -96,6 +96,9 @@ struct btrfs_ordered_sum;
 /* for storing items that use the BTRFS_UUID_KEY* types */
 #define BTRFS_UUID_TREE_OBJECTID 9ULL
 
+/* tracks free space in block groups. */
+#define BTRFS_FREE_SPACE_TREE_OBJECTID 10ULL
+
 /* for storing balance parameters in the root tree */
 #define BTRFS_BALANCE_OBJECTID -4ULL
 
@@ -500,6 +503,8 @@ struct btrfs_super_block {
  * Compat flags that we support.  If any incompat flags are set other than the
  * ones specified below then we will fail to mount
  */
+#define BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE	(1ULL << 0)
+
 #define BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF	(1ULL << 0)
 #define BTRFS_FEATURE_INCOMPAT_DEFAULT_SUBVOL	(1ULL << 1)
 #define BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS	(1ULL << 2)
@@ -1061,6 +1066,13 @@ struct btrfs_block_group_item {
 	__le64 flags;
 } __attribute__ ((__packed__));
 
+struct btrfs_free_space_info {
+	__le32 extent_count;
+	__le32 flags;
+} __attribute__ ((__packed__));
+
+#define BTRFS_FREE_SPACE_USING_BITMAPS (1ULL << 0)
+
 #define BTRFS_QGROUP_LEVEL_SHIFT		48
 static inline u64 btrfs_qgroup_level(u64 qgroupid)
 {
@@ -2064,6 +2076,27 @@ struct btrfs_ioctl_defrag_range_args {
  */
 #define BTRFS_BLOCK_GROUP_ITEM_KEY 192
 
+/*
+ * Every block group is represented in the free space tree by a free space info
+ * item, which stores some accounting information. It is keyed on
+ * (block_group_start, FREE_SPACE_INFO, block_group_length).
+ */
+#define BTRFS_FREE_SPACE_INFO_KEY 198
+
+/*
+ * A free space extent tracks an extent of space that is free in a block group.
+ * It is keyed on (start, FREE_SPACE_EXTENT, length).
+ */
+#define BTRFS_FREE_SPACE_EXTENT_KEY 199
+
+/*
+ * When a block group becomes very fragmented, we convert it to use bitmaps
+ * instead of extents. A free space bitmap is keyed on
+ * (start, FREE_SPACE_BITMAP, length); the corresponding item is a bitmap with
+ * (length / sectorsize) bits.
+ */
+#define BTRFS_FREE_SPACE_BITMAP_KEY 200
+
 #define BTRFS_DEV_EXTENT_KEY	204
 #define BTRFS_DEV_ITEM_KEY	216
 #define BTRFS_CHUNK_ITEM_KEY	228
@@ -2464,6 +2497,11 @@ BTRFS_SETGET_FUNCS(disk_block_group_flags,
 BTRFS_SETGET_STACK_FUNCS(block_group_flags,
 			struct btrfs_block_group_item, flags, 64);
 
+/* struct btrfs_free_space_info */
+BTRFS_SETGET_FUNCS(free_space_extent_count, struct btrfs_free_space_info,
+		   extent_count, 32);
+BTRFS_SETGET_FUNCS(free_space_flags, struct btrfs_free_space_info, flags, 32);
+
 /* struct btrfs_inode_ref */
 BTRFS_SETGET_FUNCS(inode_ref_name_len, struct btrfs_inode_ref, name_len, 16);
 BTRFS_SETGET_FUNCS(inode_ref_index, struct btrfs_inode_ref, index, 64);
include/trace/events/btrfs.h +2 -1
index 0b73af9be12f..e6289e62a2a8 100644
@@ -45,7 +45,8 @@ struct btrfs_qgroup_operation;
 		{ BTRFS_TREE_LOG_OBJECTID,	"TREE_LOG"	},	\
 		{ BTRFS_QUOTA_TREE_OBJECTID,	"QUOTA_TREE"	},	\
 		{ BTRFS_TREE_RELOC_OBJECTID,	"TREE_RELOC"	},	\
-		{ BTRFS_UUID_TREE_OBJECTID,	"UUID_RELOC"	},	\
+		{ BTRFS_UUID_TREE_OBJECTID,	"UUID_TREE"	},	\
+		{ BTRFS_FREE_SPACE_TREE_OBJECTID, "FREE_SPACE_TREE" },	\
 		{ BTRFS_DATA_RELOC_TREE_OBJECTID, "DATA_RELOC_TREE" })
 
 #define show_root_type(obj)						\
Signature · 1 line
2.5.2
#6 lore raw

PATCH v3 6/9 Btrfs: implement the free space B-tree

In reply to Omar Sandoval

From: Omar Sandoval <[email protected]>

The free space cache has turned out to be a scalability bottleneck on large, busy filesystems. When the cache for a lot of block groups needs to be written out, we can get extremely long commit times; if this happens in the critical section, things are especially bad because we block new transactions from happening.

The main problem with the free space cache is that it has to be written out in its entirety and is managed in an ad hoc fashion. Using a B-tree to store free space fixes this: updates can be done as needed and we get all of the benefits of using a B-tree: checksumming, RAID handling, well-understood behavior.

With the free space tree, we get commit times that are about the same as the no cache case with load times slower than the free space cache case but still much faster than the no cache case. Free space is represented with extents until it becomes more space-efficient to use bitmaps, giving us similar space overhead to the free space cache.

The operations on the free space tree are: adding and removing free space, handling the creation and deletion of block groups, and loading the free space for a block group. We can also create the free space tree by walking the extent tree and clear the free space tree.

---
 fs/btrfs/Makefile          |    2 +-
 fs/btrfs/ctree.h           |   27 +-
 fs/btrfs/extent-tree.c     |    5 +-
 fs/btrfs/free-space-tree.c | 1581 ++++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/free-space-tree.h |   72 ++
 5 files changed, 1683 insertions(+), 4 deletions(-)
 create mode 100644 fs/btrfs/free-space-tree.c
 create mode 100644 fs/btrfs/free-space-tree.h
fs/btrfs/Makefile +1 -1
index 6d1d0b93b1aa..766169709146 100644
@@ -9,7 +9,7 @@ btrfs-y += super.o ctree.o extent-tree.o print-tree.o root-tree.o dir-item.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 \
-	   uuid-tree.o props.o hash.o
+	   uuid-tree.o props.o hash.o free-space-tree.o
 
 btrfs-$(CONFIG_BTRFS_FS_POSIX_ACL) += acl.o
 btrfs-$(CONFIG_BTRFS_FS_CHECK_INTEGRITY) += check-integrity.o
fs/btrfs/ctree.h +26 -1
index b166e5c26afe..455a9016587b 100644
@@ -1302,8 +1302,20 @@ struct btrfs_block_group_cache {
 	u64 delalloc_bytes;
 	u64 bytes_super;
 	u64 flags;
-	u64 sectorsize;
 	u64 cache_generation;
+	u32 sectorsize;
+
+	/*
+	 * If the free space extent count exceeds this number, convert the block
+	 * group to bitmaps.
+	 */
+	u32 bitmap_high_thresh;
+
+	/*
+	 * If the free space extent count drops below this number, convert the
+	 * block group back to extents.
+	 */
+	u32 bitmap_low_thresh;
 
 	/*
 	 * It is just used for the delayed data space allocation because
@@ -1359,6 +1371,15 @@ struct btrfs_block_group_cache {
 	struct list_head io_list;
 
 	struct btrfs_io_ctl io_ctl;
+
+	/* Lock for free space tree operations. */
+	struct mutex free_space_lock;
+
+	/*
+	 * Does the block group need to be added to the free space tree?
+	 * Protected by free_space_lock.
+	 */
+	int needs_free_space;
 };
 
 /* delayed seq elem */
@@ -1410,6 +1431,7 @@ struct btrfs_fs_info {
 	struct btrfs_root *csum_root;
 	struct btrfs_root *quota_root;
 	struct btrfs_root *uuid_root;
+	struct btrfs_root *free_space_root;
 
 	/* the log root tree is a directory of all the other log roots */
 	struct btrfs_root *log_root_tree;
@@ -3559,6 +3581,9 @@ void btrfs_end_write_no_snapshoting(struct btrfs_root *root);
 void check_system_chunk(struct btrfs_trans_handle *trans,
 			struct btrfs_root *root,
 			const u64 type);
+u64 add_new_free_space(struct btrfs_block_group_cache *block_group,
+		       struct btrfs_fs_info *info, u64 start, u64 end);
+
 /* ctree.c */
 int btrfs_bin_search(struct extent_buffer *eb, struct btrfs_key *key,
 		     int level, int *slot);
fs/btrfs/extent-tree.c +3 -2
index 20b04edf1079..134a971bdbda 100644
@@ -337,8 +337,8 @@ static void put_caching_control(struct btrfs_caching_control *ctl)
  * we need to check the pinned_extents for any extents that can't be used yet
  * since their free space will be released as soon as the transaction commits.
  */
-static u64 add_new_free_space(struct btrfs_block_group_cache *block_group,
-			      struct btrfs_fs_info *info, u64 start, u64 end)
+u64 add_new_free_space(struct btrfs_block_group_cache *block_group,
+		       struct btrfs_fs_info *info, u64 start, u64 end)
 {
 	u64 extent_start, extent_end, size, total_added = 0;
 	int ret;
@@ -9288,6 +9288,7 @@ btrfs_create_block_group_cache(struct btrfs_root *root, u64 start, u64 size)
 	INIT_LIST_HEAD(&cache->io_list);
 	btrfs_init_free_space_ctl(cache);
 	atomic_set(&cache->trimming, 0);
+	mutex_init(&cache->free_space_lock);
 
 	return cache;
 }
fs/btrfs/free-space-tree.c new file +1581 -0

1,581 lines not on this page · raw message

fs/btrfs/free-space-tree.h new file +72 -0

72 lines not on this page · raw message

Signature · 1 line
2.5.2
#7 lore raw

PATCH v3 7/9 Btrfs: add free space tree sanity tests

In reply to Omar Sandoval

From: Omar Sandoval <[email protected]>

This tests the operations on the free space tree trying to excercise all of the main cases for both formats. Between this and xfstests, the free space tree should have pretty good coverage.

---
 fs/btrfs/Makefile                      |   3 +-
 fs/btrfs/super.c                       |   3 +
 fs/btrfs/tests/btrfs-tests.c           |  52 +++
 fs/btrfs/tests/btrfs-tests.h           |  10 +
 fs/btrfs/tests/free-space-tests.c      |  35 +-
 fs/btrfs/tests/free-space-tree-tests.c | 571 +++++++++++++++++++++++++++++++++
 fs/btrfs/tests/qgroup-tests.c          |  20 +-
 7 files changed, 646 insertions(+), 48 deletions(-)
 create mode 100644 fs/btrfs/tests/free-space-tree-tests.c
fs/btrfs/Makefile +2 -1
index 766169709146..128ce17a80b0 100644
@@ -16,4 +16,5 @@ btrfs-$(CONFIG_BTRFS_FS_CHECK_INTEGRITY) += check-integrity.o
 
 btrfs-$(CONFIG_BTRFS_FS_RUN_SANITY_TESTS) += tests/free-space-tests.o \
 	tests/extent-buffer-tests.o tests/btrfs-tests.o \
-	tests/extent-io-tests.o tests/inode-tests.o tests/qgroup-tests.o
+	tests/extent-io-tests.o tests/inode-tests.o tests/qgroup-tests.o \
+	tests/free-space-tree-tests.o
fs/btrfs/super.c +3 -0
index cd7ef34d2dce..b93f127c4bc8 100644
@@ -2203,6 +2203,9 @@ static int btrfs_run_sanity_tests(void)
 	if (ret)
 		goto out;
 	ret = btrfs_test_qgroups();
+	if (ret)
+		goto out;
+	ret = btrfs_test_free_space_tree();
 out:
 	btrfs_destroy_test_fs();
 	return ret;
fs/btrfs/tests/btrfs-tests.c +52 -0

67 lines not on this page · raw message

fs/btrfs/tests/btrfs-tests.h +10 -0
index fd3954224480..054b8c73c951 100644
@@ -24,17 +24,23 @@
 #define test_msg(fmt, ...) pr_info("BTRFS: selftest: " fmt, ##__VA_ARGS__)
 
 struct btrfs_root;
+struct btrfs_trans_handle;
 
 int btrfs_test_free_space_cache(void);
 int btrfs_test_extent_buffer_operations(void);
 int btrfs_test_extent_io(void);
 int btrfs_test_inodes(void);
 int btrfs_test_qgroups(void);
+int btrfs_test_free_space_tree(void);
 int btrfs_init_test_fs(void);
 void btrfs_destroy_test_fs(void);
 struct inode *btrfs_new_test_inode(void);
 struct btrfs_fs_info *btrfs_alloc_dummy_fs_info(void);
 void btrfs_free_dummy_root(struct btrfs_root *root);
+struct btrfs_block_group_cache *
+btrfs_alloc_dummy_block_group(unsigned long length);
+void btrfs_free_dummy_block_group(struct btrfs_block_group_cache *cache);
+void btrfs_init_dummy_trans(struct btrfs_trans_handle *trans);
 #else
 static inline int btrfs_test_free_space_cache(void)
 {
@@ -63,6 +69,10 @@ static inline int btrfs_test_qgroups(void)
 {
 	return 0;
 }
+static inline int btrfs_test_free_space_tree(void)
+{
+	return 0;
+}
 #endif
 
 #endif
fs/btrfs/tests/free-space-tests.c +2 -33
index 2299bfde39ee..bae6c599f604 100644
@@ -22,35 +22,6 @@
 #include "../free-space-cache.h"
 
 #define BITS_PER_BITMAP		(PAGE_CACHE_SIZE * 8)
-static struct btrfs_block_group_cache *init_test_block_group(void)
-{
-	struct btrfs_block_group_cache *cache;
-
-	cache = kzalloc(sizeof(*cache), GFP_NOFS);
-	if (!cache)
-		return NULL;
-	cache->free_space_ctl = kzalloc(sizeof(*cache->free_space_ctl),
-					GFP_NOFS);
-	if (!cache->free_space_ctl) {
-		kfree(cache);
-		return NULL;
-	}
-
-	cache->key.objectid = 0;
-	cache->key.offset = 1024 * 1024 * 1024;
-	cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
-	cache->sectorsize = 4096;
-	cache->full_stripe_len = 4096;
-
-	spin_lock_init(&cache->lock);
-	INIT_LIST_HEAD(&cache->list);
-	INIT_LIST_HEAD(&cache->cluster_list);
-	INIT_LIST_HEAD(&cache->bg_list);
-
-	btrfs_init_free_space_ctl(cache);
-
-	return cache;
-}
 
 /*
  * This test just does basic sanity checking, making sure we can add an exten
@@ -883,7 +854,7 @@ int btrfs_test_free_space_cache(void)
 
 	test_msg("Running btrfs free space cache tests\n");
 
-	cache = init_test_block_group();
+	cache = btrfs_alloc_dummy_block_group(1024 * 1024 * 1024);
 	if (!cache) {
 		test_msg("Couldn't run the tests\n");
 		return 0;
@@ -901,9 +872,7 @@ int btrfs_test_free_space_cache(void)
 
 	ret = test_steal_space_from_bitmap_to_extent(cache);
 out:
-	__btrfs_remove_free_space_cache(cache->free_space_ctl);
-	kfree(cache->free_space_ctl);
-	kfree(cache);
+	btrfs_free_dummy_block_group(cache);
 	test_msg("Free space cache tests finished\n");
 	return ret;
 }
fs/btrfs/tests/free-space-tree-tests.c new file +571 -0

571 lines not on this page · raw message

fs/btrfs/tests/qgroup-tests.c +6 -14
index 846d277b1901..8ea5d34bc5a2 100644
@@ -23,14 +23,6 @@
 #include "../qgroup.h"
 #include "../backref.h"
 
-static void init_dummy_trans(struct btrfs_trans_handle *trans)
-{
-	memset(trans, 0, sizeof(*trans));
-	trans->transid = 1;
-	INIT_LIST_HEAD(&trans->qgroup_ref_list);
-	trans->type = __TRANS_DUMMY;
-}
-
 static int insert_normal_tree_ref(struct btrfs_root *root, u64 bytenr,
 				  u64 num_bytes, u64 parent, u64 root_objectid)
 {
@@ -44,7 +36,7 @@ static int insert_normal_tree_ref(struct btrfs_root *root, u64 bytenr,
 	u32 size = sizeof(*item) + sizeof(*iref) + sizeof(*block_info);
 	int ret;
 
-	init_dummy_trans(&trans);
+	btrfs_init_dummy_trans(&trans);
 
 	ins.objectid = bytenr;
 	ins.type = BTRFS_EXTENT_ITEM_KEY;
@@ -94,7 +86,7 @@ static int add_tree_ref(struct btrfs_root *root, u64 bytenr, u64 num_bytes,
 	u64 refs;
 	int ret;
 
-	init_dummy_trans(&trans);
+	btrfs_init_dummy_trans(&trans);
 
 	key.objectid = bytenr;
 	key.type = BTRFS_EXTENT_ITEM_KEY;
@@ -144,7 +136,7 @@ static int remove_extent_item(struct btrfs_root *root, u64 bytenr,
 	struct btrfs_path *path;
 	int ret;
 
-	init_dummy_trans(&trans);
+	btrfs_init_dummy_trans(&trans);
 
 	key.objectid = bytenr;
 	key.type = BTRFS_EXTENT_ITEM_KEY;
@@ -178,7 +170,7 @@ static int remove_extent_ref(struct btrfs_root *root, u64 bytenr,
 	u64 refs;
 	int ret;
 
-	init_dummy_trans(&trans);
+	btrfs_init_dummy_trans(&trans);
 
 	key.objectid = bytenr;
 	key.type = BTRFS_EXTENT_ITEM_KEY;
@@ -232,7 +224,7 @@ static int test_no_shared_qgroup(struct btrfs_root *root)
 	struct ulist *new_roots = NULL;
 	int ret;
 
-	init_dummy_trans(&trans);
+	btrfs_init_dummy_trans(&trans);
 
 	test_msg("Qgroup basic add\n");
 	ret = btrfs_create_qgroup(NULL, fs_info, 5);
@@ -326,7 +318,7 @@ static int test_multiple_refs(struct btrfs_root *root)
 	struct ulist *new_roots = NULL;
 	int ret;
 
-	init_dummy_trans(&trans);
+	btrfs_init_dummy_trans(&trans);
 
 	test_msg("Qgroup multiple refs test\n");
 
Signature · 1 line
2.5.2
#8 lore raw

PATCH v3 8/9 Btrfs: wire up the free space tree to the extent tree

In reply to Omar Sandoval

From: Omar Sandoval <[email protected]>

The free space tree is updated in tandem with the extent tree. There are only a handful of places where we need to hook in:

1. Block group creation
2. Block group deletion
3. Delayed refs (extent creation and deletion)
4. Block group caching

---
 fs/btrfs/extent-tree.c | 36 +++++++++++++++++++++++++++++++++---
 1 file changed, 33 insertions(+), 3 deletions(-)
fs/btrfs/extent-tree.c +33 -3
index 134a971bdbda..0178718ec7a1 100644
@@ -33,6 +33,7 @@
 #include "raid56.h"
 #include "locking.h"
 #include "free-space-cache.h"
+#include "free-space-tree.h"
 #include "math.h"
 #include "sysfs.h"
 #include "qgroup.h"
@@ -518,7 +519,10 @@ static noinline void caching_thread(struct btrfs_work *work)
 	mutex_lock(&caching_ctl->mutex);
 	down_read(&fs_info->commit_root_sem);
 
-	ret = load_extent_tree_free(caching_ctl);
+	if (btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
+		ret = load_free_space_tree(caching_ctl);
+	else
+		ret = load_extent_tree_free(caching_ctl);
 
 	spin_lock(&block_group->lock);
 	block_group->caching_ctl = NULL;
@@ -624,8 +628,8 @@ static int cache_block_group(struct btrfs_block_group_cache *cache,
 		}
 	} else {
 		/*
-		 * We are not going to do the fast caching, set cached to the
-		 * appropriate value and wakeup any waiters.
+		 * We're either using the free space tree or no caching at all.
+		 * Set cached to the appropriate value and wakeup any waiters.
 		 */
 		spin_lock(&cache->lock);
 		if (load_cache_only) {
@@ -6383,6 +6387,13 @@ static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
 			}
 		}
 
+		ret = add_to_free_space_tree(trans, root->fs_info, bytenr,
+					     num_bytes);
+		if (ret) {
+			btrfs_abort_transaction(trans, extent_root, ret);
+			goto out;
+		}
+
 		ret = update_block_group(trans, root, bytenr, num_bytes, 0);
 		if (ret) {
 			btrfs_abort_transaction(trans, extent_root, ret);
@@ -7326,6 +7337,11 @@ static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
 	btrfs_mark_buffer_dirty(path->nodes[0]);
 	btrfs_free_path(path);
 
+	ret = remove_from_free_space_tree(trans, fs_info, ins->objectid,
+					  ins->offset);
+	if (ret)
+		return ret;
+
 	ret = update_block_group(trans, root, ins->objectid, ins->offset, 1);
 	if (ret) { /* -ENOENT, logic error */
 		btrfs_err(fs_info, "update block group failed for %llu %llu",
@@ -7407,6 +7423,11 @@ static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
 	btrfs_mark_buffer_dirty(leaf);
 	btrfs_free_path(path);
 
+	ret = remove_from_free_space_tree(trans, fs_info, ins->objectid,
+					  num_bytes);
+	if (ret)
+		return ret;
+
 	ret = update_block_group(trans, root, ins->objectid, root->nodesize,
 				 1);
 	if (ret) { /* -ENOENT, logic error */
@@ -9277,6 +9298,8 @@ btrfs_create_block_group_cache(struct btrfs_root *root, u64 start, u64 size)
 	cache->full_stripe_len = btrfs_full_stripe_len(root,
 					       &root->fs_info->mapping_tree,
 					       start);
+	set_free_space_tree_thresholds(cache);
+
 	atomic_set(&cache->count, 1);
 	spin_lock_init(&cache->lock);
 	init_rwsem(&cache->data_rwsem);
@@ -9497,6 +9520,8 @@ void btrfs_create_pending_block_groups(struct btrfs_trans_handle *trans,
 					       key.objectid, key.offset);
 		if (ret)
 			btrfs_abort_transaction(trans, extent_root, ret);
+		add_block_group_free_space(trans, root->fs_info, block_group);
+		/* already aborted the transaction if it failed. */
 next:
 		list_del_init(&block_group->bg_list);
 	}
@@ -9526,6 +9551,7 @@ int btrfs_make_block_group(struct btrfs_trans_handle *trans,
 	cache->flags = type;
 	cache->last_byte_to_unpin = (u64)-1;
 	cache->cached = BTRFS_CACHE_FINISHED;
+	cache->needs_free_space = 1;
 	ret = exclude_super_stripes(root, cache);
 	if (ret) {
 		/*
@@ -9883,6 +9909,10 @@ int btrfs_remove_block_group(struct btrfs_trans_handle *trans,
 
 	unlock_chunks(root);
 
+	ret = remove_block_group_free_space(trans, root->fs_info, block_group);
+	if (ret)
+		goto out;
+
 	btrfs_put_block_group(block_group);
 	btrfs_put_block_group(block_group);
 
Signature · 1 line
2.5.2
#9 lore raw

PATCH v3 9/9 Btrfs: add free space tree mount option

In reply to Omar Sandoval

From: Omar Sandoval <[email protected]>

Now we can finally hook up everything so we can actually use free space tree. The free space tree is enabled by passing the space_cache=v2 mount option. On the first mount with the this option set, the free space tree will be created and the FREE_SPACE_TREE read-only compat bit will be set. Any time the filesystem is mounted from then on, we must use the free space tree. The clear_cache option will also clear the free space tree.

---
 fs/btrfs/ctree.h   |  7 ++++++-
 fs/btrfs/disk-io.c | 38 ++++++++++++++++++++++++++++++++++++++
 fs/btrfs/super.c   | 53 ++++++++++++++++++++++++++++++++++++++++++++---------
 3 files changed, 88 insertions(+), 10 deletions(-)
fs/btrfs/ctree.h +6 -1
index 455a9016587b..d6e2d9cf41bf 100644
@@ -531,7 +531,10 @@ struct btrfs_super_block {
 #define BTRFS_FEATURE_COMPAT_SUPP		0ULL
 #define BTRFS_FEATURE_COMPAT_SAFE_SET		0ULL
 #define BTRFS_FEATURE_COMPAT_SAFE_CLEAR		0ULL
-#define BTRFS_FEATURE_COMPAT_RO_SUPP		0ULL
+
+#define BTRFS_FEATURE_COMPAT_RO_SUPP			\
+	(BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE)
+
 #define BTRFS_FEATURE_COMPAT_RO_SAFE_SET	0ULL
 #define BTRFS_FEATURE_COMPAT_RO_SAFE_CLEAR	0ULL
 
@@ -2209,6 +2212,7 @@ struct btrfs_ioctl_defrag_range_args {
 #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_MOUNT_FREE_SPACE_TREE	(1 << 24)
 
 #define BTRFS_DEFAULT_COMMIT_INTERVAL	(30)
 #define BTRFS_DEFAULT_MAX_INLINE	(8192)
@@ -3748,6 +3752,7 @@ static inline void free_fs_info(struct btrfs_fs_info *fs_info)
 	kfree(fs_info->csum_root);
 	kfree(fs_info->quota_root);
 	kfree(fs_info->uuid_root);
+	kfree(fs_info->free_space_root);
 	kfree(fs_info->super_copy);
 	kfree(fs_info->super_for_commit);
 	security_free_mnt_opts(&fs_info->security_opts);
fs/btrfs/disk-io.c +38 -0
index f556c3732c2c..31363675353f 100644
@@ -42,6 +42,7 @@
 #include "locking.h"
 #include "tree-log.h"
 #include "free-space-cache.h"
+#include "free-space-tree.h"
 #include "inode-map.h"
 #include "check-integrity.h"
 #include "rcu-string.h"
@@ -1641,6 +1642,9 @@ struct btrfs_root *btrfs_get_fs_root(struct btrfs_fs_info *fs_info,
 	if (location->objectid == BTRFS_UUID_TREE_OBJECTID)
 		return fs_info->uuid_root ? fs_info->uuid_root :
 					    ERR_PTR(-ENOENT);
+	if (location->objectid == BTRFS_FREE_SPACE_TREE_OBJECTID)
+		return fs_info->free_space_root ? fs_info->free_space_root :
+						  ERR_PTR(-ENOENT);
 again:
 	root = btrfs_lookup_fs_root(fs_info, location->objectid);
 	if (root) {
@@ -2138,6 +2142,7 @@ static void free_root_pointers(struct btrfs_fs_info *info, int chunk_root)
 	free_root_extent_buffers(info->uuid_root);
 	if (chunk_root)
 		free_root_extent_buffers(info->chunk_root);
+	free_root_extent_buffers(info->free_space_root);
 }
 
 void btrfs_free_fs_roots(struct btrfs_fs_info *fs_info)
@@ -2439,6 +2444,15 @@ static int btrfs_read_roots(struct btrfs_fs_info *fs_info,
 		fs_info->uuid_root = root;
 	}
 
+	if (btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE)) {
+		location.objectid = BTRFS_FREE_SPACE_TREE_OBJECTID;
+		root = btrfs_read_tree_root(tree_root, &location);
+		if (IS_ERR(root))
+			return PTR_ERR(root);
+		set_bit(BTRFS_ROOT_TRACK_DIRTY, &root->state);
+		fs_info->free_space_root = root;
+	}
+
 	return 0;
 }
 
@@ -3063,6 +3077,30 @@ retry_root_backup:
 
 	btrfs_qgroup_rescan_resume(fs_info);
 
+	if (btrfs_test_opt(tree_root, CLEAR_CACHE) &&
+	    btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE)) {
+		pr_info("BTRFS: clearing free space tree\n");
+		ret = btrfs_clear_free_space_tree(fs_info);
+		if (ret) {
+			pr_warn("BTRFS: failed to clear free space tree %d\n",
+				ret);
+			close_ctree(tree_root);
+			return ret;
+		}
+	}
+
+	if (btrfs_test_opt(tree_root, FREE_SPACE_TREE) &&
+	    !btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE)) {
+		pr_info("BTRFS: creating free space tree\n");
+		ret = btrfs_create_free_space_tree(fs_info);
+		if (ret) {
+			pr_warn("BTRFS: failed to create free space tree %d\n",
+				ret);
+			close_ctree(tree_root);
+			return ret;
+		}
+	}
+
 	if (!fs_info->uuid_root) {
 		pr_info("BTRFS: creating UUID tree\n");
 		ret = btrfs_create_uuid_tree(fs_info);
fs/btrfs/super.c +44 -9

96 lines not on this page · raw message

Signature · 1 line
2.5.2
#10 lore raw

PATCH v3 1/3 btrfs-progs: use calloc instead of malloc+memset for tree roots

In reply to Omar Sandoval

From: Omar Sandoval <[email protected]>

---
 disk-io.c | 22 +++++++---------------
 1 file changed, 7 insertions(+), 15 deletions(-)
disk-io.c +7 -15
index 1d4889322411..8496aded31c4 100644
@@ -833,13 +833,13 @@ struct btrfs_fs_info *btrfs_new_fs_info(int writable, u64 sb_bytenr)
 
 	memset(fs_info, 0, sizeof(struct btrfs_fs_info));
 
-	fs_info->tree_root = malloc(sizeof(struct btrfs_root));
-	fs_info->extent_root = malloc(sizeof(struct btrfs_root));
-	fs_info->chunk_root = malloc(sizeof(struct btrfs_root));
-	fs_info->dev_root = malloc(sizeof(struct btrfs_root));
-	fs_info->csum_root = malloc(sizeof(struct btrfs_root));
-	fs_info->quota_root = malloc(sizeof(struct btrfs_root));
-	fs_info->super_copy = malloc(BTRFS_SUPER_INFO_SIZE);
+	fs_info->tree_root = calloc(1, sizeof(struct btrfs_root));
+	fs_info->extent_root = calloc(1, sizeof(struct btrfs_root));
+	fs_info->chunk_root = calloc(1, sizeof(struct btrfs_root));
+	fs_info->dev_root = calloc(1, sizeof(struct btrfs_root));
+	fs_info->csum_root = calloc(1, sizeof(struct btrfs_root));
+	fs_info->quota_root = calloc(1, sizeof(struct btrfs_root));
+	fs_info->super_copy = calloc(1, BTRFS_SUPER_INFO_SIZE);
 
 	if (!fs_info->tree_root || !fs_info->extent_root ||
 	    !fs_info->chunk_root || !fs_info->dev_root ||
@@ -847,14 +847,6 @@ struct btrfs_fs_info *btrfs_new_fs_info(int writable, u64 sb_bytenr)
 	    !fs_info->super_copy)
 		goto free_all;
 
-	memset(fs_info->super_copy, 0, BTRFS_SUPER_INFO_SIZE);
-	memset(fs_info->tree_root, 0, sizeof(struct btrfs_root));
-	memset(fs_info->extent_root, 0, sizeof(struct btrfs_root));
-	memset(fs_info->chunk_root, 0, sizeof(struct btrfs_root));
-	memset(fs_info->dev_root, 0, sizeof(struct btrfs_root));
-	memset(fs_info->csum_root, 0, sizeof(struct btrfs_root));
-	memset(fs_info->quota_root, 0, sizeof(struct btrfs_root));
-
 	extent_io_tree_init(&fs_info->extent_cache);
 	extent_io_tree_init(&fs_info->free_space_cache);
 	extent_io_tree_init(&fs_info->block_group_cache);
Signature · 1 line
2.5.2
#11 lore raw

PATCH v3 2/3 btrfs-progs: add basic awareness of the free space tree

From: Omar Sandoval <[email protected]>

To start, let's tell btrfs-progs to read the free space root and how to print the on-disk format of the free space tree. However, we're not adding the FREE_SPACE_TREE read-only compat bit to the set of supported bits because progs doesn't know how to keep the free space tree consistent.

---
 btrfs-debug-tree.c |  4 ++++
 ctree.h            | 49 ++++++++++++++++++++++++++++++++++++++++++++++++-
 disk-io.c          | 16 +++++++++++++++-
 print-tree.c       | 25 +++++++++++++++++++++++++
 4 files changed, 92 insertions(+), 2 deletions(-)
btrfs-debug-tree.c +4 -0
index 7d8e876f1a2d..2aa5bd11d1b6 100644
@@ -375,6 +375,10 @@ again:
 				if (!skip)
 					printf("uuid");
 				break;
+			case BTRFS_FREE_SPACE_TREE_OBJECTID:
+				if (!skip)
+					printf("free space");
+				break;
 			case BTRFS_MULTIPLE_OBJECTIDS:
 				if (!skip) {
 					printf("multiple");
ctree.h +48 -1

99 lines not on this page · raw message

disk-io.c +15 -1
index 8496aded31c4..ae9d6e1abb23 100644
@@ -818,6 +818,7 @@ void btrfs_free_fs_info(struct btrfs_fs_info *fs_info)
 	free(fs_info->dev_root);
 	free(fs_info->csum_root);
 	free(fs_info->quota_root);
+	free(fs_info->free_space_root);
 	free(fs_info->super_copy);
 	free(fs_info->log_root_tree);
 	free(fs_info);
@@ -839,12 +840,13 @@ struct btrfs_fs_info *btrfs_new_fs_info(int writable, u64 sb_bytenr)
 	fs_info->dev_root = calloc(1, sizeof(struct btrfs_root));
 	fs_info->csum_root = calloc(1, sizeof(struct btrfs_root));
 	fs_info->quota_root = calloc(1, sizeof(struct btrfs_root));
+	fs_info->free_space_root = calloc(1, sizeof(struct btrfs_root));
 	fs_info->super_copy = calloc(1, BTRFS_SUPER_INFO_SIZE);
 
 	if (!fs_info->tree_root || !fs_info->extent_root ||
 	    !fs_info->chunk_root || !fs_info->dev_root ||
 	    !fs_info->csum_root || !fs_info->quota_root ||
-	    !fs_info->super_copy)
+	    !fs_info->free_space_root || !fs_info->super_copy)
 		goto free_all;
 
 	extent_io_tree_init(&fs_info->extent_cache);
@@ -1025,6 +1027,16 @@ int btrfs_setup_all_roots(struct btrfs_fs_info *fs_info, u64 root_tree_bytenr,
 	if (ret == 0)
 		fs_info->quota_enabled = 1;
 
+	if (btrfs_fs_compat_ro(fs_info, BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE)) {
+		ret = find_and_setup_root(root, fs_info, BTRFS_FREE_SPACE_TREE_OBJECTID,
+					  fs_info->free_space_root);
+		if (ret) {
+			printk("Couldn't read free space tree\n");
+			return -EIO;
+		}
+		fs_info->free_space_root->track_dirty = 1;
+	}
+
 	ret = find_and_setup_log_root(root, fs_info, sb);
 	if (ret) {
 		printk("Couldn't setup log root tree\n");
@@ -1050,6 +1062,8 @@ int btrfs_setup_all_roots(struct btrfs_fs_info *fs_info, u64 root_tree_bytenr,
 
 void btrfs_release_all_roots(struct btrfs_fs_info *fs_info)
 {
+	if (fs_info->free_space_root)
+		free_extent_buffer(fs_info->free_space_root->node);
 	if (fs_info->quota_root)
 		free_extent_buffer(fs_info->quota_root->node);
 	if (fs_info->csum_root)
print-tree.c +25 -0
index dc1d2764ae91..9dc058b58bde 100644
@@ -610,6 +610,15 @@ static void print_key_type(u64 objectid, u8 type)
 	case BTRFS_BLOCK_GROUP_ITEM_KEY:
 		printf("BLOCK_GROUP_ITEM");
 		break;
+	case BTRFS_FREE_SPACE_INFO_KEY:
+		printf("FREE_SPACE_INFO");
+		break;
+	case BTRFS_FREE_SPACE_EXTENT_KEY:
+		printf("FREE_SPACE_EXTENT");
+		break;
+	case BTRFS_FREE_SPACE_BITMAP_KEY:
+		printf("FREE_SPACE_BITMAP");
+		break;
 	case BTRFS_CHUNK_ITEM_KEY:
 		printf("CHUNK_ITEM");
 		break;
@@ -728,6 +737,9 @@ static void print_objectid(u64 objectid, u8 type)
 	case BTRFS_UUID_TREE_OBJECTID:
 		printf("UUID_TREE");
 		break;
+	case BTRFS_FREE_SPACE_TREE_OBJECTID:
+		printf("FREE_SPACE_TREE");
+		break;
 	case BTRFS_MULTIPLE_OBJECTIDS:
 		printf("MULTIPLE");
 		break;
@@ -810,6 +822,7 @@ void btrfs_print_leaf(struct btrfs_root *root, struct extent_buffer *l)
 	struct btrfs_dev_extent *dev_extent;
 	struct btrfs_disk_key disk_key;
 	struct btrfs_block_group_item bg_item;
+	struct btrfs_free_space_info *free_info;
 	struct btrfs_dir_log_item *dlog;
 	struct btrfs_qgroup_info_item *qg_info;
 	struct btrfs_qgroup_limit_item *qg_limit;
@@ -947,6 +960,18 @@ void btrfs_print_leaf(struct btrfs_root *root, struct extent_buffer *l)
 			       (unsigned long long)btrfs_block_group_chunk_objectid(&bg_item),
 			       flags_str);
 			break;
+		case BTRFS_FREE_SPACE_INFO_KEY:
+			free_info = btrfs_item_ptr(l, i, struct btrfs_free_space_info);
+			printf("\t\tfree space info extent count %u flags %u\n",
+			       (unsigned)btrfs_free_space_extent_count(l, free_info),
+			       (unsigned)btrfs_free_space_flags(l, free_info));
+			break;
+		case BTRFS_FREE_SPACE_EXTENT_KEY:
+			printf("\t\tfree space extent\n");
+			break;
+		case BTRFS_FREE_SPACE_BITMAP_KEY:
+			printf("\t\tfree space bitmap\n");
+			break;
 		case BTRFS_CHUNK_ITEM_KEY:
 			print_chunk(l, btrfs_item_ptr(l, i, struct btrfs_chunk));
 			break;
Signature · 1 line
2.5.2
#12 lore raw

PATCH v3 3/3 btrfs-progs: check the free space tree in btrfsck

In reply to Omar Sandoval

From: Omar Sandoval <[email protected]>

This reuses the existing code for checking the free space cache, we just need to load the free space tree. While we do that, we check a couple of invariants on the free space tree itself. This requires pulling in some code from the kernel to exclude the super stripes.

---
 Makefile.in        |   2 +-
 cmds-check.c       |  32 ++++++-
 ctree.h            |   6 ++
 extent-tree.c      | 118 +++++++++++++++++++++++
 extent_io.c        |   6 ++
 extent_io.h        |   2 +
 free-space-cache.c |   4 +-
 free-space-cache.h |   2 +
 free-space-tree.c  | 267 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 free-space-tree.h  |  25 +++++
 10 files changed, 457 insertions(+), 7 deletions(-)
 create mode 100644 free-space-tree.c
 create mode 100644 free-space-tree.h
Makefile.in +1 -1
index 665f83c04d00..cac9a269ee8f 100644
@@ -38,7 +38,7 @@ objects = ctree.o disk-io.o radix-tree.o extent-tree.o print-tree.o \
 	  extent-cache.o extent_io.o volumes.o utils.o repair.o \
 	  qgroup.o raid6.o free-space-cache.o list_sort.o props.o \
 	  ulist.o qgroup-verify.o backref.o string-table.o task-utils.o \
-	  inode.o file.o find-root.o
+	  inode.o file.o find-root.o free-space-tree.o
 cmds_objects = cmds-subvolume.o cmds-filesystem.o cmds-device.o cmds-scrub.o \
 	       cmds-inspect.o cmds-balance.o cmds-send.o cmds-receive.o \
 	       cmds-quota.o cmds-qgroup.o cmds-replace.o cmds-check.o \
cmds-check.c +28 -4
index 0694a3bc5646..04459750c783 100644
@@ -34,6 +34,7 @@
 #include "utils.h"
 #include "commands.h"
 #include "free-space-cache.h"
+#include "free-space-tree.h"
 #include "btrfsck.h"
 #include "qgroup-verify.h"
 #include "rbtree-utils.h"
@@ -5285,9 +5286,29 @@ static int check_space_cache(struct btrfs_root *root)
 			btrfs_remove_free_space_cache(cache);
 		}
 
-		ret = load_free_space_cache(root->fs_info, cache);
-		if (!ret)
-			continue;
+		if (btrfs_fs_compat_ro(root->fs_info,
+				       BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE)) {
+			ret = exclude_super_stripes(root, cache);
+			if (ret) {
+				fprintf(stderr, "could not exclude super stripes: %s\n",
+					strerror(-ret));
+				error++;
+				continue;
+			}
+			ret = load_free_space_tree(root->fs_info, cache);
+			free_excluded_extents(root, cache);
+			if (ret < 0) {
+				fprintf(stderr, "could not load free space tree: %s\n",
+					strerror(-ret));
+				error++;
+				continue;
+			}
+			error += ret;
+		} else {
+			ret = load_free_space_cache(root->fs_info, cache);
+			if (!ret)
+				continue;
+		}
 
 		ret = verify_space_cache(root, cache);
 		if (ret) {
@@ -9495,7 +9516,10 @@ int cmd_check(int argc, char **argv)
 		goto close_out;
 	}
 
-	fprintf(stderr, "checking free space cache\n");
+	if (btrfs_fs_compat_ro(info, BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE))
+		fprintf(stderr, "checking free space tree\n");
+	else
+		fprintf(stderr, "checking free space cache\n");
 	ret = check_space_cache(root);
 	if (ret)
 		goto out;
ctree.h +6 -0
index 6339ad50a412..34037e882ace 100644
@@ -2327,6 +2327,12 @@ int btrfs_record_file_extent(struct btrfs_trans_handle *trans,
 			      u64 num_bytes);
 int btrfs_free_block_group(struct btrfs_trans_handle *trans,
 			   struct btrfs_fs_info *fs_info, u64 bytenr, u64 len);
+void free_excluded_extents(struct btrfs_root *root,
+			   struct btrfs_block_group_cache *cache);
+int exclude_super_stripes(struct btrfs_root *root,
+			  struct btrfs_block_group_cache *cache);
+u64 add_new_free_space(struct btrfs_block_group_cache *block_group,
+		       struct btrfs_fs_info *info, u64 start, u64 end);
 /* ctree.c */
 int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2);
 int btrfs_del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
extent-tree.c +118 -0

121 lines not on this page · raw message

extent_io.c +6 -0
index 07695ef8a097..079ab7f2fb7d 100644
@@ -885,3 +885,9 @@ void memset_extent_buffer(struct extent_buffer *eb, char c,
 {
 	memset(eb->data + start, c, len);
 }
+
+int extent_buffer_test_bit(struct extent_buffer *eb, unsigned long start,
+			   unsigned long nr)
+{
+	return test_bit(nr, (unsigned long *)(eb->data + start));
+}
extent_io.h +2 -0
index 27c4b6931c97..a9a7353556a7 100644
@@ -148,6 +148,8 @@ void memmove_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset,
 			   unsigned long src_offset, unsigned long len);
 void memset_extent_buffer(struct extent_buffer *eb, char c,
 			  unsigned long start, unsigned long len);
+int extent_buffer_test_bit(struct extent_buffer *eb, unsigned long start,
+			   unsigned long nr);
 int set_extent_buffer_dirty(struct extent_buffer *eb);
 int clear_extent_buffer_dirty(struct extent_buffer *eb);
 int read_data_from_disk(struct btrfs_fs_info *info, void *buf, u64 offset,
free-space-cache.c +2 -2
index 19ab0c904a71..d10a5f517b10 100644
@@ -802,8 +802,8 @@ void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
 	__btrfs_remove_free_space_cache(block_group->free_space_ctl);
 }
 
-static int btrfs_add_free_space(struct btrfs_free_space_ctl *ctl, u64 offset,
-				u64 bytes)
+int btrfs_add_free_space(struct btrfs_free_space_ctl *ctl, u64 offset,
+			 u64 bytes)
 {
 	struct btrfs_free_space *info;
 	int ret = 0;
free-space-cache.h +2 -0
index 85411a10e64b..9214077a1b27 100644
@@ -57,4 +57,6 @@ int btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group,
 			      int sectorsize);
 void unlink_free_space(struct btrfs_free_space_ctl *ctl,
 		       struct btrfs_free_space *info);
+int btrfs_add_free_space(struct btrfs_free_space_ctl *ctl, u64 offset,
+			 u64 bytes);
 #endif
free-space-tree.c new file +267 -0

267 lines not on this page · raw message

free-space-tree.h new file +25 -0
new file mode 100644
index 000000000000..7529a46890da
@@ -0,0 +1,25 @@
+/*
+ * Copyright (C) 2015 Facebook.  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.
+ */
+
+#ifndef __BTRFS_FREE_SPACE_TREE_H__
+#define __BTRFS_FREE_SPACE_TREE_H__
+
+int load_free_space_tree(struct btrfs_fs_info *fs_info,
+			 struct btrfs_block_group_cache *block_group);
+
+#endif
Signature · 1 line
2.5.2
Tested-by on the v3 series
#14 lore raw
In reply to Omar Sandoval
Quoted 4 lines · Omar Sandoval

I went back and fixed the issues that came up since v2. Changes below. I removed Josef's Reviewed-by on patch 9 because it was completely rewritten to change the mount options like Dave suggested. These are still based on 4.2

I decided to take one for the team and try this.

Merging it into my custom 4.1++ tree (with btrfs at ~4.3) worked flawlessly, just as the -progs bits. \o/

Upgrading existing filesystems works fine and performance on my peasant systems with SATA SSDs and rust is still good; not worse but also not noticeably better. Maybe it is and I just didn't notice; otherwise I guess that's good for a cache which is not really supposed to be noticeable. :)

Unmounting, remounting, btrfs check all also seem to work as expected.

Two questions:

1) I believe the previous postings mentioned that the fst inherits the metadata properties - does this mean that e.g. on a single rotational disk with data=single,metadata=dup the fst is also dup? Is this good, bad, intentional? I guess it might prevent some of the problems with corrupted v1 caches that some people had.

2) the following:

Quoted 5 lines

- Changed the free_space_tree option to space_cache=v2 and made clear_cache clear the free space tree. If the free space tree has been created, the mount will fail unless space_cache=v2 or nospace_cache,clear_cache is given because we cannot allow the free space tree to get out of date.

also all seem to work in my testing (wrt. the clearing/downgrading to v1), but once a volume has been upgraded to v2 fst, a simple mount does not need to specify space_cache=v2 again; it seems to stick until cleared/downgraded. Not sure if that is what you meant to say.

Long story short: +1 excellent job and:

cheers!

Holger

#15 lore raw
Quoted 18 lines · Holger Hoffstätte
Quoted 4 lines · Omar Sandoval

I went back and fixed the issues that came up since v2. Changes below. I removed Josef's Reviewed-by on patch 9 because it was completely rewritten to change the mount options like Dave suggested. These are still based on 4.2

I decided to take one for the team and try this.

Merging it into my custom 4.1++ tree (with btrfs at ~4.3) worked flawlessly, just as the -progs bits. \o/

Upgrading existing filesystems works fine and performance on my peasant systems with SATA SSDs and rust is still good; not worse but also not noticeably better. Maybe it is and I just didn't notice; otherwise I guess that's good for a cache which is not really supposed to be noticeable. :)

Unmounting, remounting, btrfs check all also seem to work as expected.

Quoted 7 lines

Two questions:

1) I believe the previous postings mentioned that the fst inherits the metadata properties - does this mean that e.g. on a single rotational disk with data=single,metadata=dup the fst is also dup? Is this good, bad, intentional? I guess it might prevent some of the problems with corrupted v1 caches that some people had.

Yeah, that's correct, the free space tree will have the same profile as the rest of the metadata. There's certainly a cost in duplicating the free space tree where the old space cache wouldn't have been duplicated, but it's a good thing that the free space tree be consistent with the rest of the metadata.

Quoted 8 lines

2) the following:

Quoted 5 lines

- Changed the free_space_tree option to space_cache=v2 and made clear_cache clear the free space tree. If the free space tree has been created, the mount will fail unless space_cache=v2 or nospace_cache,clear_cache is given because we cannot allow the free space tree to get out of date.

Quoted 4 lines

also all seem to work in my testing (wrt. the clearing/downgrading to v1), but once a volume has been upgraded to v2 fst, a simple mount does not need to specify space_cache=v2 again; it seems to stick until cleared/downgraded. Not sure if that is what you meant to say.

Yeah, to be clear: if the filesystem is mounted with space_cache=v2 once, it's assumed from then on unless the user specifies otherwise (i.e., nospace_cache,clear_cache). The idea there was to be consistent with the original space_cache.

Quoted 6 lines

Long story short: +1 excellent job and:

cheers!

Holger

Thanks a ton for testing this out!

Signature · 1 line
Omar
Tested-by on the v3 series
#16 lore raw
In reply to Omar Sandoval
Quoted 70 lines · Omar Sandoval

Hi, everyone,

I went back and fixed the issues that came up since v2. Changes below. I removed Josef's Reviewed-by on patch 9 because it was completely rewritten to change the mount options like Dave suggested. These are still based on 4.2

Thanks!

Changes from v2->v3:

- Fixed a warning in the free space tree sanity tests caught by Zhao Lei.
- Moved the addition of a block group to the free space tree to occur either on the first attempt to modify the free space for the block group or in btrfs_create_pending_block_groups(), whichever happens first. This avoids a deadlock (lock recursion) when modifying the free space tree requires allocating a new block group. In order to do this, it was simpler to change the on-disk semantics: the superblock stripes will now appear to be free space according to the free space tree, but load_free_space_tree() will still exclude them when building the in-memory free space cache.
- Changed the free_space_tree option to space_cache=v2 and made clear_cache clear the free space tree. If the free space tree has been created, the mount will fail unless space_cache=v2 or nospace_cache,clear_cache is given because we cannot allow the free space tree to get out of date.
- Did a once-over of the code and caught a couple of error handling typos.

v2: http://www.spinics.net/lists/linux-btrfs/msg46796.html

Changes from v1->v2:

- Cleaned up a bunch of unnecessary instances of "if (ret) goto out; ret = 0"
- Added aborts in the free space tree code closer to the site the error is
encountered: where we add or remove block groups, add or remove free space, and also when we convert formats
- Moved loading of the free space tree into caching_thread() and added a new patch 3 in preparation for it
- Commented a bunch of stuff in the extent buffer bitmap operations and refactored some of the complicated logic

v1: http://www.spinics.net/lists/linux-btrfs/msg46713.html

Omar Sandoval (9):
Btrfs: add extent buffer bitmap operations
Btrfs: add extent buffer bitmap sanity tests
Btrfs: add helpers for read-only compat bits
Btrfs: refactor caching_thread()
Btrfs: introduce the free space B-tree on-disk format
Btrfs: implement the free space B-tree
Btrfs: add free space tree sanity tests
Btrfs: wire up the free space tree to the extent tree
Btrfs: add free space tree mount option

  fs/btrfs/Makefile                      |    5 +-
  fs/btrfs/ctree.h                       |  157 +++-
  fs/btrfs/disk-io.c                     |   38 +
  fs/btrfs/extent-tree.c                 |   98 +-
  fs/btrfs/extent_io.c                   |  183 +++-
  fs/btrfs/extent_io.h                   |   10 +-
  fs/btrfs/free-space-tree.c             | 1581 ++++++++++++++++++++++++++++++++
  fs/btrfs/free-space-tree.h             |   72 ++
  fs/btrfs/super.c                       |   56 +-
  fs/btrfs/tests/btrfs-tests.c           |   52 ++
  fs/btrfs/tests/btrfs-tests.h           |   10 +
  fs/btrfs/tests/extent-io-tests.c       |  138 ++-
  fs/btrfs/tests/free-space-tests.c      |   35 +-
  fs/btrfs/tests/free-space-tree-tests.c |  571 ++++++++++++
  fs/btrfs/tests/qgroup-tests.c          |   20 +-
  include/trace/events/btrfs.h           |    3 +-
  16 files changed, 2922 insertions(+), 107 deletions(-)
Quoted 4 lines

create mode 100644 fs/btrfs/free-space-tree.c create mode 100644 fs/btrfs/free-space-tree.h create mode 100644 fs/btrfs/tests/free-space-tree-tests.c

I've tested this in a couple of different VM's and got noticeable performance improvements in both general usage and mount times. I also threw everything I can think of at it (short of attempting to craft filesystem images specifically to break it), and nothing broke, so:

#17 lore raw
Quoted 75 lines · Austin S Hemmelgarn
Quoted 65 lines · Omar Sandoval

Hi, everyone,

I went back and fixed the issues that came up since v2. Changes below. I removed Josef's Reviewed-by on patch 9 because it was completely rewritten to change the mount options like Dave suggested. These are still based on 4.2

Thanks!

Changes from v2->v3:

- Fixed a warning in the free space tree sanity tests caught by Zhao Lei.
- Moved the addition of a block group to the free space tree to occur either on the first attempt to modify the free space for the block group or in btrfs_create_pending_block_groups(), whichever happens first. This avoids a deadlock (lock recursion) when modifying the free space tree requires allocating a new block group. In order to do this, it was simpler to change the on-disk semantics: the superblock stripes will now appear to be free space according to the free space tree, but load_free_space_tree() will still exclude them when building the in-memory free space cache.
- Changed the free_space_tree option to space_cache=v2 and made clear_cache clear the free space tree. If the free space tree has been created, the mount will fail unless space_cache=v2 or nospace_cache,clear_cache is given because we cannot allow the free space tree to get out of date.
- Did a once-over of the code and caught a couple of error handling typos.

v2: http://www.spinics.net/lists/linux-btrfs/msg46796.html

Changes from v1->v2:

- Cleaned up a bunch of unnecessary instances of "if (ret) goto out; ret = 0"
- Added aborts in the free space tree code closer to the site the error is
encountered: where we add or remove block groups, add or remove free space, and also when we convert formats
- Moved loading of the free space tree into caching_thread() and added a new patch 3 in preparation for it
- Commented a bunch of stuff in the extent buffer bitmap operations and refactored some of the complicated logic

v1: http://www.spinics.net/lists/linux-btrfs/msg46713.html

Omar Sandoval (9):
Btrfs: add extent buffer bitmap operations
Btrfs: add extent buffer bitmap sanity tests
Btrfs: add helpers for read-only compat bits
Btrfs: refactor caching_thread()
Btrfs: introduce the free space B-tree on-disk format
Btrfs: implement the free space B-tree
Btrfs: add free space tree sanity tests
Btrfs: wire up the free space tree to the extent tree
Btrfs: add free space tree mount option

 fs/btrfs/Makefile                      |    5 +-
 fs/btrfs/ctree.h                       |  157 +++-
 fs/btrfs/disk-io.c                     |   38 +
 fs/btrfs/extent-tree.c                 |   98 +-
 fs/btrfs/extent_io.c                   |  183 +++-
 fs/btrfs/extent_io.h                   |   10 +-
 fs/btrfs/free-space-tree.c             | 1581 ++++++++++++++++++++++++++++++++
 fs/btrfs/free-space-tree.h             |   72 ++
 fs/btrfs/super.c                       |   56 +-
 fs/btrfs/tests/btrfs-tests.c           |   52 ++
 fs/btrfs/tests/btrfs-tests.h           |   10 +
 fs/btrfs/tests/extent-io-tests.c       |  138 ++-
Quoted 9 lines
 fs/btrfs/tests/free-space-tests.c      |   35 +-
 fs/btrfs/tests/free-space-tree-tests.c |  571 ++++++++++++
 fs/btrfs/tests/qgroup-tests.c          |   20 +-
 include/trace/events/btrfs.h           |    3 +-
 16 files changed, 2922 insertions(+), 107 deletions(-)
 create mode 100644 fs/btrfs/free-space-tree.c
 create mode 100644 fs/btrfs/free-space-tree.h
 create mode 100644 fs/btrfs/tests/free-space-tree-tests.c
Quoted 7 lines

I've tested this in a couple of different VM's and got noticeable performance improvements in both general usage and mount times. I also threw everything I can think of at it (short of attempting to craft filesystem images specifically to break it), and nothing broke, so:

Thank you for trying this out, I really appreciate it.

Signature · 1 line
Omar