* [PATCH v4 1/9] Btrfs: add extent buffer bitmap operations
2015-09-30 3:50 [PATCH v4 0/9] Btrfs: free space B-tree Omar Sandoval
@ 2015-09-30 3:50 ` Omar Sandoval
2015-09-30 3:50 ` [PATCH v4 2/9] Btrfs: add extent buffer bitmap sanity tests Omar Sandoval
` (10 subsequent siblings)
11 siblings, 0 replies; 27+ messages in thread
From: Omar Sandoval @ 2015-09-30 3:50 UTC (permalink / raw)
To: linux-btrfs; +Cc: Omar Sandoval
From: Omar Sandoval <osandov@fb.com>
These are going to be used for the free space tree bitmap items.
Signed-off-by: Omar Sandoval <osandov@fb.com>
---
fs/btrfs/extent_io.c | 149 +++++++++++++++++++++++++++++++++++++++++++++++++++
fs/btrfs/extent_io.h | 6 +++
2 files changed, 155 insertions(+)
diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index e2357e31609a..798a5ee3bd18 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -5524,6 +5524,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;
diff --git a/fs/btrfs/extent_io.h b/fs/btrfs/extent_io.h
index c668f36898d3..9185a20081d7 100644
--- a/fs/btrfs/extent_io.h
+++ b/fs/btrfs/extent_io.h
@@ -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);
--
2.6.0
^ permalink raw reply related [flat|nested] 27+ messages in thread* [PATCH v4 2/9] Btrfs: add extent buffer bitmap sanity tests
2015-09-30 3:50 [PATCH v4 0/9] Btrfs: free space B-tree Omar Sandoval
2015-09-30 3:50 ` [PATCH v4 1/9] Btrfs: add extent buffer bitmap operations Omar Sandoval
@ 2015-09-30 3:50 ` Omar Sandoval
2015-09-30 3:50 ` [PATCH v4 3/9] Btrfs: add helpers for read-only compat bits Omar Sandoval
` (9 subsequent siblings)
11 siblings, 0 replies; 27+ messages in thread
From: Omar Sandoval @ 2015-09-30 3:50 UTC (permalink / raw)
To: linux-btrfs; +Cc: Omar Sandoval
From: Omar Sandoval <osandov@fb.com>
Sanity test the extent buffer bitmap operations (test, set, and clear)
against the equivalent standard kernel operations.
Signed-off-by: Omar Sandoval <osandov@fb.com>
---
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(-)
diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 798a5ee3bd18..2c8eafcec03f 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -4727,24 +4727,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)
@@ -4767,6 +4757,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;
diff --git a/fs/btrfs/extent_io.h b/fs/btrfs/extent_io.h
index 9185a20081d7..9f8d7d1a7015 100644
--- a/fs/btrfs/extent_io.h
+++ b/fs/btrfs/extent_io.h
@@ -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);
diff --git a/fs/btrfs/tests/extent-io-tests.c b/fs/btrfs/tests/extent-io-tests.c
index 9e9f2368177d..71ab575e7633 100644
--- a/fs/btrfs/tests/extent-io-tests.c
+++ b/fs/btrfs/tests/extent-io-tests.c
@@ -18,6 +18,7 @@
#include <linux/pagemap.h>
#include <linux/sched.h>
+#include <linux/slab.h>
#include "btrfs-tests.h"
#include "../extent_io.h"
@@ -76,6 +77,8 @@ static int test_find_delalloc(void)
u64 found;
int ret = -EINVAL;
+ test_msg("Running find delalloc tests\n");
+
inode = btrfs_new_test_inode();
if (!inode) {
test_msg("Failed to allocate test inode\n");
@@ -268,8 +271,139 @@ out:
return ret;
}
+static int __test_eb_bitmaps(unsigned long *bitmap, struct extent_buffer *eb,
+ unsigned long len)
+{
+ unsigned long i, x;
+
+ memset(bitmap, 0, len);
+ memset_extent_buffer(eb, 0, 0, len);
+ if (memcmp_extent_buffer(eb, bitmap, 0, len) != 0) {
+ test_msg("Bitmap was not zeroed\n");
+ return -EINVAL;
+ }
+
+ bitmap_set(bitmap, 0, len * BITS_PER_BYTE);
+ extent_buffer_bitmap_set(eb, 0, 0, len * BITS_PER_BYTE);
+ if (memcmp_extent_buffer(eb, bitmap, 0, len) != 0) {
+ test_msg("Setting all bits failed\n");
+ return -EINVAL;
+ }
+
+ bitmap_clear(bitmap, 0, len * BITS_PER_BYTE);
+ extent_buffer_bitmap_clear(eb, 0, 0, len * BITS_PER_BYTE);
+ if (memcmp_extent_buffer(eb, bitmap, 0, len) != 0) {
+ test_msg("Clearing all bits failed\n");
+ return -EINVAL;
+ }
+
+ bitmap_set(bitmap, (PAGE_CACHE_SIZE - sizeof(long) / 2) * BITS_PER_BYTE,
+ sizeof(long) * BITS_PER_BYTE);
+ extent_buffer_bitmap_set(eb, PAGE_CACHE_SIZE - sizeof(long) / 2, 0,
+ sizeof(long) * BITS_PER_BYTE);
+ if (memcmp_extent_buffer(eb, bitmap, 0, len) != 0) {
+ test_msg("Setting straddling pages failed\n");
+ return -EINVAL;
+ }
+
+ bitmap_set(bitmap, 0, len * BITS_PER_BYTE);
+ bitmap_clear(bitmap,
+ (PAGE_CACHE_SIZE - sizeof(long) / 2) * BITS_PER_BYTE,
+ sizeof(long) * BITS_PER_BYTE);
+ extent_buffer_bitmap_set(eb, 0, 0, len * BITS_PER_BYTE);
+ extent_buffer_bitmap_clear(eb, PAGE_CACHE_SIZE - sizeof(long) / 2, 0,
+ sizeof(long) * BITS_PER_BYTE);
+ if (memcmp_extent_buffer(eb, bitmap, 0, len) != 0) {
+ test_msg("Clearing straddling pages failed\n");
+ return -EINVAL;
+ }
+
+ /*
+ * Generate a wonky pseudo-random bit pattern for the sake of not using
+ * something repetitive that could miss some hypothetical off-by-n bug.
+ */
+ x = 0;
+ for (i = 0; i < len / sizeof(long); i++) {
+ x = (0x19660dULL * (u64)x + 0x3c6ef35fULL) & 0xffffffffUL;
+ bitmap[i] = x;
+ }
+ write_extent_buffer(eb, bitmap, 0, len);
+
+ for (i = 0; i < len * BITS_PER_BYTE; i++) {
+ int bit, bit1;
+
+ bit = !!test_bit(i, bitmap);
+ bit1 = !!extent_buffer_test_bit(eb, 0, i);
+ if (bit1 != bit) {
+ test_msg("Testing bit pattern failed\n");
+ return -EINVAL;
+ }
+
+ bit1 = !!extent_buffer_test_bit(eb, i / BITS_PER_BYTE,
+ i % BITS_PER_BYTE);
+ if (bit1 != bit) {
+ test_msg("Testing bit pattern with offset failed\n");
+ return -EINVAL;
+ }
+ }
+
+ return 0;
+}
+
+static int test_eb_bitmaps(void)
+{
+ unsigned long len = PAGE_CACHE_SIZE * 4;
+ unsigned long *bitmap;
+ struct extent_buffer *eb;
+ int ret;
+
+ test_msg("Running extent buffer bitmap tests\n");
+
+ bitmap = kmalloc(len, GFP_NOFS);
+ if (!bitmap) {
+ test_msg("Couldn't allocate test bitmap\n");
+ return -ENOMEM;
+ }
+
+ eb = __alloc_dummy_extent_buffer(NULL, 0, len);
+ if (!eb) {
+ test_msg("Couldn't allocate test extent buffer\n");
+ kfree(bitmap);
+ return -ENOMEM;
+ }
+
+ ret = __test_eb_bitmaps(bitmap, eb, len);
+ if (ret)
+ goto out;
+
+ /* Do it over again with an extent buffer which isn't page-aligned. */
+ free_extent_buffer(eb);
+ eb = __alloc_dummy_extent_buffer(NULL, PAGE_CACHE_SIZE / 2, len);
+ if (!eb) {
+ test_msg("Couldn't allocate test extent buffer\n");
+ kfree(bitmap);
+ return -ENOMEM;
+ }
+
+ ret = __test_eb_bitmaps(bitmap, eb, len);
+out:
+ free_extent_buffer(eb);
+ kfree(bitmap);
+ return ret;
+}
+
int btrfs_test_extent_io(void)
{
- test_msg("Running find delalloc tests\n");
- return test_find_delalloc();
+ int ret;
+
+ test_msg("Running extent I/O tests\n");
+
+ ret = test_find_delalloc();
+ if (ret)
+ goto out;
+
+ ret = test_eb_bitmaps();
+out:
+ test_msg("Extent I/O tests finished\n");
+ return ret;
}
--
2.6.0
^ permalink raw reply related [flat|nested] 27+ messages in thread* [PATCH v4 3/9] Btrfs: add helpers for read-only compat bits
2015-09-30 3:50 [PATCH v4 0/9] Btrfs: free space B-tree Omar Sandoval
2015-09-30 3:50 ` [PATCH v4 1/9] Btrfs: add extent buffer bitmap operations Omar Sandoval
2015-09-30 3:50 ` [PATCH v4 2/9] Btrfs: add extent buffer bitmap sanity tests Omar Sandoval
@ 2015-09-30 3:50 ` Omar Sandoval
2015-09-30 3:50 ` [PATCH v4 4/9] Btrfs: refactor caching_thread() Omar Sandoval
` (8 subsequent siblings)
11 siblings, 0 replies; 27+ messages in thread
From: Omar Sandoval @ 2015-09-30 3:50 UTC (permalink / raw)
To: linux-btrfs; +Cc: Omar Sandoval
From: Omar Sandoval <osandov@fb.com>
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.
Reviewed-by: Josef Bacik <jbacik@fb.com>
Signed-off-by: Omar Sandoval <osandov@fb.com>
---
fs/btrfs/ctree.h | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 82 insertions(+)
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 938efe33be80..42c41dc68cbb 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -4100,6 +4100,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)
@@ -4110,6 +4134,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.
--
2.6.0
^ permalink raw reply related [flat|nested] 27+ messages in thread* [PATCH v4 4/9] Btrfs: refactor caching_thread()
2015-09-30 3:50 [PATCH v4 0/9] Btrfs: free space B-tree Omar Sandoval
` (2 preceding siblings ...)
2015-09-30 3:50 ` [PATCH v4 3/9] Btrfs: add helpers for read-only compat bits Omar Sandoval
@ 2015-09-30 3:50 ` Omar Sandoval
2015-09-30 3:50 ` [PATCH v4 5/9] Btrfs: introduce the free space B-tree on-disk format Omar Sandoval
` (7 subsequent siblings)
11 siblings, 0 replies; 27+ messages in thread
From: Omar Sandoval @ 2015-09-30 3:50 UTC (permalink / raw)
To: linux-btrfs; +Cc: Omar Sandoval
From: Omar Sandoval <osandov@fb.com>
We're also going to load the free space tree from caching_thread(), so
we should refactor some of the common code.
Signed-off-by: Omar Sandoval <osandov@fb.com>
---
fs/btrfs/ctree.h | 3 +++
fs/btrfs/extent-tree.c | 59 ++++++++++++++++++++++++++++----------------------
2 files changed, 36 insertions(+), 26 deletions(-)
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 42c41dc68cbb..60df67efef96 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -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;
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 9f9604201333..24f95299efe9 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -375,11 +375,10 @@ static u64 add_new_free_space(struct btrfs_block_group_cache *block_group,
return total_added;
}
-static noinline void caching_thread(struct btrfs_work *work)
+static int load_extent_tree_free(struct btrfs_caching_control *caching_ctl)
{
struct btrfs_block_group_cache *block_group;
struct btrfs_fs_info *fs_info;
- struct btrfs_caching_control *caching_ctl;
struct btrfs_root *extent_root;
struct btrfs_path *path;
struct extent_buffer *leaf;
@@ -387,16 +386,15 @@ static noinline void caching_thread(struct btrfs_work *work)
u64 total_found = 0;
u64 last = 0;
u32 nritems;
- int ret = -ENOMEM;
+ int ret;
- caching_ctl = container_of(work, struct btrfs_caching_control, work);
block_group = caching_ctl->block_group;
fs_info = block_group->fs_info;
extent_root = fs_info->extent_root;
path = btrfs_alloc_path();
if (!path)
- goto out;
+ return -ENOMEM;
last = max_t(u64, block_group->key.objectid, BTRFS_SUPER_INFO_OFFSET);
@@ -413,15 +411,11 @@ static noinline void caching_thread(struct btrfs_work *work)
key.objectid = last;
key.offset = 0;
key.type = BTRFS_EXTENT_ITEM_KEY;
-again:
- mutex_lock(&caching_ctl->mutex);
- /* need to make sure the commit_root doesn't disappear */
- down_read(&fs_info->commit_root_sem);
next:
ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
if (ret < 0)
- goto err;
+ goto out;
leaf = path->nodes[0];
nritems = btrfs_header_nritems(leaf);
@@ -446,12 +440,14 @@ next:
up_read(&fs_info->commit_root_sem);
mutex_unlock(&caching_ctl->mutex);
cond_resched();
- goto again;
+ mutex_lock(&caching_ctl->mutex);
+ down_read(&fs_info->commit_root_sem);
+ goto next;
}
ret = btrfs_next_leaf(extent_root, path);
if (ret < 0)
- goto err;
+ goto out;
if (ret)
break;
leaf = path->nodes[0];
@@ -489,7 +485,7 @@ next:
else
last = key.objectid + key.offset;
- if (total_found > (1024 * 1024 * 2)) {
+ if (total_found > CACHING_CTL_WAKE_UP) {
total_found = 0;
wake_up(&caching_ctl->wait);
}
@@ -503,25 +499,36 @@ next:
block_group->key.offset);
caching_ctl->progress = (u64)-1;
+out:
+ btrfs_free_path(path);
+ return ret;
+}
+
+static noinline void caching_thread(struct btrfs_work *work)
+{
+ struct btrfs_block_group_cache *block_group;
+ struct btrfs_fs_info *fs_info;
+ struct btrfs_caching_control *caching_ctl;
+ int ret;
+
+ caching_ctl = container_of(work, struct btrfs_caching_control, work);
+ block_group = caching_ctl->block_group;
+ fs_info = block_group->fs_info;
+
+ mutex_lock(&caching_ctl->mutex);
+ down_read(&fs_info->commit_root_sem);
+
+ ret = load_extent_tree_free(caching_ctl);
+
spin_lock(&block_group->lock);
block_group->caching_ctl = NULL;
- block_group->cached = BTRFS_CACHE_FINISHED;
+ block_group->cached = ret ? BTRFS_CACHE_ERROR : BTRFS_CACHE_FINISHED;
spin_unlock(&block_group->lock);
-err:
- btrfs_free_path(path);
up_read(&fs_info->commit_root_sem);
-
- free_excluded_extents(extent_root, block_group);
-
+ free_excluded_extents(fs_info->extent_root, block_group);
mutex_unlock(&caching_ctl->mutex);
-out:
- if (ret) {
- spin_lock(&block_group->lock);
- block_group->caching_ctl = NULL;
- block_group->cached = BTRFS_CACHE_ERROR;
- spin_unlock(&block_group->lock);
- }
+
wake_up(&caching_ctl->wait);
put_caching_control(caching_ctl);
--
2.6.0
^ permalink raw reply related [flat|nested] 27+ messages in thread* [PATCH v4 5/9] Btrfs: introduce the free space B-tree on-disk format
2015-09-30 3:50 [PATCH v4 0/9] Btrfs: free space B-tree Omar Sandoval
` (3 preceding siblings ...)
2015-09-30 3:50 ` [PATCH v4 4/9] Btrfs: refactor caching_thread() Omar Sandoval
@ 2015-09-30 3:50 ` Omar Sandoval
2015-09-30 3:50 ` [PATCH v4 6/9] Btrfs: implement the free space B-tree Omar Sandoval
` (6 subsequent siblings)
11 siblings, 0 replies; 27+ messages in thread
From: Omar Sandoval @ 2015-09-30 3:50 UTC (permalink / raw)
To: linux-btrfs; +Cc: Omar Sandoval
From: Omar Sandoval <osandov@fb.com>
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.
Reviewed-by: Josef Bacik <jbacik@fb.com>
Signed-off-by: Omar Sandoval <osandov@fb.com>
---
fs/btrfs/ctree.h | 38 ++++++++++++++++++++++++++++++++++++++
include/trace/events/btrfs.h | 3 ++-
2 files changed, 40 insertions(+), 1 deletion(-)
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 60df67efef96..0e40d323f4e9 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -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)
{
@@ -2058,6 +2070,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
@@ -2458,6 +2491,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);
diff --git a/include/trace/events/btrfs.h b/include/trace/events/btrfs.h
index 0b73af9be12f..e6289e62a2a8 100644
--- a/include/trace/events/btrfs.h
+++ b/include/trace/events/btrfs.h
@@ -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) \
--
2.6.0
^ permalink raw reply related [flat|nested] 27+ messages in thread* [PATCH v4 6/9] Btrfs: implement the free space B-tree
2015-09-30 3:50 [PATCH v4 0/9] Btrfs: free space B-tree Omar Sandoval
` (4 preceding siblings ...)
2015-09-30 3:50 ` [PATCH v4 5/9] Btrfs: introduce the free space B-tree on-disk format Omar Sandoval
@ 2015-09-30 3:50 ` Omar Sandoval
2015-09-30 4:35 ` kbuild test robot
` (4 more replies)
2015-09-30 3:50 ` [PATCH v4 7/9] Btrfs: add free space tree sanity tests Omar Sandoval
` (5 subsequent siblings)
11 siblings, 5 replies; 27+ messages in thread
From: Omar Sandoval @ 2015-09-30 3:50 UTC (permalink / raw)
To: linux-btrfs; +Cc: Omar Sandoval
From: Omar Sandoval <osandov@fb.com>
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.
Signed-off-by: Omar Sandoval <osandov@fb.com>
---
fs/btrfs/Makefile | 2 +-
fs/btrfs/ctree.h | 27 +-
fs/btrfs/extent-tree.c | 5 +-
fs/btrfs/free-space-tree.c | 1584 ++++++++++++++++++++++++++++++++++++++++++++
fs/btrfs/free-space-tree.h | 72 ++
5 files changed, 1686 insertions(+), 4 deletions(-)
create mode 100644 fs/btrfs/free-space-tree.c
create mode 100644 fs/btrfs/free-space-tree.h
diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
index 6d1d0b93b1aa..766169709146 100644
--- a/fs/btrfs/Makefile
+++ b/fs/btrfs/Makefile
@@ -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
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 0e40d323f4e9..0888c3e2cc7d 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -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;
@@ -3555,6 +3577,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);
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 24f95299efe9..a3b84ee8a28d 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -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;
@@ -9377,6 +9377,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;
}
diff --git a/fs/btrfs/free-space-tree.c b/fs/btrfs/free-space-tree.c
new file mode 100644
index 000000000000..cbe36dd0d97b
--- /dev/null
+++ b/fs/btrfs/free-space-tree.c
@@ -0,0 +1,1584 @@
+/*
+ * 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.
+ */
+
+#include <linux/kernel.h>
+#include <linux/vmalloc.h>
+#include "ctree.h"
+#include "disk-io.h"
+#include "locking.h"
+#include "free-space-tree.h"
+#include "transaction.h"
+
+static int __add_block_group_free_space(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path);
+
+void set_free_space_tree_thresholds(struct btrfs_block_group_cache *cache)
+{
+ u32 bitmap_range;
+ size_t bitmap_size;
+ u64 num_bitmaps, total_bitmap_size;
+
+ /*
+ * We convert to bitmaps when the disk space required for using extents
+ * exceeds that required for using bitmaps.
+ */
+ bitmap_range = cache->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
+ num_bitmaps = div_u64(cache->key.offset + bitmap_range - 1,
+ bitmap_range);
+ bitmap_size = sizeof(struct btrfs_item) + BTRFS_FREE_SPACE_BITMAP_SIZE;
+ total_bitmap_size = num_bitmaps * bitmap_size;
+ cache->bitmap_high_thresh = div_u64(total_bitmap_size,
+ sizeof(struct btrfs_item));
+
+ /*
+ * We allow for a small buffer between the high threshold and low
+ * threshold to avoid thrashing back and forth between the two formats.
+ */
+ if (cache->bitmap_high_thresh > 100)
+ cache->bitmap_low_thresh = cache->bitmap_high_thresh - 100;
+ else
+ cache->bitmap_low_thresh = 0;
+}
+
+static int add_new_free_space_info(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path)
+{
+ struct btrfs_root *root = fs_info->free_space_root;
+ struct btrfs_free_space_info *info;
+ struct btrfs_key key;
+ struct extent_buffer *leaf;
+ int ret;
+
+ key.objectid = block_group->key.objectid;
+ key.type = BTRFS_FREE_SPACE_INFO_KEY;
+ key.offset = block_group->key.offset;
+
+ ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*info));
+ if (ret)
+ goto out;
+
+ leaf = path->nodes[0];
+ info = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_free_space_info);
+ btrfs_set_free_space_extent_count(leaf, info, 0);
+ btrfs_set_free_space_flags(leaf, info, 0);
+ btrfs_mark_buffer_dirty(leaf);
+
+ ret = 0;
+out:
+ btrfs_release_path(path);
+ return ret;
+}
+
+struct btrfs_free_space_info *
+search_free_space_info(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path, int cow)
+{
+ struct btrfs_root *root = fs_info->free_space_root;
+ struct btrfs_key key;
+ int ret;
+
+ key.objectid = block_group->key.objectid;
+ key.type = BTRFS_FREE_SPACE_INFO_KEY;
+ key.offset = block_group->key.offset;
+
+ ret = btrfs_search_slot(trans, root, &key, path, 0, cow);
+ if (ret < 0)
+ return ERR_PTR(ret);
+ if (ret != 0) {
+ btrfs_warn(fs_info, "missing free space info for %llu\n",
+ block_group->key.objectid);
+ ASSERT(0);
+ return ERR_PTR(-ENOENT);
+ }
+
+ return btrfs_item_ptr(path->nodes[0], path->slots[0],
+ struct btrfs_free_space_info);
+}
+
+/*
+ * btrfs_search_slot() but we're looking for the greatest key less than the
+ * passed key.
+ */
+static int btrfs_search_prev_slot(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_key *key, struct btrfs_path *p,
+ int ins_len, int cow)
+{
+ int ret;
+
+ ret = btrfs_search_slot(trans, root, key, p, ins_len, cow);
+ if (ret < 0)
+ return ret;
+
+ if (ret == 0) {
+ ASSERT(0);
+ return -EIO;
+ }
+
+ if (p->slots[0] == 0) {
+ ASSERT(0);
+ return -EIO;
+ }
+ p->slots[0]--;
+
+ return 0;
+}
+
+static inline u32 free_space_bitmap_size(u64 size, u32 sectorsize)
+{
+ return DIV_ROUND_UP((u32)div_u64(size, sectorsize), BITS_PER_BYTE);
+}
+
+static unsigned long *alloc_bitmap(u32 bitmap_size)
+{
+ return __vmalloc(bitmap_size, GFP_NOFS | __GFP_HIGHMEM | __GFP_ZERO,
+ PAGE_KERNEL);
+}
+
+int convert_free_space_to_bitmaps(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path)
+{
+ struct btrfs_root *root = fs_info->free_space_root;
+ struct btrfs_free_space_info *info;
+ struct btrfs_key key, found_key;
+ struct extent_buffer *leaf;
+ unsigned long *bitmap;
+ char *bitmap_cursor;
+ u64 start, end;
+ u64 bitmap_range, i;
+ u32 bitmap_size, flags, expected_extent_count;
+ u32 extent_count = 0;
+ int done = 0, nr;
+ int ret;
+
+ bitmap_size = free_space_bitmap_size(block_group->key.offset,
+ block_group->sectorsize);
+ bitmap = alloc_bitmap(bitmap_size);
+ if (!bitmap) {
+ ret = -ENOMEM;
+ goto out;
+ }
+
+ start = block_group->key.objectid;
+ end = block_group->key.objectid + block_group->key.offset;
+
+ key.objectid = end - 1;
+ key.type = (u8)-1;
+ key.offset = (u64)-1;
+
+ while (!done) {
+ ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
+ if (ret)
+ goto out;
+
+ leaf = path->nodes[0];
+ nr = 0;
+ path->slots[0]++;
+ while (path->slots[0] > 0) {
+ btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
+
+ if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
+ ASSERT(found_key.objectid == block_group->key.objectid);
+ ASSERT(found_key.offset == block_group->key.offset);
+ done = 1;
+ break;
+ } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY) {
+ u64 first, last;
+
+ ASSERT(found_key.objectid >= start);
+ ASSERT(found_key.objectid < end);
+ ASSERT(found_key.objectid + found_key.offset <= end);
+
+ first = div_u64(found_key.objectid - start,
+ block_group->sectorsize);
+ last = div_u64(found_key.objectid + found_key.offset - start,
+ block_group->sectorsize);
+ bitmap_set(bitmap, first, last - first);
+
+ extent_count++;
+ nr++;
+ path->slots[0]--;
+ } else {
+ ASSERT(0);
+ }
+ }
+
+ ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
+ if (ret)
+ goto out;
+ btrfs_release_path(path);
+ }
+
+ info = search_free_space_info(trans, fs_info, block_group, path, 1);
+ if (IS_ERR(info)) {
+ ret = PTR_ERR(info);
+ goto out;
+ }
+ leaf = path->nodes[0];
+ flags = btrfs_free_space_flags(leaf, info);
+ flags |= BTRFS_FREE_SPACE_USING_BITMAPS;
+ btrfs_set_free_space_flags(leaf, info, flags);
+ expected_extent_count = btrfs_free_space_extent_count(leaf, info);
+ btrfs_mark_buffer_dirty(leaf);
+ btrfs_release_path(path);
+
+ if (extent_count != expected_extent_count) {
+ btrfs_err(fs_info, "incorrect extent count for %llu; counted %u, expected %u",
+ block_group->key.objectid, extent_count,
+ expected_extent_count);
+ ASSERT(0);
+ ret = -EIO;
+ goto out;
+ }
+
+ bitmap_cursor = (char *)bitmap;
+ bitmap_range = block_group->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
+ i = start;
+ while (i < end) {
+ unsigned long ptr;
+ u64 extent_size;
+ u32 data_size;
+
+ extent_size = min(end - i, bitmap_range);
+ data_size = free_space_bitmap_size(extent_size,
+ block_group->sectorsize);
+
+ key.objectid = i;
+ key.type = BTRFS_FREE_SPACE_BITMAP_KEY;
+ key.offset = extent_size;
+
+ ret = btrfs_insert_empty_item(trans, root, path, &key,
+ data_size);
+ if (ret)
+ goto out;
+
+ leaf = path->nodes[0];
+ ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
+ write_extent_buffer(leaf, bitmap_cursor, ptr,
+ data_size);
+ btrfs_mark_buffer_dirty(leaf);
+ btrfs_release_path(path);
+
+ i += extent_size;
+ bitmap_cursor += data_size;
+ }
+
+ ret = 0;
+out:
+ vfree(bitmap);
+ if (ret)
+ btrfs_abort_transaction(trans, root, ret);
+ return ret;
+}
+
+int convert_free_space_to_extents(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path)
+{
+ struct btrfs_root *root = fs_info->free_space_root;
+ struct btrfs_free_space_info *info;
+ struct btrfs_key key, found_key;
+ struct extent_buffer *leaf;
+ unsigned long *bitmap;
+ u64 start, end;
+ /* Initialize to silence GCC. */
+ u64 extent_start = 0;
+ u64 offset;
+ u32 bitmap_size, flags, expected_extent_count;
+ int prev_bit = 0, bit, bitnr;
+ u32 extent_count = 0;
+ int done = 0, nr;
+ int ret;
+
+ bitmap_size = free_space_bitmap_size(block_group->key.offset,
+ block_group->sectorsize);
+ bitmap = alloc_bitmap(bitmap_size);
+ if (!bitmap) {
+ ret = -ENOMEM;
+ goto out;
+ }
+
+ start = block_group->key.objectid;
+ end = block_group->key.objectid + block_group->key.offset;
+
+ key.objectid = end - 1;
+ key.type = (u8)-1;
+ key.offset = (u64)-1;
+
+ while (!done) {
+ ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
+ if (ret)
+ goto out;
+
+ leaf = path->nodes[0];
+ nr = 0;
+ path->slots[0]++;
+ while (path->slots[0] > 0) {
+ btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
+
+ if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
+ ASSERT(found_key.objectid == block_group->key.objectid);
+ ASSERT(found_key.offset == block_group->key.offset);
+ done = 1;
+ break;
+ } else if (found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
+ unsigned long ptr;
+ char *bitmap_cursor;
+ u32 bitmap_pos, data_size;
+
+ ASSERT(found_key.objectid >= start);
+ ASSERT(found_key.objectid < end);
+ ASSERT(found_key.objectid + found_key.offset <= end);
+
+ bitmap_pos = div_u64(found_key.objectid - start,
+ block_group->sectorsize *
+ BITS_PER_BYTE);
+ bitmap_cursor = ((char *)bitmap) + bitmap_pos;
+ data_size = free_space_bitmap_size(found_key.offset,
+ block_group->sectorsize);
+
+ ptr = btrfs_item_ptr_offset(leaf, path->slots[0] - 1);
+ read_extent_buffer(leaf, bitmap_cursor, ptr,
+ data_size);
+
+ nr++;
+ path->slots[0]--;
+ } else {
+ ASSERT(0);
+ }
+ }
+
+ ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
+ if (ret)
+ goto out;
+ btrfs_release_path(path);
+ }
+
+ info = search_free_space_info(trans, fs_info, block_group, path, 1);
+ if (IS_ERR(info)) {
+ ret = PTR_ERR(info);
+ goto out;
+ }
+ leaf = path->nodes[0];
+ flags = btrfs_free_space_flags(leaf, info);
+ flags &= ~BTRFS_FREE_SPACE_USING_BITMAPS;
+ btrfs_set_free_space_flags(leaf, info, flags);
+ expected_extent_count = btrfs_free_space_extent_count(leaf, info);
+ btrfs_mark_buffer_dirty(leaf);
+ btrfs_release_path(path);
+
+ offset = start;
+ bitnr = 0;
+ while (offset < end) {
+ bit = !!test_bit(bitnr, bitmap);
+ if (prev_bit == 0 && bit == 1) {
+ extent_start = offset;
+ } else if (prev_bit == 1 && bit == 0) {
+ key.objectid = extent_start;
+ key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
+ key.offset = offset - extent_start;
+
+ ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
+ if (ret)
+ goto out;
+ btrfs_release_path(path);
+
+ extent_count++;
+ }
+ prev_bit = bit;
+ offset += block_group->sectorsize;
+ bitnr++;
+ }
+ if (prev_bit == 1) {
+ key.objectid = extent_start;
+ key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
+ key.offset = end - extent_start;
+
+ ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
+ if (ret)
+ goto out;
+ btrfs_release_path(path);
+
+ extent_count++;
+ }
+
+ if (extent_count != expected_extent_count) {
+ btrfs_err(fs_info, "incorrect extent count for %llu; counted %u, expected %u",
+ block_group->key.objectid, extent_count,
+ expected_extent_count);
+ ASSERT(0);
+ ret = -EIO;
+ goto out;
+ }
+
+ ret = 0;
+out:
+ vfree(bitmap);
+ if (ret)
+ btrfs_abort_transaction(trans, root, ret);
+ return ret;
+}
+
+static int update_free_space_extent_count(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path,
+ int new_extents)
+{
+ struct btrfs_free_space_info *info;
+ u32 flags;
+ u32 extent_count;
+ int ret = 0;
+
+ if (new_extents == 0)
+ return 0;
+
+ info = search_free_space_info(trans, fs_info, block_group, path, 1);
+ if (IS_ERR(info)) {
+ ret = PTR_ERR(info);
+ goto out;
+ }
+ flags = btrfs_free_space_flags(path->nodes[0], info);
+ extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
+
+ extent_count += new_extents;
+ btrfs_set_free_space_extent_count(path->nodes[0], info, extent_count);
+ btrfs_mark_buffer_dirty(path->nodes[0]);
+ btrfs_release_path(path);
+
+ if (!(flags & BTRFS_FREE_SPACE_USING_BITMAPS) &&
+ extent_count > block_group->bitmap_high_thresh) {
+ ret = convert_free_space_to_bitmaps(trans, fs_info, block_group,
+ path);
+ } else if ((flags & BTRFS_FREE_SPACE_USING_BITMAPS) &&
+ extent_count < block_group->bitmap_low_thresh) {
+ ret = convert_free_space_to_extents(trans, fs_info, block_group,
+ path);
+ }
+
+out:
+ return ret;
+}
+
+int free_space_test_bit(struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path, u64 offset)
+{
+ struct extent_buffer *leaf;
+ struct btrfs_key key;
+ u64 found_start, found_end;
+ unsigned long ptr, i;
+
+ leaf = path->nodes[0];
+ btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
+ ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
+
+ found_start = key.objectid;
+ found_end = key.objectid + key.offset;
+ ASSERT(offset >= found_start && offset < found_end);
+
+ ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
+ i = div_u64(offset - found_start, block_group->sectorsize);
+ return !!extent_buffer_test_bit(leaf, ptr, i);
+}
+
+static void free_space_set_bits(struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path, u64 *start, u64 *size,
+ int bit)
+{
+ struct extent_buffer *leaf;
+ struct btrfs_key key;
+ u64 end = *start + *size;
+ u64 found_start, found_end;
+ unsigned long ptr, first, last;
+
+ leaf = path->nodes[0];
+ btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
+ ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
+
+ found_start = key.objectid;
+ found_end = key.objectid + key.offset;
+ ASSERT(*start >= found_start && *start < found_end);
+ ASSERT(end > found_start);
+
+ if (end > found_end)
+ end = found_end;
+
+ ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
+ first = div_u64(*start - found_start, block_group->sectorsize);
+ last = div_u64(end - found_start, block_group->sectorsize);
+ if (bit)
+ extent_buffer_bitmap_set(leaf, ptr, first, last - first);
+ else
+ extent_buffer_bitmap_clear(leaf, ptr, first, last - first);
+ btrfs_mark_buffer_dirty(leaf);
+
+ *size -= end - *start;
+ *start = end;
+}
+
+/*
+ * We can't use btrfs_next_item() in modify_free_space_bitmap() because
+ * btrfs_next_leaf() doesn't get the path for writing. We can forgo the fancy
+ * tree walking in btrfs_next_leaf() anyways because we know exactly what we're
+ * looking for.
+ */
+static int free_space_next_bitmap(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root, struct btrfs_path *p)
+{
+ struct btrfs_key key;
+
+ if (p->slots[0] + 1 < btrfs_header_nritems(p->nodes[0])) {
+ p->slots[0]++;
+ return 0;
+ }
+
+ btrfs_item_key_to_cpu(p->nodes[0], &key, p->slots[0]);
+ btrfs_release_path(p);
+
+ key.objectid += key.offset;
+ key.type = (u8)-1;
+ key.offset = (u64)-1;
+
+ return btrfs_search_prev_slot(trans, root, &key, p, 0, 1);
+}
+
+/*
+ * If remove is 1, then we are removing free space, thus clearing bits in the
+ * bitmap. If remove is 0, then we are adding free space, thus setting bits in
+ * the bitmap.
+ */
+static int modify_free_space_bitmap(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path,
+ u64 start, u64 size, int remove)
+{
+ struct btrfs_root *root = fs_info->free_space_root;
+ struct btrfs_key key;
+ u64 end = start + size;
+ u64 cur_start, cur_size;
+ int prev_bit, next_bit;
+ int new_extents;
+ int ret;
+
+ /*
+ * Read the bit for the block immediately before the extent of space if
+ * that block is within the block group.
+ */
+ if (start > block_group->key.objectid) {
+ u64 prev_block = start - block_group->sectorsize;
+
+ key.objectid = prev_block;
+ key.type = (u8)-1;
+ key.offset = (u64)-1;
+
+ ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);
+ if (ret)
+ goto out;
+
+ prev_bit = free_space_test_bit(block_group, path, prev_block);
+
+ /* The previous block may have been in the previous bitmap. */
+ btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+ if (start >= key.objectid + key.offset) {
+ ret = free_space_next_bitmap(trans, root, path);
+ if (ret)
+ goto out;
+ }
+ } else {
+ key.objectid = start;
+ key.type = (u8)-1;
+ key.offset = (u64)-1;
+
+ ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);
+ if (ret)
+ goto out;
+
+ prev_bit = -1;
+ }
+
+ /*
+ * Iterate over all of the bitmaps overlapped by the extent of space,
+ * clearing/setting bits as required.
+ */
+ cur_start = start;
+ cur_size = size;
+ while (1) {
+ free_space_set_bits(block_group, path, &cur_start, &cur_size,
+ !remove);
+ if (cur_size == 0)
+ break;
+ ret = free_space_next_bitmap(trans, root, path);
+ if (ret)
+ goto out;
+ }
+
+ /*
+ * Read the bit for the block immediately after the extent of space if
+ * that block is within the block group.
+ */
+ if (end < block_group->key.objectid + block_group->key.offset) {
+ /* The next block may be in the next bitmap. */
+ btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+ if (end >= key.objectid + key.offset) {
+ ret = free_space_next_bitmap(trans, root, path);
+ if (ret)
+ goto out;
+ }
+
+ next_bit = free_space_test_bit(block_group, path, end);
+ } else {
+ next_bit = -1;
+ }
+
+ if (remove) {
+ new_extents = -1;
+ if (prev_bit == 1) {
+ /* Leftover on the left. */
+ new_extents++;
+ }
+ if (next_bit == 1) {
+ /* Leftover on the right. */
+ new_extents++;
+ }
+ } else {
+ new_extents = 1;
+ if (prev_bit == 1) {
+ /* Merging with neighbor on the left. */
+ new_extents--;
+ }
+ if (next_bit == 1) {
+ /* Merging with neighbor on the right. */
+ new_extents--;
+ }
+ }
+
+ btrfs_release_path(path);
+ ret = update_free_space_extent_count(trans, fs_info, block_group, path,
+ new_extents);
+
+out:
+ return ret;
+}
+
+static int remove_free_space_extent(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path,
+ u64 start, u64 size)
+{
+ struct btrfs_root *root = fs_info->free_space_root;
+ struct btrfs_key key;
+ u64 found_start, found_end;
+ u64 end = start + size;
+ int new_extents = -1;
+ int ret;
+
+ key.objectid = start;
+ key.type = (u8)-1;
+ key.offset = (u64)-1;
+
+ ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
+ if (ret)
+ goto out;
+
+ btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+
+ ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);
+
+ found_start = key.objectid;
+ found_end = key.objectid + key.offset;
+ ASSERT(start >= found_start && end <= found_end);
+
+ /*
+ * Okay, now that we've found the free space extent which contains the
+ * free space that we are removing, there are four cases:
+ *
+ * 1. We're using the whole extent: delete the key we found and
+ * decrement the free space extent count.
+ * 2. We are using part of the extent starting at the beginning: delete
+ * the key we found and insert a new key representing the leftover at
+ * the end. There is no net change in the number of extents.
+ * 3. We are using part of the extent ending at the end: delete the key
+ * we found and insert a new key representing the leftover at the
+ * beginning. There is no net change in the number of extents.
+ * 4. We are using part of the extent in the middle: delete the key we
+ * found and insert two new keys representing the leftovers on each
+ * side. Where we used to have one extent, we now have two, so increment
+ * the extent count. We may need to convert the block group to bitmaps
+ * as a result.
+ */
+
+ /* Delete the existing key (cases 1-4). */
+ ret = btrfs_del_item(trans, root, path);
+ if (ret)
+ goto out;
+
+ /* Add a key for leftovers at the beginning (cases 3 and 4). */
+ if (start > found_start) {
+ key.objectid = found_start;
+ key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
+ key.offset = start - found_start;
+
+ btrfs_release_path(path);
+ ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
+ if (ret)
+ goto out;
+ new_extents++;
+ }
+
+ /* Add a key for leftovers at the end (cases 2 and 4). */
+ if (end < found_end) {
+ key.objectid = end;
+ key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
+ key.offset = found_end - end;
+
+ btrfs_release_path(path);
+ ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
+ if (ret)
+ goto out;
+ new_extents++;
+ }
+
+ btrfs_release_path(path);
+ ret = update_free_space_extent_count(trans, fs_info, block_group, path,
+ new_extents);
+
+out:
+ return ret;
+}
+
+int __remove_from_free_space_tree(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path, u64 start, u64 size)
+{
+ struct btrfs_free_space_info *info;
+ u32 flags;
+ int ret;
+
+ if (block_group->needs_free_space) {
+ ret = __add_block_group_free_space(trans, fs_info, block_group,
+ path);
+ if (ret)
+ return ret;
+ }
+
+ info = search_free_space_info(NULL, fs_info, block_group, path, 0);
+ if (IS_ERR(info))
+ return PTR_ERR(info);
+ flags = btrfs_free_space_flags(path->nodes[0], info);
+ btrfs_release_path(path);
+
+ if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
+ return modify_free_space_bitmap(trans, fs_info, block_group,
+ path, start, size, 1);
+ } else {
+ return remove_free_space_extent(trans, fs_info, block_group,
+ path, start, size);
+ }
+}
+
+int remove_from_free_space_tree(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ u64 start, u64 size)
+{
+ struct btrfs_block_group_cache *block_group;
+ struct btrfs_path *path;
+ int ret;
+
+ if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
+ return 0;
+
+ path = btrfs_alloc_path();
+ if (!path) {
+ ret = -ENOMEM;
+ goto out;
+ }
+
+ block_group = btrfs_lookup_block_group(fs_info, start);
+ if (!block_group) {
+ ASSERT(0);
+ ret = -ENOENT;
+ goto out;
+ }
+
+ mutex_lock(&block_group->free_space_lock);
+ ret = __remove_from_free_space_tree(trans, fs_info, block_group, path,
+ start, size);
+ mutex_unlock(&block_group->free_space_lock);
+
+ btrfs_put_block_group(block_group);
+out:
+ btrfs_free_path(path);
+ if (ret)
+ btrfs_abort_transaction(trans, fs_info->free_space_root, ret);
+ return ret;
+}
+
+static int add_free_space_extent(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path,
+ u64 start, u64 size)
+{
+ struct btrfs_root *root = fs_info->free_space_root;
+ struct btrfs_key key, new_key;
+ u64 found_start, found_end;
+ u64 end = start + size;
+ int new_extents = 1;
+ int ret;
+
+ /*
+ * We are adding a new extent of free space, but we need to merge
+ * extents. There are four cases here:
+ *
+ * 1. The new extent does not have any immediate neighbors to merge
+ * with: add the new key and increment the free space extent count. We
+ * may need to convert the block group to bitmaps as a result.
+ * 2. The new extent has an immediate neighbor before it: remove the
+ * previous key and insert a new key combining both of them. There is no
+ * net change in the number of extents.
+ * 3. The new extent has an immediate neighbor after it: remove the next
+ * key and insert a new key combining both of them. There is no net
+ * change in the number of extents.
+ * 4. The new extent has immediate neighbors on both sides: remove both
+ * of the keys and insert a new key combining all of them. Where we used
+ * to have two extents, we now have one, so decrement the extent count.
+ */
+
+ new_key.objectid = start;
+ new_key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
+ new_key.offset = size;
+
+ /* Search for a neighbor on the left. */
+ if (start == block_group->key.objectid)
+ goto right;
+ key.objectid = start - 1;
+ key.type = (u8)-1;
+ key.offset = (u64)-1;
+
+ ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
+ if (ret)
+ goto out;
+
+ btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+
+ if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
+ ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);
+ btrfs_release_path(path);
+ goto right;
+ }
+
+ found_start = key.objectid;
+ found_end = key.objectid + key.offset;
+ ASSERT(found_start >= block_group->key.objectid &&
+ found_end > block_group->key.objectid);
+ ASSERT(found_start < start && found_end <= start);
+
+ /*
+ * Delete the neighbor on the left and absorb it into the new key (cases
+ * 2 and 4).
+ */
+ if (found_end == start) {
+ ret = btrfs_del_item(trans, root, path);
+ if (ret)
+ goto out;
+ new_key.objectid = found_start;
+ new_key.offset += key.offset;
+ new_extents--;
+ }
+ btrfs_release_path(path);
+
+right:
+ /* Search for a neighbor on the right. */
+ if (end == block_group->key.objectid + block_group->key.offset)
+ goto insert;
+ key.objectid = end;
+ key.type = (u8)-1;
+ key.offset = (u64)-1;
+
+ ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
+ if (ret)
+ goto out;
+
+ btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+
+ if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
+ ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);
+ btrfs_release_path(path);
+ goto insert;
+ }
+
+ found_start = key.objectid;
+ found_end = key.objectid + key.offset;
+ ASSERT(found_start >= block_group->key.objectid &&
+ found_end > block_group->key.objectid);
+ ASSERT((found_start < start && found_end <= start) ||
+ (found_start >= end && found_end > end));
+
+ /*
+ * Delete the neighbor on the right and absorb it into the new key
+ * (cases 3 and 4).
+ */
+ if (found_start == end) {
+ ret = btrfs_del_item(trans, root, path);
+ if (ret)
+ goto out;
+ new_key.offset += key.offset;
+ new_extents--;
+ }
+ btrfs_release_path(path);
+
+insert:
+ /* Insert the new key (cases 1-4). */
+ ret = btrfs_insert_empty_item(trans, root, path, &new_key, 0);
+ if (ret)
+ goto out;
+
+ btrfs_release_path(path);
+ ret = update_free_space_extent_count(trans, fs_info, block_group, path,
+ new_extents);
+
+out:
+ return ret;
+}
+
+int __add_to_free_space_tree(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path, u64 start, u64 size)
+{
+ struct btrfs_free_space_info *info;
+ u32 flags;
+ int ret;
+
+ if (block_group->needs_free_space) {
+ ret = __add_block_group_free_space(trans, fs_info, block_group,
+ path);
+ if (ret)
+ return ret;
+ }
+
+ info = search_free_space_info(NULL, fs_info, block_group, path, 0);
+ if (IS_ERR(info))
+ return PTR_ERR(info);
+ flags = btrfs_free_space_flags(path->nodes[0], info);
+ btrfs_release_path(path);
+
+ if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
+ return modify_free_space_bitmap(trans, fs_info, block_group,
+ path, start, size, 0);
+ } else {
+ return add_free_space_extent(trans, fs_info, block_group, path,
+ start, size);
+ }
+}
+
+int add_to_free_space_tree(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ u64 start, u64 size)
+{
+ struct btrfs_block_group_cache *block_group;
+ struct btrfs_path *path;
+ int ret;
+
+ if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
+ return 0;
+
+ path = btrfs_alloc_path();
+ if (!path) {
+ ret = -ENOMEM;
+ goto out;
+ }
+
+ block_group = btrfs_lookup_block_group(fs_info, start);
+ if (!block_group) {
+ ASSERT(0);
+ ret = -ENOENT;
+ goto out;
+ }
+
+ mutex_lock(&block_group->free_space_lock);
+ ret = __add_to_free_space_tree(trans, fs_info, block_group, path, start,
+ size);
+ mutex_unlock(&block_group->free_space_lock);
+
+ btrfs_put_block_group(block_group);
+out:
+ btrfs_free_path(path);
+ if (ret)
+ btrfs_abort_transaction(trans, fs_info->free_space_root, ret);
+ return ret;
+}
+
+/*
+ * Populate the free space tree by walking the extent tree. Operations on the
+ * extent tree that happen as a result of writes to the free space tree will go
+ * through the normal add/remove hooks.
+ */
+static int populate_free_space_tree(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group)
+{
+ struct btrfs_root *extent_root = fs_info->extent_root;
+ struct btrfs_path *path, *path2;
+ struct btrfs_key key;
+ u64 start, end;
+ int ret;
+
+ path = btrfs_alloc_path();
+ if (!path)
+ return -ENOMEM;
+ path->reada = 1;
+
+ path2 = btrfs_alloc_path();
+ if (!path2) {
+ btrfs_free_path(path);
+ return -ENOMEM;
+ }
+
+ ret = add_new_free_space_info(trans, fs_info, block_group, path2);
+ if (ret)
+ goto out;
+
+ /*
+ * Iterate through all of the extent and metadata items in this block
+ * group, adding the free space between them and the free space at the
+ * end. Note that EXTENT_ITEM and METADATA_ITEM are less than
+ * BLOCK_GROUP_ITEM, so an extent may precede the block group that it's
+ * contained in.
+ */
+ key.objectid = block_group->key.objectid;
+ key.type = BTRFS_EXTENT_ITEM_KEY;
+ key.offset = 0;
+
+ ret = btrfs_search_slot_for_read(extent_root, &key, path, 1, 0);
+ if (ret < 0)
+ goto out;
+ ASSERT(ret == 0);
+
+ start = block_group->key.objectid;
+ end = block_group->key.objectid + block_group->key.offset;
+ while (1) {
+ btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+
+ if (key.type == BTRFS_EXTENT_ITEM_KEY ||
+ key.type == BTRFS_METADATA_ITEM_KEY) {
+ if (key.objectid >= end)
+ break;
+
+ if (start < key.objectid) {
+ ret = __add_to_free_space_tree(trans, fs_info,
+ block_group,
+ path2, start,
+ key.objectid -
+ start);
+ if (ret)
+ goto out;
+ }
+ start = key.objectid;
+ if (key.type == BTRFS_METADATA_ITEM_KEY)
+ start += fs_info->tree_root->nodesize;
+ else
+ start += key.offset;
+ } else if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
+ if (key.objectid != block_group->key.objectid)
+ break;
+ }
+
+ ret = btrfs_next_item(extent_root, path);
+ if (ret < 0)
+ goto out;
+ if (ret)
+ break;
+ }
+ if (start < end) {
+ ret = __add_to_free_space_tree(trans, fs_info, block_group,
+ path2, start, end - start);
+ if (ret)
+ goto out;
+ }
+
+ ret = 0;
+out:
+ btrfs_free_path(path2);
+ btrfs_free_path(path);
+ return ret;
+}
+
+int btrfs_create_free_space_tree(struct btrfs_fs_info *fs_info)
+{
+ struct btrfs_trans_handle *trans;
+ struct btrfs_root *tree_root = fs_info->tree_root;
+ struct btrfs_root *free_space_root;
+ struct btrfs_block_group_cache *block_group;
+ struct rb_node *node;
+ int ret;
+
+ trans = btrfs_start_transaction(tree_root, 0);
+ if (IS_ERR(trans))
+ return PTR_ERR(trans);
+
+ free_space_root = btrfs_create_tree(trans, fs_info,
+ BTRFS_FREE_SPACE_TREE_OBJECTID);
+ if (IS_ERR(free_space_root)) {
+ ret = PTR_ERR(free_space_root);
+ goto abort;
+ }
+ fs_info->free_space_root = free_space_root;
+
+ node = rb_first(&fs_info->block_group_cache_tree);
+ while (node) {
+ block_group = rb_entry(node, struct btrfs_block_group_cache,
+ cache_node);
+ ret = populate_free_space_tree(trans, fs_info, block_group);
+ if (ret)
+ goto abort;
+ node = rb_next(node);
+ }
+
+ btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE);
+
+ ret = btrfs_commit_transaction(trans, tree_root);
+ if (ret)
+ return ret;
+
+ return 0;
+
+abort:
+ btrfs_abort_transaction(trans, tree_root, ret);
+ btrfs_end_transaction(trans, tree_root);
+ return ret;
+}
+
+static int clear_free_space_tree(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root)
+{
+ struct btrfs_path *path;
+ struct btrfs_key key;
+ int nr;
+ int ret;
+
+ path = btrfs_alloc_path();
+ if (!path)
+ return -ENOMEM;
+
+ path->leave_spinning = 1;
+
+ key.objectid = 0;
+ key.type = 0;
+ key.offset = 0;
+
+ while (1) {
+ ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
+ if (ret < 0)
+ goto out;
+
+ nr = btrfs_header_nritems(path->nodes[0]);
+ if (!nr)
+ break;
+
+ path->slots[0] = 0;
+ ret = btrfs_del_items(trans, root, path, 0, nr);
+ if (ret)
+ goto out;
+
+ btrfs_release_path(path);
+ }
+
+ ret = 0;
+out:
+ btrfs_free_path(path);
+ return ret;
+}
+
+int btrfs_clear_free_space_tree(struct btrfs_fs_info *fs_info)
+{
+ struct btrfs_trans_handle *trans;
+ struct btrfs_root *tree_root = fs_info->tree_root;
+ struct btrfs_root *free_space_root = fs_info->free_space_root;
+ int ret;
+
+ trans = btrfs_start_transaction(tree_root, 0);
+ if (IS_ERR(trans))
+ return PTR_ERR(trans);
+
+ btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE);
+ fs_info->free_space_root = NULL;
+
+ ret = clear_free_space_tree(trans, free_space_root);
+ if (ret)
+ goto abort;
+
+ ret = btrfs_del_root(trans, tree_root, &free_space_root->root_key);
+ if (ret)
+ goto abort;
+
+ list_del(&free_space_root->dirty_list);
+
+ btrfs_tree_lock(free_space_root->node);
+ clean_tree_block(trans, tree_root->fs_info, free_space_root->node);
+ btrfs_tree_unlock(free_space_root->node);
+ btrfs_free_tree_block(trans, free_space_root, free_space_root->node,
+ 0, 1);
+
+ free_extent_buffer(free_space_root->node);
+ free_extent_buffer(free_space_root->commit_root);
+ kfree(free_space_root);
+
+ ret = btrfs_commit_transaction(trans, tree_root);
+ if (ret)
+ return ret;
+
+ return 0;
+
+abort:
+ btrfs_abort_transaction(trans, tree_root, ret);
+ btrfs_end_transaction(trans, tree_root);
+ return ret;
+}
+
+static int __add_block_group_free_space(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path)
+{
+ u64 start, end;
+ int ret;
+
+ start = block_group->key.objectid;
+ end = block_group->key.objectid + block_group->key.offset;
+
+ block_group->needs_free_space = 0;
+
+ ret = add_new_free_space_info(trans, fs_info, block_group, path);
+ if (ret)
+ return ret;
+
+ return __add_to_free_space_tree(trans, fs_info, block_group, path,
+ block_group->key.objectid,
+ block_group->key.offset);
+}
+
+int add_block_group_free_space(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group)
+{
+ struct btrfs_path *path = NULL;
+ int ret = 0;
+
+ if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
+ return 0;
+
+ mutex_lock(&block_group->free_space_lock);
+ if (!block_group->needs_free_space)
+ goto out;
+
+ path = btrfs_alloc_path();
+ if (!path) {
+ ret = -ENOMEM;
+ goto out;
+ }
+
+ ret = __add_block_group_free_space(trans, fs_info, block_group, path);
+
+out:
+ btrfs_free_path(path);
+ mutex_unlock(&block_group->free_space_lock);
+ if (ret)
+ btrfs_abort_transaction(trans, fs_info->free_space_root, ret);
+ return ret;
+}
+
+int remove_block_group_free_space(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group)
+{
+ struct btrfs_root *root = fs_info->free_space_root;
+ struct btrfs_path *path;
+ struct btrfs_key key, found_key;
+ struct extent_buffer *leaf;
+ u64 start, end;
+ int done = 0, nr;
+ int ret;
+
+ if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
+ return 0;
+
+ if (block_group->needs_free_space) {
+ /* We never added this block group to the free space tree. */
+ return 0;
+ }
+
+ path = btrfs_alloc_path();
+ if (!path) {
+ ret = -ENOMEM;
+ goto out;
+ }
+
+ start = block_group->key.objectid;
+ end = block_group->key.objectid + block_group->key.offset;
+
+ key.objectid = end - 1;
+ key.type = (u8)-1;
+ key.offset = (u64)-1;
+
+ while (!done) {
+ ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
+ if (ret)
+ goto out;
+
+ leaf = path->nodes[0];
+ nr = 0;
+ path->slots[0]++;
+ while (path->slots[0] > 0) {
+ btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
+
+ if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
+ ASSERT(found_key.objectid == block_group->key.objectid);
+ ASSERT(found_key.offset == block_group->key.offset);
+ done = 1;
+ nr++;
+ path->slots[0]--;
+ break;
+ } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY ||
+ found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
+ ASSERT(found_key.objectid >= start);
+ ASSERT(found_key.objectid < end);
+ ASSERT(found_key.objectid + found_key.offset <= end);
+ nr++;
+ path->slots[0]--;
+ } else {
+ ASSERT(0);
+ }
+ }
+
+ ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
+ if (ret)
+ goto out;
+ btrfs_release_path(path);
+ }
+
+ ret = 0;
+out:
+ btrfs_free_path(path);
+ if (ret)
+ btrfs_abort_transaction(trans, root, ret);
+ return ret;
+}
+
+static int load_free_space_bitmaps(struct btrfs_caching_control *caching_ctl,
+ struct btrfs_path *path,
+ u32 expected_extent_count)
+{
+ struct btrfs_block_group_cache *block_group;
+ struct btrfs_fs_info *fs_info;
+ struct btrfs_root *root;
+ struct btrfs_key key;
+ int prev_bit = 0, bit;
+ /* Initialize to silence GCC. */
+ u64 extent_start = 0;
+ u64 end, offset;
+ u64 total_found = 0;
+ u32 extent_count = 0;
+ int ret;
+
+ block_group = caching_ctl->block_group;
+ fs_info = block_group->fs_info;
+ root = fs_info->free_space_root;
+
+ end = block_group->key.objectid + block_group->key.offset;
+
+ while (1) {
+ ret = btrfs_next_item(root, path);
+ if (ret < 0)
+ goto out;
+ if (ret)
+ break;
+
+ btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+
+ if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
+ break;
+
+ ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
+ ASSERT(key.objectid < end && key.objectid + key.offset <= end);
+
+ caching_ctl->progress = key.objectid;
+
+ offset = key.objectid;
+ while (offset < key.objectid + key.offset) {
+ bit = free_space_test_bit(block_group, path, offset);
+ if (prev_bit == 0 && bit == 1) {
+ extent_start = offset;
+ } else if (prev_bit == 1 && bit == 0) {
+ total_found += add_new_free_space(block_group,
+ fs_info,
+ extent_start,
+ offset);
+ if (total_found > CACHING_CTL_WAKE_UP) {
+ total_found = 0;
+ wake_up(&caching_ctl->wait);
+ }
+ extent_count++;
+ }
+ prev_bit = bit;
+ offset += block_group->sectorsize;
+ }
+ }
+ if (prev_bit == 1) {
+ total_found += add_new_free_space(block_group, fs_info,
+ extent_start, end);
+ extent_count++;
+ }
+
+ if (extent_count != expected_extent_count) {
+ btrfs_err(fs_info, "incorrect extent count for %llu; counted %u, expected %u",
+ block_group->key.objectid, extent_count,
+ expected_extent_count);
+ ASSERT(0);
+ ret = -EIO;
+ goto out;
+ }
+
+ caching_ctl->progress = (u64)-1;
+
+ ret = 0;
+out:
+ return ret;
+}
+
+static int load_free_space_extents(struct btrfs_caching_control *caching_ctl,
+ struct btrfs_path *path,
+ u32 expected_extent_count)
+{
+ struct btrfs_block_group_cache *block_group;
+ struct btrfs_fs_info *fs_info;
+ struct btrfs_root *root;
+ struct btrfs_key key;
+ u64 end;
+ u64 total_found = 0;
+ u32 extent_count = 0;
+ int ret;
+
+ block_group = caching_ctl->block_group;
+ fs_info = block_group->fs_info;
+ root = fs_info->free_space_root;
+
+ end = block_group->key.objectid + block_group->key.offset;
+
+ while (1) {
+ ret = btrfs_next_item(root, path);
+ if (ret < 0)
+ goto out;
+ if (ret)
+ break;
+
+ btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+
+ if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
+ break;
+
+ ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);
+ ASSERT(key.objectid < end && key.objectid + key.offset <= end);
+
+ caching_ctl->progress = key.objectid;
+
+ total_found += add_new_free_space(block_group, fs_info,
+ key.objectid,
+ key.objectid + key.offset);
+ if (total_found > CACHING_CTL_WAKE_UP) {
+ total_found = 0;
+ wake_up(&caching_ctl->wait);
+ }
+ extent_count++;
+ }
+
+ if (extent_count != expected_extent_count) {
+ btrfs_err(fs_info, "incorrect extent count for %llu; counted %u, expected %u",
+ block_group->key.objectid, extent_count,
+ expected_extent_count);
+ ASSERT(0);
+ ret = -EIO;
+ goto out;
+ }
+
+ caching_ctl->progress = (u64)-1;
+
+ ret = 0;
+out:
+ return ret;
+}
+
+int load_free_space_tree(struct btrfs_caching_control *caching_ctl)
+{
+ struct btrfs_block_group_cache *block_group;
+ struct btrfs_fs_info *fs_info;
+ struct btrfs_free_space_info *info;
+ struct btrfs_path *path;
+ u32 extent_count, flags;
+ int ret;
+
+ block_group = caching_ctl->block_group;
+ fs_info = block_group->fs_info;
+
+ path = btrfs_alloc_path();
+ if (!path)
+ return -ENOMEM;
+
+ /*
+ * Just like caching_thread() doesn't want to deadlock on the extent
+ * tree, we don't want to deadlock on the free space tree.
+ */
+ path->skip_locking = 1;
+ path->search_commit_root = 1;
+ path->reada = 1;
+
+ info = search_free_space_info(NULL, fs_info, block_group, path, 0);
+ if (IS_ERR(info)) {
+ ret = PTR_ERR(info);
+ goto out;
+ }
+ extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
+ flags = btrfs_free_space_flags(path->nodes[0], info);
+
+ /*
+ * We left path pointing to the free space info item, so now
+ * load_free_space_foo can just iterate through the free space tree from
+ * there.
+ */
+ if (flags & BTRFS_FREE_SPACE_USING_BITMAPS)
+ ret = load_free_space_bitmaps(caching_ctl, path, extent_count);
+ else
+ ret = load_free_space_extents(caching_ctl, path, extent_count);
+
+out:
+ btrfs_free_path(path);
+ return ret;
+}
diff --git a/fs/btrfs/free-space-tree.h b/fs/btrfs/free-space-tree.h
new file mode 100644
index 000000000000..54ffced3bce8
--- /dev/null
+++ b/fs/btrfs/free-space-tree.h
@@ -0,0 +1,72 @@
+/*
+ * 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
+#define __BTRFS_FREE_SPACE_TREE
+
+/*
+ * The default size for new free space bitmap items. The last bitmap in a block
+ * group may be truncated, and none of the free space tree code assumes that
+ * existing bitmaps are this size.
+ */
+#define BTRFS_FREE_SPACE_BITMAP_SIZE 256
+#define BTRFS_FREE_SPACE_BITMAP_BITS (BTRFS_FREE_SPACE_BITMAP_SIZE * BITS_PER_BYTE)
+
+void set_free_space_tree_thresholds(struct btrfs_block_group_cache *block_group);
+int btrfs_create_free_space_tree(struct btrfs_fs_info *fs_info);
+int btrfs_clear_free_space_tree(struct btrfs_fs_info *fs_info);
+int load_free_space_tree(struct btrfs_caching_control *caching_ctl);
+int add_block_group_free_space(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group);
+int remove_block_group_free_space(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group);
+int add_to_free_space_tree(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ u64 start, u64 size);
+int remove_from_free_space_tree(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ u64 start, u64 size);
+
+/* Exposed for testing. */
+struct btrfs_free_space_info *
+search_free_space_info(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path, int cow);
+int __add_to_free_space_tree(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path, u64 start, u64 size);
+int __remove_from_free_space_tree(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path, u64 start, u64 size);
+int convert_free_space_to_bitmaps(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path);
+int convert_free_space_to_extents(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path);
+int free_space_test_bit(struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path, u64 offset);
+
+#endif
--
2.6.0
^ permalink raw reply related [flat|nested] 27+ messages in thread* Re: [PATCH v4 6/9] Btrfs: implement the free space B-tree
2015-09-30 3:50 ` [PATCH v4 6/9] Btrfs: implement the free space B-tree Omar Sandoval
@ 2015-09-30 4:35 ` kbuild test robot
2015-09-30 4:35 ` [PATCH] Btrfs: fix simple_return.cocci warnings kbuild test robot
` (3 subsequent siblings)
4 siblings, 0 replies; 27+ messages in thread
From: kbuild test robot @ 2015-09-30 4:35 UTC (permalink / raw)
To: Omar Sandoval; +Cc: kbuild-all, linux-btrfs, Omar Sandoval
Hi Omar,
[auto build test results on v4.3-rc3 -- if it's inappropriate base, please ignore]
coccinelle warnings: (new ones prefixed by >>)
>> fs/btrfs/free-space-tree.c:1255:1-4: WARNING: end returns can be simpified
fs/btrfs/free-space-tree.c:1168:1-4: WARNING: end returns can be simpified
Please review and possibly fold the followup patch.
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
^ permalink raw reply [flat|nested] 27+ messages in thread* [PATCH] Btrfs: fix simple_return.cocci warnings
2015-09-30 3:50 ` [PATCH v4 6/9] Btrfs: implement the free space B-tree Omar Sandoval
2015-09-30 4:35 ` kbuild test robot
@ 2015-09-30 4:35 ` kbuild test robot
2015-10-01 12:54 ` [PATCH v4 6/9] Btrfs: implement the free space B-tree David Sterba
` (2 subsequent siblings)
4 siblings, 0 replies; 27+ messages in thread
From: kbuild test robot @ 2015-09-30 4:35 UTC (permalink / raw)
To: Omar Sandoval; +Cc: kbuild-all, linux-btrfs, Omar Sandoval
fs/btrfs/free-space-tree.c:1255:1-4: WARNING: end returns can be simpified
fs/btrfs/free-space-tree.c:1168:1-4: WARNING: end returns can be simpified
Simplify a trivial if-return sequence. Possibly combine with a
preceding function call.
Generated by: scripts/coccinelle/misc/simple_return.cocci
CC: Omar Sandoval <osandov@fb.com>
Signed-off-by: Fengguang Wu <fengguang.wu@intel.com>
---
free-space-tree.c | 12 ++----------
1 file changed, 2 insertions(+), 10 deletions(-)
--- a/fs/btrfs/free-space-tree.c
+++ b/fs/btrfs/free-space-tree.c
@@ -1165,11 +1165,7 @@ int btrfs_create_free_space_tree(struct
btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE);
- ret = btrfs_commit_transaction(trans, tree_root);
- if (ret)
- return ret;
-
- return 0;
+ return btrfs_commit_transaction(trans, tree_root);
abort:
btrfs_abort_transaction(trans, tree_root, ret);
@@ -1252,11 +1248,7 @@ int btrfs_clear_free_space_tree(struct b
free_extent_buffer(free_space_root->commit_root);
kfree(free_space_root);
- ret = btrfs_commit_transaction(trans, tree_root);
- if (ret)
- return ret;
-
- return 0;
+ return btrfs_commit_transaction(trans, tree_root);
abort:
btrfs_abort_transaction(trans, tree_root, ret);
^ permalink raw reply [flat|nested] 27+ messages in thread* Re: [PATCH v4 6/9] Btrfs: implement the free space B-tree
2015-09-30 3:50 ` [PATCH v4 6/9] Btrfs: implement the free space B-tree Omar Sandoval
2015-09-30 4:35 ` kbuild test robot
2015-09-30 4:35 ` [PATCH] Btrfs: fix simple_return.cocci warnings kbuild test robot
@ 2015-10-01 12:54 ` David Sterba
2015-10-02 14:23 ` kbuild test robot
2015-12-29 20:19 ` Chris Mason
4 siblings, 0 replies; 27+ messages in thread
From: David Sterba @ 2015-10-01 12:54 UTC (permalink / raw)
To: Omar Sandoval; +Cc: linux-btrfs
Hi,
a few minor comments, I haven't reviewed the changes in depth.
On Tue, Sep 29, 2015 at 08:50:35PM -0700, Omar Sandoval wrote:
> From: Omar Sandoval <osandov@fb.com>
> +static int btrfs_search_prev_slot(struct btrfs_trans_handle *trans,
> + struct btrfs_root *root,
> + struct btrfs_key *key, struct btrfs_path *p,
Please don't use single letter variables, eg. 'path' is commonly used
elsewere.
> + int ins_len, int cow)
> +{
> + int ret;
> +
> + ret = btrfs_search_slot(trans, root, key, p, ins_len, cow);
> + if (ret < 0)
> + return ret;
> +
> + if (ret == 0) {
> + ASSERT(0);
> + return -EIO;
> + }
> +
> + if (p->slots[0] == 0) {
> + ASSERT(0);
> + return -EIO;
> + }
> + p->slots[0]--;
> +
> + return 0;
> +}
> +
> +static unsigned long *alloc_bitmap(u32 bitmap_size)
> +{
> + return __vmalloc(bitmap_size, GFP_NOFS | __GFP_HIGHMEM | __GFP_ZERO,
Why is GFP_HIGHMEM here?
> + PAGE_KERNEL);
> +}
> +
> +int convert_free_space_to_bitmaps(struct btrfs_trans_handle *trans,
> + struct btrfs_fs_info *fs_info,
> + struct btrfs_block_group_cache *block_group,
> + struct btrfs_path *path)
> +{
> + struct btrfs_root *root = fs_info->free_space_root;
> + struct btrfs_free_space_info *info;
> + struct btrfs_key key, found_key;
> + struct extent_buffer *leaf;
> + unsigned long *bitmap;
> + char *bitmap_cursor;
> + u64 start, end;
> + u64 bitmap_range, i;
> + u32 bitmap_size, flags, expected_extent_count;
> + u32 extent_count = 0;
> + int done = 0, nr;
> + int ret;
> +
> + bitmap_size = free_space_bitmap_size(block_group->key.offset,
> + block_group->sectorsize);
> + bitmap = alloc_bitmap(bitmap_size);
> + if (!bitmap) {
> + ret = -ENOMEM;
> + goto out;
> + }
Can we get rid of this potential allocation failure site? You free the
buffer in the same function, no recursion, so it should be ok to
preallocate the buffer at the mount time and just reuse here. Converting
to bitmap is not a frequent operation but IMO is critical enough to make
it more robust.
> +
> + start = block_group->key.objectid;
> + end = block_group->key.objectid + block_group->key.offset;
> +
> + key.objectid = end - 1;
> + key.type = (u8)-1;
> + key.offset = (u64)-1;
> +
> + while (!done) {
> + ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
> + if (ret)
> + goto out;
> +
> + leaf = path->nodes[0];
> + nr = 0;
> + path->slots[0]++;
> + while (path->slots[0] > 0) {
> + btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
> +
> + if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
> + ASSERT(found_key.objectid == block_group->key.objectid);
> + ASSERT(found_key.offset == block_group->key.offset);
> + done = 1;
> + break;
> + } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY) {
> + u64 first, last;
> +
> + ASSERT(found_key.objectid >= start);
> + ASSERT(found_key.objectid < end);
> + ASSERT(found_key.objectid + found_key.offset <= end);
> +
> + first = div_u64(found_key.objectid - start,
> + block_group->sectorsize);
> + last = div_u64(found_key.objectid + found_key.offset - start,
> + block_group->sectorsize);
> + bitmap_set(bitmap, first, last - first);
> +
> + extent_count++;
> + nr++;
> + path->slots[0]--;
> + } else {
> + ASSERT(0);
> + }
> + }
> +
> + ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
> + if (ret)
> + goto out;
> + btrfs_release_path(path);
> + }
> +
> + info = search_free_space_info(trans, fs_info, block_group, path, 1);
> + if (IS_ERR(info)) {
> + ret = PTR_ERR(info);
> + goto out;
> + }
> + leaf = path->nodes[0];
> + flags = btrfs_free_space_flags(leaf, info);
> + flags |= BTRFS_FREE_SPACE_USING_BITMAPS;
> + btrfs_set_free_space_flags(leaf, info, flags);
> + expected_extent_count = btrfs_free_space_extent_count(leaf, info);
> + btrfs_mark_buffer_dirty(leaf);
> + btrfs_release_path(path);
> +
> + if (extent_count != expected_extent_count) {
> + btrfs_err(fs_info, "incorrect extent count for %llu; counted %u, expected %u",
> + block_group->key.objectid, extent_count,
> + expected_extent_count);
> + ASSERT(0);
> + ret = -EIO;
> + goto out;
> + }
> +
> + bitmap_cursor = (char *)bitmap;
> + bitmap_range = block_group->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
> + i = start;
> + while (i < end) {
> + unsigned long ptr;
> + u64 extent_size;
> + u32 data_size;
> +
> + extent_size = min(end - i, bitmap_range);
> + data_size = free_space_bitmap_size(extent_size,
> + block_group->sectorsize);
> +
> + key.objectid = i;
> + key.type = BTRFS_FREE_SPACE_BITMAP_KEY;
> + key.offset = extent_size;
> +
> + ret = btrfs_insert_empty_item(trans, root, path, &key,
> + data_size);
> + if (ret)
> + goto out;
> +
> + leaf = path->nodes[0];
> + ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
> + write_extent_buffer(leaf, bitmap_cursor, ptr,
> + data_size);
> + btrfs_mark_buffer_dirty(leaf);
> + btrfs_release_path(path);
> +
> + i += extent_size;
> + bitmap_cursor += data_size;
> + }
> +
> + ret = 0;
> +out:
> + vfree(bitmap);
> + if (ret)
> + btrfs_abort_transaction(trans, root, ret);
A general comment to the transaction aborts: the call should happen at
the location of the error and not in the common exit block. Otherwise we
lose the information what caused the failure.
This applies to the remaining functions as well, I won't point it out
specifically.
^ permalink raw reply [flat|nested] 27+ messages in thread* Re: [PATCH v4 6/9] Btrfs: implement the free space B-tree
2015-09-30 3:50 ` [PATCH v4 6/9] Btrfs: implement the free space B-tree Omar Sandoval
` (2 preceding siblings ...)
2015-10-01 12:54 ` [PATCH v4 6/9] Btrfs: implement the free space B-tree David Sterba
@ 2015-10-02 14:23 ` kbuild test robot
2015-12-29 20:19 ` Chris Mason
4 siblings, 0 replies; 27+ messages in thread
From: kbuild test robot @ 2015-10-02 14:23 UTC (permalink / raw)
To: Omar Sandoval; +Cc: kbuild-all, linux-btrfs, Omar Sandoval
[-- Attachment #1: Type: text/plain, Size: 10879 bytes --]
Hi Omar,
[auto build test results on v4.3-rc3 -- if it's inappropriate base, please ignore]
config: mips-ip27_defconfig (attached as .config)
reproduce:
wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross
chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
make.cross ARCH=mips
All warnings (new ones prefixed by >>):
mips-linux-gnu-ld: fs/btrfs/super.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/super.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/ctree.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/ctree.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/extent-tree.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/extent-tree.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/print-tree.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/print-tree.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/root-tree.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/root-tree.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/dir-item.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/dir-item.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/file-item.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/file-item.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/inode-item.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/inode-item.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/inode-map.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/inode-map.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/disk-io.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/disk-io.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/transaction.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/transaction.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/inode.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/inode.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/file.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/file.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/tree-defrag.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/tree-defrag.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/extent_map.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/extent_map.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/sysfs.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/sysfs.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/struct-funcs.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/struct-funcs.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/xattr.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/xattr.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/ordered-data.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/ordered-data.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/extent_io.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/extent_io.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/volumes.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/volumes.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/async-thread.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/async-thread.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/ioctl.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/ioctl.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/locking.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/locking.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/orphan.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/orphan.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/export.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/export.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/tree-log.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/tree-log.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/free-space-cache.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/free-space-cache.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/zlib.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/zlib.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/lzo.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/lzo.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/compression.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/compression.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/delayed-ref.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/delayed-ref.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/relocation.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/relocation.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/delayed-inode.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/delayed-inode.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/scrub.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/scrub.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/reada.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/reada.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/backref.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/backref.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/ulist.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/ulist.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/qgroup.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/qgroup.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/send.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/send.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/dev-replace.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/dev-replace.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/raid56.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/raid56.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/uuid-tree.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/uuid-tree.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/props.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/props.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/hash.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/hash.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/free-space-tree.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
>> mips-linux-gnu-ld: fs/btrfs/free-space-tree.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/acl.o: warning: Inconsistent ISA between e_flags and .MIPS.abiflags
mips-linux-gnu-ld: fs/btrfs/acl.o: warning: Inconsistent ISA extensions between e_flags and .MIPS.abiflags
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
[-- Attachment #2: .config.gz --]
[-- Type: application/octet-stream, Size: 14096 bytes --]
^ permalink raw reply [flat|nested] 27+ messages in thread* Re: [PATCH v4 6/9] Btrfs: implement the free space B-tree
2015-09-30 3:50 ` [PATCH v4 6/9] Btrfs: implement the free space B-tree Omar Sandoval
` (3 preceding siblings ...)
2015-10-02 14:23 ` kbuild test robot
@ 2015-12-29 20:19 ` Chris Mason
2016-04-22 8:28 ` Alex Lyakas
4 siblings, 1 reply; 27+ messages in thread
From: Chris Mason @ 2015-12-29 20:19 UTC (permalink / raw)
To: Omar Sandoval; +Cc: linux-btrfs
On Tue, Sep 29, 2015 at 08:50:35PM -0700, Omar Sandoval wrote:
> From: Omar Sandoval <osandov@fb.com>
>
> 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.
>
> Signed-off-by: Omar Sandoval <osandov@fb.com>
> +int btrfs_create_free_space_tree(struct btrfs_fs_info *fs_info)
> +{
> + struct btrfs_trans_handle *trans;
> + struct btrfs_root *tree_root = fs_info->tree_root;
> + struct btrfs_root *free_space_root;
> + struct btrfs_block_group_cache *block_group;
> + struct rb_node *node;
> + int ret;
> +
> + trans = btrfs_start_transaction(tree_root, 0);
> + if (IS_ERR(trans))
> + return PTR_ERR(trans);
> +
> + free_space_root = btrfs_create_tree(trans, fs_info,
> + BTRFS_FREE_SPACE_TREE_OBJECTID);
> + if (IS_ERR(free_space_root)) {
> + ret = PTR_ERR(free_space_root);
> + goto abort;
> + }
> + fs_info->free_space_root = free_space_root;
> +
> + node = rb_first(&fs_info->block_group_cache_tree);
> + while (node) {
> + block_group = rb_entry(node, struct btrfs_block_group_cache,
> + cache_node);
> + ret = populate_free_space_tree(trans, fs_info, block_group);
> + if (ret)
> + goto abort;
> + node = rb_next(node);
> + }
> +
> + btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE);
> +
> + ret = btrfs_commit_transaction(trans, tree_root);
> + if (ret)
> + return ret;
> +
> + return 0;
> +
> +abort:
> + btrfs_abort_transaction(trans, tree_root, ret);
> + btrfs_end_transaction(trans, tree_root);
> + return ret;
> +}
> +
Hi Omar,
The only problem I've hit testing this stuff is where we create the tree
on existing filesystems. There are a few different problems here:
1) The populate code happens after resuming balance operations. The
balancing code could be changing these block groups while we scan them.
I fixed this by moving the scan up earlier.
2) Delayed references may be run, which will also change the extent tree
as we're scanning it.
3) We might need to commit the transaction to reclaim space.
For now I'm ignoring #3 and adding a flag in fs_info that will make us
skip delayed references. This really isn't a good long term solution,
we need to be able to do this on a per block group basis and make
forward progress without pinning the delayed refs in ram.
But for now, it'll do to get this into the tree for more testing.
-chris
^ permalink raw reply [flat|nested] 27+ messages in thread* Re: [PATCH v4 6/9] Btrfs: implement the free space B-tree
2015-12-29 20:19 ` Chris Mason
@ 2016-04-22 8:28 ` Alex Lyakas
2016-05-02 21:55 ` Omar Sandoval
0 siblings, 1 reply; 27+ messages in thread
From: Alex Lyakas @ 2016-04-22 8:28 UTC (permalink / raw)
To: Chris Mason, Omar Sandoval, linux-btrfs
Hi Omar, Chris,
I have reviewed the free-space-tree code. It is a very nice feature.
However, I have a basic understanding question.
Let's say we are running a delayed ref which inserts a new EXTENT_ITEM
into the extent tree, e.g., we are in alloc_reserved_file_extent. At
this point we call remove_from_free_space_tree(), which updates the
free-space-tree about the allocated space. But this requires to COW
the free-space-tree itself. So we allocate a new tree block for the
free-space tree, and insert a new delayed ref, which will update the
extent tree about the new tree block allocation. We also insert a
delayed ref to free the previous copy of the free-space-tree block.
At some point we run these new delayed refs, so we insert/remove
EXTENT_ITEMs from the extent tree, and this in turn requires us to
update the free-space-tree again. So we need again to COW
free-space-tree blocks, generating more delayed refs.
At which point this recursion stops?
Do we assume that at some point all needed free-space tree blocks have
been COW'ed already, and we do not COW a tree block more than once per
transaction (unless it was written to disk due to memory pressure)?
Thanks!
Alex.
On Tue, Dec 29, 2015 at 11:19 PM, Chris Mason <clm@fb.com> wrote:
> On Tue, Sep 29, 2015 at 08:50:35PM -0700, Omar Sandoval wrote:
>> From: Omar Sandoval <osandov@fb.com>
>>
>> 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.
>>
>> Signed-off-by: Omar Sandoval <osandov@fb.com>
>
>> +int btrfs_create_free_space_tree(struct btrfs_fs_info *fs_info)
>> +{
>> + struct btrfs_trans_handle *trans;
>> + struct btrfs_root *tree_root = fs_info->tree_root;
>> + struct btrfs_root *free_space_root;
>> + struct btrfs_block_group_cache *block_group;
>> + struct rb_node *node;
>> + int ret;
>> +
>> + trans = btrfs_start_transaction(tree_root, 0);
>> + if (IS_ERR(trans))
>> + return PTR_ERR(trans);
>> +
>> + free_space_root = btrfs_create_tree(trans, fs_info,
>> + BTRFS_FREE_SPACE_TREE_OBJECTID);
>> + if (IS_ERR(free_space_root)) {
>> + ret = PTR_ERR(free_space_root);
>> + goto abort;
>> + }
>> + fs_info->free_space_root = free_space_root;
>> +
>> + node = rb_first(&fs_info->block_group_cache_tree);
>> + while (node) {
>> + block_group = rb_entry(node, struct btrfs_block_group_cache,
>> + cache_node);
>> + ret = populate_free_space_tree(trans, fs_info, block_group);
>> + if (ret)
>> + goto abort;
>> + node = rb_next(node);
>> + }
>> +
>> + btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE);
>> +
>> + ret = btrfs_commit_transaction(trans, tree_root);
>> + if (ret)
>> + return ret;
>> +
>> + return 0;
>> +
>> +abort:
>> + btrfs_abort_transaction(trans, tree_root, ret);
>> + btrfs_end_transaction(trans, tree_root);
>> + return ret;
>> +}
>> +
>
> Hi Omar,
>
> The only problem I've hit testing this stuff is where we create the tree
> on existing filesystems. There are a few different problems here:
>
> 1) The populate code happens after resuming balance operations. The
> balancing code could be changing these block groups while we scan them.
> I fixed this by moving the scan up earlier.
>
> 2) Delayed references may be run, which will also change the extent tree
> as we're scanning it.
>
> 3) We might need to commit the transaction to reclaim space.
>
> For now I'm ignoring #3 and adding a flag in fs_info that will make us
> skip delayed references. This really isn't a good long term solution,
> we need to be able to do this on a per block group basis and make
> forward progress without pinning the delayed refs in ram.
>
> But for now, it'll do to get this into the tree for more testing.
>
> -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
^ permalink raw reply [flat|nested] 27+ messages in thread* Re: [PATCH v4 6/9] Btrfs: implement the free space B-tree
2016-04-22 8:28 ` Alex Lyakas
@ 2016-05-02 21:55 ` Omar Sandoval
0 siblings, 0 replies; 27+ messages in thread
From: Omar Sandoval @ 2016-05-02 21:55 UTC (permalink / raw)
To: Alex Lyakas; +Cc: Chris Mason, linux-btrfs
On Fri, Apr 22, 2016 at 11:28:24AM +0300, Alex Lyakas wrote:
> Hi Omar, Chris,
>
> I have reviewed the free-space-tree code. It is a very nice feature.
>
> However, I have a basic understanding question.
>
> Let's say we are running a delayed ref which inserts a new EXTENT_ITEM
> into the extent tree, e.g., we are in alloc_reserved_file_extent. At
> this point we call remove_from_free_space_tree(), which updates the
> free-space-tree about the allocated space. But this requires to COW
> the free-space-tree itself. So we allocate a new tree block for the
> free-space tree, and insert a new delayed ref, which will update the
> extent tree about the new tree block allocation. We also insert a
> delayed ref to free the previous copy of the free-space-tree block.
>
> At some point we run these new delayed refs, so we insert/remove
> EXTENT_ITEMs from the extent tree, and this in turn requires us to
> update the free-space-tree again. So we need again to COW
> free-space-tree blocks, generating more delayed refs.
>
> At which point this recursion stops?
>
> Do we assume that at some point all needed free-space tree blocks have
> been COW'ed already, and we do not COW a tree block more than once per
> transaction (unless it was written to disk due to memory pressure)?
>
> Thanks!
> Alex.
Hi, Alex,
Your understanding is correct, we'll only COW a tree block once during a
transaction, so the recursion stops once all of the free space items we
need to add/remove don't require rebalancing the tree or allocating or
freeing a block. Same thing goes for extent items in the extent tree.
Since the extent tree and free space tree items are much smaller than a
tree block, this doesn't turn out to be a problem in practice.
Thanks for taking a look :)
--
Omar
^ permalink raw reply [flat|nested] 27+ messages in thread
* [PATCH v4 7/9] Btrfs: add free space tree sanity tests
2015-09-30 3:50 [PATCH v4 0/9] Btrfs: free space B-tree Omar Sandoval
` (5 preceding siblings ...)
2015-09-30 3:50 ` [PATCH v4 6/9] Btrfs: implement the free space B-tree Omar Sandoval
@ 2015-09-30 3:50 ` Omar Sandoval
2015-10-01 13:04 ` David Sterba
2023-10-11 2:12 ` Jinjie Ruan
2015-09-30 3:50 ` [PATCH v4 8/9] Btrfs: wire up the free space tree to the extent tree Omar Sandoval
` (4 subsequent siblings)
11 siblings, 2 replies; 27+ messages in thread
From: Omar Sandoval @ 2015-09-30 3:50 UTC (permalink / raw)
To: linux-btrfs; +Cc: Omar Sandoval
From: Omar Sandoval <osandov@fb.com>
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.
Signed-off-by: Omar Sandoval <osandov@fb.com>
---
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
diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
index 766169709146..128ce17a80b0 100644
--- a/fs/btrfs/Makefile
+++ b/fs/btrfs/Makefile
@@ -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
diff --git a/fs/btrfs/super.c b/fs/btrfs/super.c
index 11d1eab9234d..442bf434b783 100644
--- a/fs/btrfs/super.c
+++ b/fs/btrfs/super.c
@@ -2212,6 +2212,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;
diff --git a/fs/btrfs/tests/btrfs-tests.c b/fs/btrfs/tests/btrfs-tests.c
index 9626252ee6b4..ba28cefdf9e7 100644
--- a/fs/btrfs/tests/btrfs-tests.c
+++ b/fs/btrfs/tests/btrfs-tests.c
@@ -21,6 +21,9 @@
#include <linux/magic.h>
#include "btrfs-tests.h"
#include "../ctree.h"
+#include "../free-space-cache.h"
+#include "../free-space-tree.h"
+#include "../transaction.h"
#include "../volumes.h"
#include "../disk-io.h"
#include "../qgroup.h"
@@ -122,6 +125,9 @@ struct btrfs_fs_info *btrfs_alloc_dummy_fs_info(void)
INIT_LIST_HEAD(&fs_info->tree_mod_seq_list);
INIT_RADIX_TREE(&fs_info->buffer_radix, GFP_ATOMIC);
INIT_RADIX_TREE(&fs_info->fs_roots_radix, GFP_ATOMIC);
+ extent_io_tree_init(&fs_info->freed_extents[0], NULL);
+ extent_io_tree_init(&fs_info->freed_extents[1], NULL);
+ fs_info->pinned_extents = &fs_info->freed_extents[0];
return fs_info;
}
@@ -169,3 +175,49 @@ void btrfs_free_dummy_root(struct btrfs_root *root)
kfree(root);
}
+struct btrfs_block_group_cache *
+btrfs_alloc_dummy_block_group(unsigned long length)
+{
+ 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 = length;
+ cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
+ cache->sectorsize = 4096;
+ cache->full_stripe_len = 4096;
+
+ INIT_LIST_HEAD(&cache->list);
+ INIT_LIST_HEAD(&cache->cluster_list);
+ INIT_LIST_HEAD(&cache->bg_list);
+ btrfs_init_free_space_ctl(cache);
+ mutex_init(&cache->free_space_lock);
+
+ return cache;
+}
+
+void btrfs_free_dummy_block_group(struct btrfs_block_group_cache *cache)
+{
+ if (!cache)
+ return;
+ __btrfs_remove_free_space_cache(cache->free_space_ctl);
+ kfree(cache->free_space_ctl);
+ kfree(cache);
+}
+
+void btrfs_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;
+}
diff --git a/fs/btrfs/tests/btrfs-tests.h b/fs/btrfs/tests/btrfs-tests.h
index fd3954224480..054b8c73c951 100644
--- a/fs/btrfs/tests/btrfs-tests.h
+++ b/fs/btrfs/tests/btrfs-tests.h
@@ -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
diff --git a/fs/btrfs/tests/free-space-tests.c b/fs/btrfs/tests/free-space-tests.c
index 2299bfde39ee..bae6c599f604 100644
--- a/fs/btrfs/tests/free-space-tests.c
+++ b/fs/btrfs/tests/free-space-tests.c
@@ -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;
}
diff --git a/fs/btrfs/tests/free-space-tree-tests.c b/fs/btrfs/tests/free-space-tree-tests.c
new file mode 100644
index 000000000000..d05fe1ab4808
--- /dev/null
+++ b/fs/btrfs/tests/free-space-tree-tests.c
@@ -0,0 +1,571 @@
+/*
+ * 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.
+ */
+
+#include "btrfs-tests.h"
+#include "../ctree.h"
+#include "../disk-io.h"
+#include "../free-space-tree.h"
+#include "../transaction.h"
+
+struct free_space_extent {
+ u64 start, length;
+};
+
+/*
+ * The test cases align their operations to this in order to hit some of the
+ * edge cases in the bitmap code.
+ */
+#define BITMAP_RANGE (BTRFS_FREE_SPACE_BITMAP_BITS * 4096)
+
+static int __check_free_space_extents(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *cache,
+ struct btrfs_path *path,
+ struct free_space_extent *extents,
+ unsigned int num_extents)
+{
+ struct btrfs_free_space_info *info;
+ struct btrfs_key key;
+ int prev_bit = 0, bit;
+ u64 extent_start = 0, offset, end;
+ u32 flags, extent_count;
+ unsigned int i;
+ int ret;
+
+ info = search_free_space_info(trans, fs_info, cache, path, 0);
+ if (IS_ERR(info)) {
+ test_msg("Could not find free space info\n");
+ ret = PTR_ERR(info);
+ goto out;
+ }
+ flags = btrfs_free_space_flags(path->nodes[0], info);
+ extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
+
+ if (extent_count != num_extents) {
+ test_msg("Extent count is wrong\n");
+ ret = -EINVAL;
+ goto out;
+ }
+ if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
+ if (path->slots[0] != 0)
+ goto invalid;
+ end = cache->key.objectid + cache->key.offset;
+ i = 0;
+ while (++path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
+ btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+ if (key.type != BTRFS_FREE_SPACE_BITMAP_KEY)
+ goto invalid;
+ offset = key.objectid;
+ while (offset < key.objectid + key.offset) {
+ bit = free_space_test_bit(cache, path, offset);
+ if (prev_bit == 0 && bit == 1) {
+ extent_start = offset;
+ } else if (prev_bit == 1 && bit == 0) {
+ if (i >= num_extents)
+ goto invalid;
+ if (i >= num_extents ||
+ extent_start != extents[i].start ||
+ offset - extent_start != extents[i].length)
+ goto invalid;
+ i++;
+ }
+ prev_bit = bit;
+ offset += cache->sectorsize;
+ }
+ }
+ if (prev_bit == 1) {
+ if (i >= num_extents ||
+ extent_start != extents[i].start ||
+ end - extent_start != extents[i].length)
+ goto invalid;
+ i++;
+ }
+ if (i != num_extents)
+ goto invalid;
+ } else {
+ if (btrfs_header_nritems(path->nodes[0]) != num_extents + 1 ||
+ path->slots[0] != 0)
+ goto invalid;
+ for (i = 0; i < num_extents; i++) {
+ path->slots[0]++;
+ btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+ if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY ||
+ key.objectid != extents[i].start ||
+ key.offset != extents[i].length)
+ goto invalid;
+ }
+ }
+
+ ret = 0;
+out:
+ btrfs_release_path(path);
+ return ret;
+invalid:
+ test_msg("Free space tree is invalid\n");
+ ret = -EINVAL;
+ goto out;
+}
+
+static int check_free_space_extents(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *cache,
+ struct btrfs_path *path,
+ struct free_space_extent *extents,
+ unsigned int num_extents)
+{
+ struct btrfs_free_space_info *info;
+ u32 flags;
+ int ret;
+
+ info = search_free_space_info(trans, fs_info, cache, path, 0);
+ if (IS_ERR(info)) {
+ test_msg("Could not find free space info\n");
+ btrfs_release_path(path);
+ return PTR_ERR(info);
+ }
+ flags = btrfs_free_space_flags(path->nodes[0], info);
+ btrfs_release_path(path);
+
+ ret = __check_free_space_extents(trans, fs_info, cache, path, extents,
+ num_extents);
+ if (ret)
+ return ret;
+
+ /* Flip it to the other format and check that for good measure. */
+ if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
+ ret = convert_free_space_to_extents(trans, fs_info, cache, path);
+ if (ret) {
+ test_msg("Could not convert to extents\n");
+ return ret;
+ }
+ } else {
+ ret = convert_free_space_to_bitmaps(trans, fs_info, cache, path);
+ if (ret) {
+ test_msg("Could not convert to bitmaps\n");
+ return ret;
+ }
+ }
+ return __check_free_space_extents(trans, fs_info, cache, path, extents,
+ num_extents);
+}
+
+static int test_empty_block_group(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *cache,
+ struct btrfs_path *path)
+{
+ struct free_space_extent extents[] = {
+ {cache->key.objectid, cache->key.offset},
+ };
+
+ return check_free_space_extents(trans, fs_info, cache, path,
+ extents, ARRAY_SIZE(extents));
+}
+
+static int test_remove_all(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *cache,
+ struct btrfs_path *path)
+{
+ struct free_space_extent extents[] = {};
+ int ret;
+
+ ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid,
+ cache->key.offset);
+ if (ret) {
+ test_msg("Could not remove free space\n");
+ return ret;
+ }
+
+ return check_free_space_extents(trans, fs_info, cache, path,
+ extents, ARRAY_SIZE(extents));
+}
+
+static int test_remove_beginning(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *cache,
+ struct btrfs_path *path)
+{
+ struct free_space_extent extents[] = {
+ {cache->key.objectid + BITMAP_RANGE,
+ cache->key.offset - BITMAP_RANGE},
+ };
+ int ret;
+
+ ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid, BITMAP_RANGE);
+ if (ret) {
+ test_msg("Could not remove free space\n");
+ return ret;
+ }
+
+ return check_free_space_extents(trans, fs_info, cache, path,
+ extents, ARRAY_SIZE(extents));
+
+}
+
+static int test_remove_end(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *cache,
+ struct btrfs_path *path)
+{
+ struct free_space_extent extents[] = {
+ {cache->key.objectid, cache->key.offset - BITMAP_RANGE},
+ };
+ int ret;
+
+ ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid +
+ cache->key.offset - BITMAP_RANGE,
+ BITMAP_RANGE);
+ if (ret) {
+ test_msg("Could not remove free space\n");
+ return ret;
+ }
+
+ return check_free_space_extents(trans, fs_info, cache, path,
+ extents, ARRAY_SIZE(extents));
+}
+
+static int test_remove_middle(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *cache,
+ struct btrfs_path *path)
+{
+ struct free_space_extent extents[] = {
+ {cache->key.objectid, BITMAP_RANGE},
+ {cache->key.objectid + 2 * BITMAP_RANGE,
+ cache->key.offset - 2 * BITMAP_RANGE},
+ };
+ int ret;
+
+ ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid + BITMAP_RANGE,
+ BITMAP_RANGE);
+ if (ret) {
+ test_msg("Could not remove free space\n");
+ return ret;
+ }
+
+ return check_free_space_extents(trans, fs_info, cache, path,
+ extents, ARRAY_SIZE(extents));
+}
+
+static int test_merge_left(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *cache,
+ struct btrfs_path *path)
+{
+ struct free_space_extent extents[] = {
+ {cache->key.objectid, 2 * BITMAP_RANGE},
+ };
+ int ret;
+
+ ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid,
+ cache->key.offset);
+ if (ret) {
+ test_msg("Could not remove free space\n");
+ return ret;
+ }
+
+ ret = __add_to_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid, BITMAP_RANGE);
+ if (ret) {
+ test_msg("Could not add free space\n");
+ return ret;
+ }
+
+ ret = __add_to_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid + BITMAP_RANGE,
+ BITMAP_RANGE);
+ if (ret) {
+ test_msg("Could not add free space\n");
+ return ret;
+ }
+
+ return check_free_space_extents(trans, fs_info, cache, path,
+ extents, ARRAY_SIZE(extents));
+}
+
+static int test_merge_right(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *cache,
+ struct btrfs_path *path)
+{
+ struct free_space_extent extents[] = {
+ {cache->key.objectid + BITMAP_RANGE, 2 * BITMAP_RANGE},
+ };
+ int ret;
+
+ ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid,
+ cache->key.offset);
+ if (ret) {
+ test_msg("Could not remove free space\n");
+ return ret;
+ }
+
+ ret = __add_to_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid + 2 * BITMAP_RANGE,
+ BITMAP_RANGE);
+ if (ret) {
+ test_msg("Could not add free space\n");
+ return ret;
+ }
+
+ ret = __add_to_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid + BITMAP_RANGE,
+ BITMAP_RANGE);
+ if (ret) {
+ test_msg("Could not add free space\n");
+ return ret;
+ }
+
+ return check_free_space_extents(trans, fs_info, cache, path,
+ extents, ARRAY_SIZE(extents));
+}
+
+static int test_merge_both(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *cache,
+ struct btrfs_path *path)
+{
+ struct free_space_extent extents[] = {
+ {cache->key.objectid, 3 * BITMAP_RANGE},
+ };
+ int ret;
+
+ ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid,
+ cache->key.offset);
+ if (ret) {
+ test_msg("Could not remove free space\n");
+ return ret;
+ }
+
+ ret = __add_to_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid, BITMAP_RANGE);
+ if (ret) {
+ test_msg("Could not add free space\n");
+ return ret;
+ }
+
+ ret = __add_to_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid + 2 * BITMAP_RANGE,
+ BITMAP_RANGE);
+ if (ret) {
+ test_msg("Could not add free space\n");
+ return ret;
+ }
+
+ ret = __add_to_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid + BITMAP_RANGE,
+ BITMAP_RANGE);
+ if (ret) {
+ test_msg("Could not add free space\n");
+ return ret;
+ }
+
+ return check_free_space_extents(trans, fs_info, cache, path,
+ extents, ARRAY_SIZE(extents));
+}
+
+static int test_merge_none(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *cache,
+ struct btrfs_path *path)
+{
+ struct free_space_extent extents[] = {
+ {cache->key.objectid, BITMAP_RANGE},
+ {cache->key.objectid + 2 * BITMAP_RANGE, BITMAP_RANGE},
+ {cache->key.objectid + 4 * BITMAP_RANGE, BITMAP_RANGE},
+ };
+ int ret;
+
+ ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid,
+ cache->key.offset);
+ if (ret) {
+ test_msg("Could not remove free space\n");
+ return ret;
+ }
+
+ ret = __add_to_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid, BITMAP_RANGE);
+ if (ret) {
+ test_msg("Could not add free space\n");
+ return ret;
+ }
+
+ ret = __add_to_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid + 4 * BITMAP_RANGE,
+ BITMAP_RANGE);
+ if (ret) {
+ test_msg("Could not add free space\n");
+ return ret;
+ }
+
+ ret = __add_to_free_space_tree(trans, fs_info, cache, path,
+ cache->key.objectid + 2 * BITMAP_RANGE,
+ BITMAP_RANGE);
+ if (ret) {
+ test_msg("Could not add free space\n");
+ return ret;
+ }
+
+ return check_free_space_extents(trans, fs_info, cache, path,
+ extents, ARRAY_SIZE(extents));
+}
+
+typedef int (*test_func_t)(struct btrfs_trans_handle *,
+ struct btrfs_fs_info *,
+ struct btrfs_block_group_cache *,
+ struct btrfs_path *);
+
+static int run_test(test_func_t test_func, int bitmaps)
+{
+ struct btrfs_root *root = NULL;
+ struct btrfs_block_group_cache *cache = NULL;
+ struct btrfs_trans_handle trans;
+ struct btrfs_path *path = NULL;
+ int ret;
+
+ root = btrfs_alloc_dummy_root();
+ if (IS_ERR(root)) {
+ test_msg("Couldn't allocate dummy root\n");
+ ret = PTR_ERR(root);
+ goto out;
+ }
+
+ root->fs_info = btrfs_alloc_dummy_fs_info();
+ if (!root->fs_info) {
+ test_msg("Couldn't allocate dummy fs info\n");
+ ret = -ENOMEM;
+ goto out;
+ }
+
+ btrfs_set_super_compat_ro_flags(root->fs_info->super_copy,
+ BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE);
+ root->fs_info->free_space_root = root;
+ root->fs_info->tree_root = root;
+
+ root->node = alloc_test_extent_buffer(root->fs_info, 4096);
+ if (!root->node) {
+ test_msg("Couldn't allocate dummy buffer\n");
+ ret = -ENOMEM;
+ goto out;
+ }
+ btrfs_set_header_level(root->node, 0);
+ btrfs_set_header_nritems(root->node, 0);
+ root->alloc_bytenr += 8192;
+
+ cache = btrfs_alloc_dummy_block_group(8 * BITMAP_RANGE);
+ if (!cache) {
+ test_msg("Couldn't allocate dummy block group cache\n");
+ ret = -ENOMEM;
+ goto out;
+ }
+ cache->bitmap_low_thresh = 0;
+ cache->bitmap_high_thresh = (u32)-1;
+ cache->needs_free_space = 1;
+
+ btrfs_init_dummy_trans(&trans);
+
+ path = btrfs_alloc_path();
+ if (!path) {
+ test_msg("Couldn't allocate path\n");
+ return -ENOMEM;
+ }
+
+ ret = add_block_group_free_space(&trans, root->fs_info, cache);
+ if (ret) {
+ test_msg("Could not add block group free space\n");
+ goto out;
+ }
+
+ if (bitmaps) {
+ ret = convert_free_space_to_bitmaps(&trans, root->fs_info,
+ cache, path);
+ if (ret) {
+ test_msg("Could not convert block group to bitmaps\n");
+ goto out;
+ }
+ }
+
+ ret = test_func(&trans, root->fs_info, cache, path);
+ if (ret)
+ goto out;
+
+ ret = remove_block_group_free_space(&trans, root->fs_info, cache);
+ if (ret) {
+ test_msg("Could not remove block group free space\n");
+ goto out;
+ }
+
+ if (btrfs_header_nritems(root->node) != 0) {
+ test_msg("Free space tree has leftover items\n");
+ ret = -EINVAL;
+ goto out;
+ }
+
+ ret = 0;
+out:
+ btrfs_free_path(path);
+ btrfs_free_dummy_block_group(cache);
+ btrfs_free_dummy_root(root);
+ return ret;
+}
+
+static int run_test_both_formats(test_func_t test_func)
+{
+ int ret;
+
+ ret = run_test(test_func, 0);
+ if (ret)
+ return ret;
+ return run_test(test_func, 1);
+}
+
+int btrfs_test_free_space_tree(void)
+{
+ test_func_t tests[] = {
+ test_empty_block_group,
+ test_remove_all,
+ test_remove_beginning,
+ test_remove_end,
+ test_remove_middle,
+ test_merge_left,
+ test_merge_right,
+ test_merge_both,
+ test_merge_none,
+ };
+ int i;
+
+ test_msg("Running free space tree tests\n");
+ for (i = 0; i < ARRAY_SIZE(tests); i++) {
+ int ret = run_test_both_formats(tests[i]);
+ if (ret) {
+ test_msg("%pf failed\n", tests[i]);
+ return ret;
+ }
+ }
+
+ return 0;
+}
diff --git a/fs/btrfs/tests/qgroup-tests.c b/fs/btrfs/tests/qgroup-tests.c
index 846d277b1901..8ea5d34bc5a2 100644
--- a/fs/btrfs/tests/qgroup-tests.c
+++ b/fs/btrfs/tests/qgroup-tests.c
@@ -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");
--
2.6.0
^ permalink raw reply related [flat|nested] 27+ messages in thread* Re: [PATCH v4 7/9] Btrfs: add free space tree sanity tests
2015-09-30 3:50 ` [PATCH v4 7/9] Btrfs: add free space tree sanity tests Omar Sandoval
@ 2015-10-01 13:04 ` David Sterba
2023-10-11 2:12 ` Jinjie Ruan
1 sibling, 0 replies; 27+ messages in thread
From: David Sterba @ 2015-10-01 13:04 UTC (permalink / raw)
To: Omar Sandoval; +Cc: linux-btrfs
On Tue, Sep 29, 2015 at 08:50:36PM -0700, Omar Sandoval wrote:
> +struct free_space_extent {
> + u64 start, length;
Structure members should be put on separate lines.
^ permalink raw reply [flat|nested] 27+ messages in thread* Re: [PATCH v4 7/9] Btrfs: add free space tree sanity tests
2015-09-30 3:50 ` [PATCH v4 7/9] Btrfs: add free space tree sanity tests Omar Sandoval
2015-10-01 13:04 ` David Sterba
@ 2023-10-11 2:12 ` Jinjie Ruan
2023-10-11 10:20 ` David Sterba
1 sibling, 1 reply; 27+ messages in thread
From: Jinjie Ruan @ 2023-10-11 2:12 UTC (permalink / raw)
To: Omar Sandoval, linux-btrfs
On 2015/9/30 11:50, Omar Sandoval wrote:
> From: Omar Sandoval <osandov@fb.com>
>
> 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.
>
> Signed-off-by: Omar Sandoval <osandov@fb.com>
> ---
> 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
>
> diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
> index 766169709146..128ce17a80b0 100644
> --- a/fs/btrfs/Makefile
> +++ b/fs/btrfs/Makefile
> @@ -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
> diff --git a/fs/btrfs/super.c b/fs/btrfs/super.c
> index 11d1eab9234d..442bf434b783 100644
> --- a/fs/btrfs/super.c
> +++ b/fs/btrfs/super.c
> @@ -2212,6 +2212,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;
> diff --git a/fs/btrfs/tests/btrfs-tests.c b/fs/btrfs/tests/btrfs-tests.c
> index 9626252ee6b4..ba28cefdf9e7 100644
> --- a/fs/btrfs/tests/btrfs-tests.c
> +++ b/fs/btrfs/tests/btrfs-tests.c
> @@ -21,6 +21,9 @@
> #include <linux/magic.h>
> #include "btrfs-tests.h"
> #include "../ctree.h"
> +#include "../free-space-cache.h"
> +#include "../free-space-tree.h"
> +#include "../transaction.h"
> #include "../volumes.h"
> #include "../disk-io.h"
> #include "../qgroup.h"
> @@ -122,6 +125,9 @@ struct btrfs_fs_info *btrfs_alloc_dummy_fs_info(void)
> INIT_LIST_HEAD(&fs_info->tree_mod_seq_list);
> INIT_RADIX_TREE(&fs_info->buffer_radix, GFP_ATOMIC);
> INIT_RADIX_TREE(&fs_info->fs_roots_radix, GFP_ATOMIC);
> + extent_io_tree_init(&fs_info->freed_extents[0], NULL);
> + extent_io_tree_init(&fs_info->freed_extents[1], NULL);
> + fs_info->pinned_extents = &fs_info->freed_extents[0];
> return fs_info;
> }
>
> @@ -169,3 +175,49 @@ void btrfs_free_dummy_root(struct btrfs_root *root)
> kfree(root);
> }
>
> +struct btrfs_block_group_cache *
> +btrfs_alloc_dummy_block_group(unsigned long length)
> +{
> + 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 = length;
> + cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
> + cache->sectorsize = 4096;
> + cache->full_stripe_len = 4096;
> +
> + INIT_LIST_HEAD(&cache->list);
> + INIT_LIST_HEAD(&cache->cluster_list);
> + INIT_LIST_HEAD(&cache->bg_list);
> + btrfs_init_free_space_ctl(cache);
> + mutex_init(&cache->free_space_lock);
> +
> + return cache;
> +}
> +
> +void btrfs_free_dummy_block_group(struct btrfs_block_group_cache *cache)
> +{
> + if (!cache)
> + return;
> + __btrfs_remove_free_space_cache(cache->free_space_ctl);
> + kfree(cache->free_space_ctl);
> + kfree(cache);
> +}
> +
> +void btrfs_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;
> +}
> diff --git a/fs/btrfs/tests/btrfs-tests.h b/fs/btrfs/tests/btrfs-tests.h
> index fd3954224480..054b8c73c951 100644
> --- a/fs/btrfs/tests/btrfs-tests.h
> +++ b/fs/btrfs/tests/btrfs-tests.h
> @@ -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
> diff --git a/fs/btrfs/tests/free-space-tests.c b/fs/btrfs/tests/free-space-tests.c
> index 2299bfde39ee..bae6c599f604 100644
> --- a/fs/btrfs/tests/free-space-tests.c
> +++ b/fs/btrfs/tests/free-space-tests.c
> @@ -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;
> }
> diff --git a/fs/btrfs/tests/free-space-tree-tests.c b/fs/btrfs/tests/free-space-tree-tests.c
> new file mode 100644
> index 000000000000..d05fe1ab4808
> --- /dev/null
> +++ b/fs/btrfs/tests/free-space-tree-tests.c
> @@ -0,0 +1,571 @@
> +/*
> + * 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.
> + */
> +
> +#include "btrfs-tests.h"
> +#include "../ctree.h"
> +#include "../disk-io.h"
> +#include "../free-space-tree.h"
> +#include "../transaction.h"
> +
> +struct free_space_extent {
> + u64 start, length;
> +};
> +
> +/*
> + * The test cases align their operations to this in order to hit some of the
> + * edge cases in the bitmap code.
> + */
> +#define BITMAP_RANGE (BTRFS_FREE_SPACE_BITMAP_BITS * 4096)
> +
> +static int __check_free_space_extents(struct btrfs_trans_handle *trans,
> + struct btrfs_fs_info *fs_info,
> + struct btrfs_block_group_cache *cache,
> + struct btrfs_path *path,
> + struct free_space_extent *extents,
> + unsigned int num_extents)
> +{
> + struct btrfs_free_space_info *info;
> + struct btrfs_key key;
> + int prev_bit = 0, bit;
> + u64 extent_start = 0, offset, end;
> + u32 flags, extent_count;
> + unsigned int i;
> + int ret;
> +
> + info = search_free_space_info(trans, fs_info, cache, path, 0);
> + if (IS_ERR(info)) {
> + test_msg("Could not find free space info\n");
> + ret = PTR_ERR(info);
> + goto out;
> + }
> + flags = btrfs_free_space_flags(path->nodes[0], info);
> + extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
> +
> + if (extent_count != num_extents) {
> + test_msg("Extent count is wrong\n");
> + ret = -EINVAL;
> + goto out;
> + }
> + if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
> + if (path->slots[0] != 0)
> + goto invalid;
> + end = cache->key.objectid + cache->key.offset;
> + i = 0;
> + while (++path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
> + btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
> + if (key.type != BTRFS_FREE_SPACE_BITMAP_KEY)
> + goto invalid;
> + offset = key.objectid;
> + while (offset < key.objectid + key.offset) {
> + bit = free_space_test_bit(cache, path, offset);
> + if (prev_bit == 0 && bit == 1) {
> + extent_start = offset;
> + } else if (prev_bit == 1 && bit == 0) {
> + if (i >= num_extents)
> + goto invalid;
> + if (i >= num_extents ||
> + extent_start != extents[i].start ||
> + offset - extent_start != extents[i].length)
> + goto invalid;
> + i++;
> + }
> + prev_bit = bit;
> + offset += cache->sectorsize;
> + }
> + }
> + if (prev_bit == 1) {
> + if (i >= num_extents ||
> + extent_start != extents[i].start ||
> + end - extent_start != extents[i].length)
> + goto invalid;
> + i++;
> + }
> + if (i != num_extents)
> + goto invalid;
> + } else {
> + if (btrfs_header_nritems(path->nodes[0]) != num_extents + 1 ||
> + path->slots[0] != 0)
> + goto invalid;
> + for (i = 0; i < num_extents; i++) {
> + path->slots[0]++;
> + btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
> + if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY ||
> + key.objectid != extents[i].start ||
> + key.offset != extents[i].length)
> + goto invalid;
> + }
> + }
> +
> + ret = 0;
> +out:
> + btrfs_release_path(path);
> + return ret;
> +invalid:
> + test_msg("Free space tree is invalid\n");
> + ret = -EINVAL;
> + goto out;
> +}
> +
> +static int check_free_space_extents(struct btrfs_trans_handle *trans,
> + struct btrfs_fs_info *fs_info,
> + struct btrfs_block_group_cache *cache,
> + struct btrfs_path *path,
> + struct free_space_extent *extents,
> + unsigned int num_extents)
> +{
> + struct btrfs_free_space_info *info;
> + u32 flags;
> + int ret;
> +
> + info = search_free_space_info(trans, fs_info, cache, path, 0);
> + if (IS_ERR(info)) {
> + test_msg("Could not find free space info\n");
> + btrfs_release_path(path);
> + return PTR_ERR(info);
> + }
> + flags = btrfs_free_space_flags(path->nodes[0], info);
> + btrfs_release_path(path);
> +
> + ret = __check_free_space_extents(trans, fs_info, cache, path, extents,
> + num_extents);
> + if (ret)
> + return ret;
> +
> + /* Flip it to the other format and check that for good measure. */
> + if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
> + ret = convert_free_space_to_extents(trans, fs_info, cache, path);
> + if (ret) {
> + test_msg("Could not convert to extents\n");
> + return ret;
> + }
> + } else {
> + ret = convert_free_space_to_bitmaps(trans, fs_info, cache, path);
> + if (ret) {
> + test_msg("Could not convert to bitmaps\n");
> + return ret;
> + }
> + }
> + return __check_free_space_extents(trans, fs_info, cache, path, extents,
> + num_extents);
> +}
> +
> +static int test_empty_block_group(struct btrfs_trans_handle *trans,
> + struct btrfs_fs_info *fs_info,
> + struct btrfs_block_group_cache *cache,
> + struct btrfs_path *path)
> +{
> + struct free_space_extent extents[] = {
> + {cache->key.objectid, cache->key.offset},
> + };
> +
> + return check_free_space_extents(trans, fs_info, cache, path,
> + extents, ARRAY_SIZE(extents));
Inject fault when probe btrfs.ko, there is a null-ptr-deref as below, it
seems that the transaction in btrfs_trans_handle struct has not been
initialized but used in __btrfs_abort_transaction() when calling
WRITE_ONCE(trans->transaction->aborted, errno).
[37093.705309] FAULT_INJECTION: forcing a failure.
[37093.705309] name failslab, interval 1, probability 0, space 0, times 0
[37093.706279] CPU: 6 PID: 22177 Comm: modprobe Tainted: G W
N 6.6.0-rc4+ #70
[37093.707019] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996),
BIOS 1.15.0-1 04/01/2014
[37093.707742] Call Trace:
[37093.707965] <TASK>
[37093.708161] dump_stack_lvl+0x33/0x50
[37093.708492] should_fail_ex+0x4c3/0x5c0
[37093.708836] ? alloc_bitmap+0xaf/0x150 [btrfs]
[37093.709332] should_failslab+0xa/0x20
[37093.709669] __kmem_cache_alloc_node+0x59/0x350
[37093.710068] ? alloc_bitmap+0xaf/0x150 [btrfs]
[37093.710545] ? alloc_bitmap+0xaf/0x150 [btrfs]
[37093.711015] __kmalloc_node+0x55/0x150
[37093.711371] ? btrfs_search_slot+0x17bd/0x2950 [btrfs]
[37093.711889] alloc_bitmap+0xaf/0x150 [btrfs]
[37093.712332] convert_free_space_to_bitmaps+0x266/0xd40 [btrfs]
[37093.712906] ? alloc_extent_buffer+0x1020/0x1020 [btrfs]
[37093.713444] ? btrfs_release_path+0x51/0x2b0 [btrfs]
[37093.713958] ? search_free_space_info+0x3b0/0x3b0 [btrfs]
[37093.714497] ? __check_free_space_extents+0x64e/0xb20 [btrfs]
[37093.715080] ? free_extent_buffer+0x136/0x290 [btrfs]
[37093.715556] ? btrfs_test_qgroups+0x860/0x860 [btrfs]
[37093.716036] ? btrfs_release_path+0x51/0x2b0 [btrfs]
[37093.716548] ? kasan_quarantine_put+0x21/0x1a0
[37093.716949] check_free_space_extents+0xac/0x170 [btrfs]
[37093.717497] test_empty_block_group+0xb9/0x140 [btrfs]
[37093.718025] ? __mutex_unlock_slowpath.constprop.0+0x2a0/0x2a0
[37093.718547] ? test_remove_all+0x180/0x180 [btrfs]
[37093.719031] ? add_block_group_free_space+0x168/0x2a0 [btrfs]
[37093.719595] run_test+0x5ba/0xb80 [btrfs]
[37093.720001] ? test_remove_all+0x180/0x180 [btrfs]
[37093.720475] ? test_empty_block_group+0x140/0x140 [btrfs]
[37093.721029] ? __wake_up_klogd.part.0+0x7d/0xc0
[37093.721422] ? printk_timed_ratelimit+0xb0/0xb0
[37093.721814] ? __kmem_cache_free+0xc4/0x310
[37093.722170] ? test_remove_all+0x180/0x180 [btrfs]
[37093.722651] ? test_remove_all+0x180/0x180 [btrfs]
[37093.723132] run_test_both_formats+0x27/0xc0 [btrfs]
[37093.723621] ? test_remove_all+0x180/0x180 [btrfs]
[37093.724103] btrfs_test_free_space_tree+0x12a/0x200 [btrfs]
[37093.724650] ? run_test_both_formats+0xc0/0xc0 [btrfs]
[37093.725149] ? test_remove_all+0x180/0x180 [btrfs]
[37093.725621] ? test_remove_beginning+0x190/0x190 [btrfs]
[37093.726127] ? test_remove_end+0x190/0x190 [btrfs]
[37093.726598] ? test_remove_middle+0x1c0/0x1c0 [btrfs]
[37093.727090] ? test_merge_left+0x290/0x290 [btrfs]
[37093.727556] ? test_merge_right+0x280/0x280 [btrfs]
[37093.728044] ? test_merge_both+0x320/0x320 [btrfs]
[37093.728512] ? test_merge_none+0x370/0x370 [btrfs]
[37093.728981] ? check_free_space_extents+0x170/0x170 [btrfs]
[37093.729506] ? btrfs_test_qgroups+0x587/0x860 [btrfs]
[37093.729997] btrfs_run_sanity_tests+0xc4/0x150 [btrfs]
[37093.730484] init_btrfs_fs+0x4b/0x340 [btrfs]
[37093.730956] ? btrfs_interface_init+0x20/0x20 [btrfs]
[37093.731453] do_one_initcall+0x87/0x2e0
[37093.731796] ? trace_event_raw_event_initcall_level+0x1b0/0x1b0
[37093.732305] ? memset_orig+0x82/0xac
[37093.732624] ? kasan_unpoison+0x40/0x70
[37093.732989] do_init_module+0x22d/0x730
[37093.733334] load_module+0x4ffd/0x67d0
[37093.733670] ? module_frob_arch_sections+0x20/0x20
[37093.734102] ? update_cfs_group+0x10a/0x290
[37093.734484] ? sched_clock_cpu+0x69/0x550
[37093.734856] ? kernel_read_file+0x3ca/0x510
[37093.735220] ? __x64_sys_fspick+0x2a0/0x2a0
[37093.735585] ? __schedule+0x9fa/0x2a50
[37093.735914] ? init_module_from_file+0xd2/0x130
[37093.736320] init_module_from_file+0xd2/0x130
[37093.736734] ? __ia32_sys_init_module+0xa0/0xa0
[37093.737144] ? _raw_spin_lock_bh+0xe0/0xe0
[37093.737500] ? cgroup_leave_frozen+0x1e1/0x2d0
[37093.737903] ? ptrace_stop.part.0+0x544/0x790
[37093.738290] idempotent_init_module+0x339/0x610
[37093.738696] ? init_module_from_file+0x130/0x130
[37093.739109] ? __fget_light+0x57/0x500
[37093.739426] __x64_sys_finit_module+0xba/0x130
[37093.739838] do_syscall_64+0x35/0x80
[37093.740161] entry_SYSCALL_64_after_hwframe+0x46/0xb0
[37093.740621] RIP: 0033:0x7fa73731b839
[37093.740942] Code: 00 f3 c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 40 00
48 89 f8 48 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f
05 <48> 3d 01 f0 ff ff 73 01 c3 48 8b 0d 1f f6 2c 00 f7 d8 64 89 01 48
[37093.742555] RSP: 002b:00007fff44e94228 EFLAGS: 00000246 ORIG_RAX:
0000000000000139
[37093.743224] RAX: ffffffffffffffda RBX: 0000564c90379db0 RCX:
00007fa73731b839
[37093.743858] RDX: 0000000000000000 RSI: 0000564c8e81bc2e RDI:
0000000000000003
[37093.744499] RBP: 0000564c8e81bc2e R08: 0000000000000000 R09:
0000564c90379db0
[37093.745106] R10: 0000000000000003 R11: 0000000000000246 R12:
0000000000000000
[37093.745730] R13: 0000564c90379e30 R14: 0000000000040000 R15:
0000564c90379db0
[37093.746351] </TASK>
[37093.746587] BTRFS error (device (efault): state A): Transaction
aborted (error -12)
[37093.747348] general protection fault, probably for non-canonical
address 0xdffffc0000000004: 0000 [#1] PREEMPT SMP KASAN
[37093.748299] KASAN: null-ptr-deref in range
[0x0000000000000020-0x0000000000000027]
[37093.748950] CPU: 6 PID: 22177 Comm: modprobe Tainted: G W
N 6.6.0-rc4+ #70
[37093.749682] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996),
BIOS 1.15.0-1 04/01/2014
[37093.750406] RIP: 0010:__btrfs_abort_transaction+0xab/0x180 [btrfs]
[37093.751049] Code: 48 89 fa 48 c1 ea 03 80 3c 02 00 0f 85 bc 00 00 00
48 b8 00 00 00 00 00 fc ff df 48 8b 5b 20 48 8d 7b 24 48 89 fa 48 c1 ea
03 <0f> b6 14 02 48 89 f8 83 e0 07 83 c0 03 38 d0 7c 04 84 d2 75 69 44
[37093.752636] RSP: 0018:ffff88811629f2f0 EFLAGS: 00010203
[37093.753101] RAX: dffffc0000000000 RBX: 0000000000000000 RCX:
00000000fffffff4
[37093.753719] RDX: 0000000000000004 RSI: ffffffffa066dec0 RDI:
0000000000000024
[37093.754337] RBP: ffff888117844000 R08: 0000000000000001 R09:
ffffed1022c53df8
[37093.754953] R10: ffff88811629efc7 R11: 0000000046525442 R12:
00000000fffffff4
[37093.755573] R13: ffffffffa066dec0 R14: 0000000000000152 R15:
0000000000000000
[37093.756207] FS: 00007fa7379f5540(0000) GS:ffff888119f00000(0000)
knlGS:0000000000000000
[37093.756904] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[37093.757407] CR2: 00007fff44e90ff8 CR3: 000000010f33d001 CR4:
0000000000770ee0
[37093.758026] DR0: 0000000000000000 DR1: 0000000000000000 DR2:
0000000000000000
[37093.758638] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7:
0000000000000400
[37093.759263] PKRU: 55555554
[37093.759509] Call Trace:
[37093.759743] <TASK>
[37093.759940] ? die_addr+0x3d/0xa0
[37093.760228] ? exc_general_protection+0x144/0x220
[37093.760633] ? asm_exc_general_protection+0x22/0x30
[37093.761069] ? __btrfs_abort_transaction+0xab/0x180 [btrfs]
[37093.761603] convert_free_space_to_bitmaps+0x6f1/0xd40 [btrfs]
[37093.762177] ? btrfs_release_path+0x51/0x2b0 [btrfs]
[37093.762698] ? search_free_space_info+0x3b0/0x3b0 [btrfs]
[37093.763238] ? __check_free_space_extents+0x64e/0xb20 [btrfs]
[37093.763788] ? free_extent_buffer+0x136/0x290 [btrfs]
[37093.764271] ? btrfs_test_qgroups+0x860/0x860 [btrfs]
[37093.764737] ? btrfs_release_path+0x51/0x2b0 [btrfs]
[37093.765233] ? kasan_quarantine_put+0x21/0x1a0
[37093.765640] check_free_space_extents+0xac/0x170 [btrfs]
[37093.766153] test_empty_block_group+0xb9/0x140 [btrfs]
[37093.766674] ? __mutex_unlock_slowpath.constprop.0+0x2a0/0x2a0
[37093.767184] ? test_remove_all+0x180/0x180 [btrfs]
[37093.767656] ? add_block_group_free_space+0x168/0x2a0 [btrfs]
[37093.768237] run_test+0x5ba/0xb80 [btrfs]
[37093.768646] ? test_remove_all+0x180/0x180 [btrfs]
[37093.769059] ? test_empty_block_group+0x140/0x140 [btrfs]
[37093.769590] ? __wake_up_klogd.part.0+0x7d/0xc0
[37093.770021] ? printk_timed_ratelimit+0xb0/0xb0
[37093.770427] ? __kmem_cache_free+0xc4/0x310
[37093.770822] ? test_remove_all+0x180/0x180 [btrfs]
[37093.771298] ? test_remove_all+0x180/0x180 [btrfs]
[37093.771768] run_test_both_formats+0x27/0xc0 [btrfs]
[37093.772257] ? test_remove_all+0x180/0x180 [btrfs]
[37093.772740] btrfs_test_free_space_tree+0x12a/0x200 [btrfs]
[37093.773296] ? run_test_both_formats+0xc0/0xc0 [btrfs]
[37093.773806] ? test_remove_all+0x180/0x180 [btrfs]
[37093.774281] ? test_remove_beginning+0x190/0x190 [btrfs]
[37093.774815] ? test_remove_end+0x190/0x190 [btrfs]
[37093.775278] ? test_remove_middle+0x1c0/0x1c0 [btrfs]
[37093.775793] ? test_merge_left+0x290/0x290 [btrfs]
[37093.776270] ? test_merge_right+0x280/0x280 [btrfs]
[37093.776768] ? test_merge_both+0x320/0x320 [btrfs]
[37093.777240] ? test_merge_none+0x370/0x370 [btrfs]
[37093.777714] ? check_free_space_extents+0x170/0x170 [btrfs]
[37093.778266] ? btrfs_test_qgroups+0x587/0x860 [btrfs]
[37093.778782] btrfs_run_sanity_tests+0xc4/0x150 [btrfs]
[37093.779307] init_btrfs_fs+0x4b/0x340 [btrfs]
[37093.779764] ? btrfs_interface_init+0x20/0x20 [btrfs]
[37093.780274] do_one_initcall+0x87/0x2e0
[37093.780612] ? trace_event_raw_event_initcall_level+0x1b0/0x1b0
[37093.781146] ? memset_orig+0x82/0xac
[37093.781473] ? kasan_unpoison+0x40/0x70
[37093.781812] do_init_module+0x22d/0x730
[37093.782151] load_module+0x4ffd/0x67d0
[37093.782477] ? module_frob_arch_sections+0x20/0x20
[37093.782930] ? update_cfs_group+0x10a/0x290
[37093.783300] ? sched_clock_cpu+0x69/0x550
[37093.783653] ? kernel_read_file+0x3ca/0x510
[37093.784018] ? __x64_sys_fspick+0x2a0/0x2a0
[37093.784388] ? __schedule+0x9fa/0x2a50
[37093.784726] ? init_module_from_file+0xd2/0x130
[37093.785125] init_module_from_file+0xd2/0x130
[37093.785529] ? __ia32_sys_init_module+0xa0/0xa0
[37093.785938] ? _raw_spin_lock_bh+0xe0/0xe0
[37093.786308] ? cgroup_leave_frozen+0x1e1/0x2d0
[37093.786708] ? ptrace_stop.part.0+0x544/0x790
[37093.787099] idempotent_init_module+0x339/0x610
[37093.787484] ? init_module_from_file+0x130/0x130
[37093.787894] ? __fget_light+0x57/0x500
[37093.788233] __x64_sys_finit_module+0xba/0x130
[37093.788623] do_syscall_64+0x35/0x80
[37093.788946] entry_SYSCALL_64_after_hwframe+0x46/0xb0
[37093.789407] RIP: 0033:0x7fa73731b839
[37093.789745] Code: 00 f3 c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 40 00
48 89 f8 48 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f
05 <48> 3d 01 f0 ff ff 73 01 c3 48 8b 0d 1f f6 2c 00 f7 d8 64 89 01 48
[37093.791390] RSP: 002b:00007fff44e94228 EFLAGS: 00000246 ORIG_RAX:
0000000000000139
[37093.792064] RAX: ffffffffffffffda RBX: 0000564c90379db0 RCX:
00007fa73731b839
[37093.792707] RDX: 0000000000000000 RSI: 0000564c8e81bc2e RDI:
0000000000000003
[37093.793328] RBP: 0000564c8e81bc2e R08: 0000000000000000 R09:
0000564c90379db0
[37093.793948] R10: 0000000000000003 R11: 0000000000000246 R12:
0000000000000000
[37093.794592] R13: 0000564c90379e30 R14: 0000000000040000 R15:
0000564c90379db0
[37093.795200] </TASK>
[37093.795403] Modules linked in: btrfs(+) blake2b_generic fpga_region
fpga_bridge [last unloaded: btrfs]
[37093.796373] Dumping ftrace buffer:
[37093.796704] (ftrace buffer empty)
[37093.797077] ---[ end trace 0000000000000000 ]---
[37093.797491] RIP: 0010:__btrfs_abort_transaction+0xab/0x180 [btrfs]
[37093.798105] Code: 48 89 fa 48 c1 ea 03 80 3c 02 00 0f 85 bc 00 00 00
48 b8 00 00 00 00 00 fc ff df 48 8b 5b 20 48 8d 7b 24 48 89 fa 48 c1 ea
03 <0f> b6 14 02 48 89 f8 83 e0 07 83 c0 03 38 d0 7c 04 84 d2 75 69 44
[37093.800294] RSP: 0018:ffff88811629f2f0 EFLAGS: 00010203
[37093.800813] RAX: dffffc0000000000 RBX: 0000000000000000 RCX:
00000000fffffff4
[37093.801424] RDX: 0000000000000004 RSI: ffffffffa066dec0 RDI:
0000000000000024
[37093.802097] RBP: ffff888117844000 R08: 0000000000000001 R09:
ffffed1022c53df8
[37093.802780] R10: ffff88811629efc7 R11: 0000000046525442 R12:
00000000fffffff4
[37093.803382] R13: ffffffffa066dec0 R14: 0000000000000152 R15:
0000000000000000
[37093.804051] FS: 00007fa7379f5540(0000) GS:ffff888119f00000(0000)
knlGS:0000000000000000
[37093.804802] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[37093.805295] CR2: 00007fff44e90ff8 CR3: 000000010f33d001 CR4:
0000000000770ee0
[37093.805971] DR0: 0000000000000000 DR1: 0000000000000000 DR2:
0000000000000000
[37093.806728] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7:
0000000000000400
[37093.807351] PKRU: 55555554
[37093.807639] Kernel panic - not syncing: Fatal exception
[37093.808876] Dumping ftrace buffer:
[37093.809128] (ftrace buffer empty)
[37093.809377] Kernel Offset: disabled
[37093.809684] Rebooting in 1 seconds..
Reported-by: Jinjie Ruan <ruanjinjie@huawei.com>
> +}
> +
> +static int test_remove_all(struct btrfs_trans_handle *trans,
> + struct btrfs_fs_info *fs_info,
> + struct btrfs_block_group_cache *cache,
> + struct btrfs_path *path)
> +{
> + struct free_space_extent extents[] = {};
> + int ret;
> +
> + ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid,
> + cache->key.offset);
> + if (ret) {
> + test_msg("Could not remove free space\n");
> + return ret;
> + }
> +
> + return check_free_space_extents(trans, fs_info, cache, path,
> + extents, ARRAY_SIZE(extents));
> +}
> +
> +static int test_remove_beginning(struct btrfs_trans_handle *trans,
> + struct btrfs_fs_info *fs_info,
> + struct btrfs_block_group_cache *cache,
> + struct btrfs_path *path)
> +{
> + struct free_space_extent extents[] = {
> + {cache->key.objectid + BITMAP_RANGE,
> + cache->key.offset - BITMAP_RANGE},
> + };
> + int ret;
> +
> + ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid, BITMAP_RANGE);
> + if (ret) {
> + test_msg("Could not remove free space\n");
> + return ret;
> + }
> +
> + return check_free_space_extents(trans, fs_info, cache, path,
> + extents, ARRAY_SIZE(extents));
> +
> +}
> +
> +static int test_remove_end(struct btrfs_trans_handle *trans,
> + struct btrfs_fs_info *fs_info,
> + struct btrfs_block_group_cache *cache,
> + struct btrfs_path *path)
> +{
> + struct free_space_extent extents[] = {
> + {cache->key.objectid, cache->key.offset - BITMAP_RANGE},
> + };
> + int ret;
> +
> + ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid +
> + cache->key.offset - BITMAP_RANGE,
> + BITMAP_RANGE);
> + if (ret) {
> + test_msg("Could not remove free space\n");
> + return ret;
> + }
> +
> + return check_free_space_extents(trans, fs_info, cache, path,
> + extents, ARRAY_SIZE(extents));
> +}
> +
> +static int test_remove_middle(struct btrfs_trans_handle *trans,
> + struct btrfs_fs_info *fs_info,
> + struct btrfs_block_group_cache *cache,
> + struct btrfs_path *path)
> +{
> + struct free_space_extent extents[] = {
> + {cache->key.objectid, BITMAP_RANGE},
> + {cache->key.objectid + 2 * BITMAP_RANGE,
> + cache->key.offset - 2 * BITMAP_RANGE},
> + };
> + int ret;
> +
> + ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid + BITMAP_RANGE,
> + BITMAP_RANGE);
> + if (ret) {
> + test_msg("Could not remove free space\n");
> + return ret;
> + }
> +
> + return check_free_space_extents(trans, fs_info, cache, path,
> + extents, ARRAY_SIZE(extents));
> +}
> +
> +static int test_merge_left(struct btrfs_trans_handle *trans,
> + struct btrfs_fs_info *fs_info,
> + struct btrfs_block_group_cache *cache,
> + struct btrfs_path *path)
> +{
> + struct free_space_extent extents[] = {
> + {cache->key.objectid, 2 * BITMAP_RANGE},
> + };
> + int ret;
> +
> + ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid,
> + cache->key.offset);
> + if (ret) {
> + test_msg("Could not remove free space\n");
> + return ret;
> + }
> +
> + ret = __add_to_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid, BITMAP_RANGE);
> + if (ret) {
> + test_msg("Could not add free space\n");
> + return ret;
> + }
> +
> + ret = __add_to_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid + BITMAP_RANGE,
> + BITMAP_RANGE);
> + if (ret) {
> + test_msg("Could not add free space\n");
> + return ret;
> + }
> +
> + return check_free_space_extents(trans, fs_info, cache, path,
> + extents, ARRAY_SIZE(extents));
> +}
> +
> +static int test_merge_right(struct btrfs_trans_handle *trans,
> + struct btrfs_fs_info *fs_info,
> + struct btrfs_block_group_cache *cache,
> + struct btrfs_path *path)
> +{
> + struct free_space_extent extents[] = {
> + {cache->key.objectid + BITMAP_RANGE, 2 * BITMAP_RANGE},
> + };
> + int ret;
> +
> + ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid,
> + cache->key.offset);
> + if (ret) {
> + test_msg("Could not remove free space\n");
> + return ret;
> + }
> +
> + ret = __add_to_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid + 2 * BITMAP_RANGE,
> + BITMAP_RANGE);
> + if (ret) {
> + test_msg("Could not add free space\n");
> + return ret;
> + }
> +
> + ret = __add_to_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid + BITMAP_RANGE,
> + BITMAP_RANGE);
> + if (ret) {
> + test_msg("Could not add free space\n");
> + return ret;
> + }
> +
> + return check_free_space_extents(trans, fs_info, cache, path,
> + extents, ARRAY_SIZE(extents));
> +}
> +
> +static int test_merge_both(struct btrfs_trans_handle *trans,
> + struct btrfs_fs_info *fs_info,
> + struct btrfs_block_group_cache *cache,
> + struct btrfs_path *path)
> +{
> + struct free_space_extent extents[] = {
> + {cache->key.objectid, 3 * BITMAP_RANGE},
> + };
> + int ret;
> +
> + ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid,
> + cache->key.offset);
> + if (ret) {
> + test_msg("Could not remove free space\n");
> + return ret;
> + }
> +
> + ret = __add_to_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid, BITMAP_RANGE);
> + if (ret) {
> + test_msg("Could not add free space\n");
> + return ret;
> + }
> +
> + ret = __add_to_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid + 2 * BITMAP_RANGE,
> + BITMAP_RANGE);
> + if (ret) {
> + test_msg("Could not add free space\n");
> + return ret;
> + }
> +
> + ret = __add_to_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid + BITMAP_RANGE,
> + BITMAP_RANGE);
> + if (ret) {
> + test_msg("Could not add free space\n");
> + return ret;
> + }
> +
> + return check_free_space_extents(trans, fs_info, cache, path,
> + extents, ARRAY_SIZE(extents));
> +}
> +
> +static int test_merge_none(struct btrfs_trans_handle *trans,
> + struct btrfs_fs_info *fs_info,
> + struct btrfs_block_group_cache *cache,
> + struct btrfs_path *path)
> +{
> + struct free_space_extent extents[] = {
> + {cache->key.objectid, BITMAP_RANGE},
> + {cache->key.objectid + 2 * BITMAP_RANGE, BITMAP_RANGE},
> + {cache->key.objectid + 4 * BITMAP_RANGE, BITMAP_RANGE},
> + };
> + int ret;
> +
> + ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid,
> + cache->key.offset);
> + if (ret) {
> + test_msg("Could not remove free space\n");
> + return ret;
> + }
> +
> + ret = __add_to_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid, BITMAP_RANGE);
> + if (ret) {
> + test_msg("Could not add free space\n");
> + return ret;
> + }
> +
> + ret = __add_to_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid + 4 * BITMAP_RANGE,
> + BITMAP_RANGE);
> + if (ret) {
> + test_msg("Could not add free space\n");
> + return ret;
> + }
> +
> + ret = __add_to_free_space_tree(trans, fs_info, cache, path,
> + cache->key.objectid + 2 * BITMAP_RANGE,
> + BITMAP_RANGE);
> + if (ret) {
> + test_msg("Could not add free space\n");
> + return ret;
> + }
> +
> + return check_free_space_extents(trans, fs_info, cache, path,
> + extents, ARRAY_SIZE(extents));
> +}
> +
> +typedef int (*test_func_t)(struct btrfs_trans_handle *,
> + struct btrfs_fs_info *,
> + struct btrfs_block_group_cache *,
> + struct btrfs_path *);
> +
> +static int run_test(test_func_t test_func, int bitmaps)
> +{
> + struct btrfs_root *root = NULL;
> + struct btrfs_block_group_cache *cache = NULL;
> + struct btrfs_trans_handle trans;
> + struct btrfs_path *path = NULL;
> + int ret;
> +
> + root = btrfs_alloc_dummy_root();
> + if (IS_ERR(root)) {
> + test_msg("Couldn't allocate dummy root\n");
> + ret = PTR_ERR(root);
> + goto out;
> + }
> +
> + root->fs_info = btrfs_alloc_dummy_fs_info();
> + if (!root->fs_info) {
> + test_msg("Couldn't allocate dummy fs info\n");
> + ret = -ENOMEM;
> + goto out;
> + }
> +
> + btrfs_set_super_compat_ro_flags(root->fs_info->super_copy,
> + BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE);
> + root->fs_info->free_space_root = root;
> + root->fs_info->tree_root = root;
> +
> + root->node = alloc_test_extent_buffer(root->fs_info, 4096);
> + if (!root->node) {
> + test_msg("Couldn't allocate dummy buffer\n");
> + ret = -ENOMEM;
> + goto out;
> + }
> + btrfs_set_header_level(root->node, 0);
> + btrfs_set_header_nritems(root->node, 0);
> + root->alloc_bytenr += 8192;
> +
> + cache = btrfs_alloc_dummy_block_group(8 * BITMAP_RANGE);
> + if (!cache) {
> + test_msg("Couldn't allocate dummy block group cache\n");
> + ret = -ENOMEM;
> + goto out;
> + }
> + cache->bitmap_low_thresh = 0;
> + cache->bitmap_high_thresh = (u32)-1;
> + cache->needs_free_space = 1;
> +
> + btrfs_init_dummy_trans(&trans);
> +
> + path = btrfs_alloc_path();
> + if (!path) {
> + test_msg("Couldn't allocate path\n");
> + return -ENOMEM;
> + }
> +
> + ret = add_block_group_free_space(&trans, root->fs_info, cache);
> + if (ret) {
> + test_msg("Could not add block group free space\n");
> + goto out;
> + }
> +
> + if (bitmaps) {
> + ret = convert_free_space_to_bitmaps(&trans, root->fs_info,
> + cache, path);
> + if (ret) {
> + test_msg("Could not convert block group to bitmaps\n");
> + goto out;
> + }
> + }
> +
> + ret = test_func(&trans, root->fs_info, cache, path);
> + if (ret)
> + goto out;
> +
> + ret = remove_block_group_free_space(&trans, root->fs_info, cache);
> + if (ret) {
> + test_msg("Could not remove block group free space\n");
> + goto out;
> + }
> +
> + if (btrfs_header_nritems(root->node) != 0) {
> + test_msg("Free space tree has leftover items\n");
> + ret = -EINVAL;
> + goto out;
> + }
> +
> + ret = 0;
> +out:
> + btrfs_free_path(path);
> + btrfs_free_dummy_block_group(cache);
> + btrfs_free_dummy_root(root);
> + return ret;
> +}
> +
> +static int run_test_both_formats(test_func_t test_func)
> +{
> + int ret;
> +
> + ret = run_test(test_func, 0);
> + if (ret)
> + return ret;
> + return run_test(test_func, 1);
> +}
> +
> +int btrfs_test_free_space_tree(void)
> +{
> + test_func_t tests[] = {
> + test_empty_block_group,
> + test_remove_all,
> + test_remove_beginning,
> + test_remove_end,
> + test_remove_middle,
> + test_merge_left,
> + test_merge_right,
> + test_merge_both,
> + test_merge_none,
> + };
> + int i;
> +
> + test_msg("Running free space tree tests\n");
> + for (i = 0; i < ARRAY_SIZE(tests); i++) {
> + int ret = run_test_both_formats(tests[i]);
> + if (ret) {
> + test_msg("%pf failed\n", tests[i]);
> + return ret;
> + }
> + }
> +
> + return 0;
> +}
> diff --git a/fs/btrfs/tests/qgroup-tests.c b/fs/btrfs/tests/qgroup-tests.c
> index 846d277b1901..8ea5d34bc5a2 100644
> --- a/fs/btrfs/tests/qgroup-tests.c
> +++ b/fs/btrfs/tests/qgroup-tests.c
> @@ -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");
>
^ permalink raw reply [flat|nested] 27+ messages in thread* Re: [PATCH v4 7/9] Btrfs: add free space tree sanity tests
2023-10-11 2:12 ` Jinjie Ruan
@ 2023-10-11 10:20 ` David Sterba
0 siblings, 0 replies; 27+ messages in thread
From: David Sterba @ 2023-10-11 10:20 UTC (permalink / raw)
To: Jinjie Ruan; +Cc: Omar Sandoval, linux-btrfs
On Wed, Oct 11, 2023 at 10:12:37AM +0800, Jinjie Ruan wrote:
>
>
> On 2015/9/30 11:50, Omar Sandoval wrote:
^^^^^^^^^
> > From: Omar Sandoval <osandov@fb.com>
> >
> > 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.
> >
> > Signed-off-by: Omar Sandoval <osandov@fb.com>
> > +static int test_empty_block_group(struct btrfs_trans_handle *trans,
> > + struct btrfs_fs_info *fs_info,
> > + struct btrfs_block_group_cache *cache,
> > + struct btrfs_path *path)
> > +{
> > + struct free_space_extent extents[] = {
> > + {cache->key.objectid, cache->key.offset},
> > + };
> > +
> > + return check_free_space_extents(trans, fs_info, cache, path,
> > + extents, ARRAY_SIZE(extents));
>
> Inject fault when probe btrfs.ko,
I wonder how valid is fault injection during self tests, there are lot
of stub structures that are half-initialized and hitting a NULL could be
possible while the tests would not need it and knowingly ignore it.
The whole transaction abort mechanism cannot work reliably, there's no
single start or commit of the transaction in the test/ code so
an abort (in the regular code) can't work.
> there is a null-ptr-deref as below, it
> seems that the transaction in btrfs_trans_handle struct has not been
> initialized but used in __btrfs_abort_transaction() when calling
> WRITE_ONCE(trans->transaction->aborted, errno).
Yeah, not all structures are initialized.
^ permalink raw reply [flat|nested] 27+ messages in thread
* [PATCH v4 8/9] Btrfs: wire up the free space tree to the extent tree
2015-09-30 3:50 [PATCH v4 0/9] Btrfs: free space B-tree Omar Sandoval
` (6 preceding siblings ...)
2015-09-30 3:50 ` [PATCH v4 7/9] Btrfs: add free space tree sanity tests Omar Sandoval
@ 2015-09-30 3:50 ` Omar Sandoval
2015-09-30 3:50 ` [PATCH v4 9/9] Btrfs: add free space tree mount option Omar Sandoval
` (3 subsequent siblings)
11 siblings, 0 replies; 27+ messages in thread
From: Omar Sandoval @ 2015-09-30 3:50 UTC (permalink / raw)
To: linux-btrfs; +Cc: Omar Sandoval
From: Omar Sandoval <osandov@fb.com>
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
Signed-off-by: Omar Sandoval <osandov@fb.com>
---
fs/btrfs/extent-tree.c | 36 +++++++++++++++++++++++++++++++++---
1 file changed, 33 insertions(+), 3 deletions(-)
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index a3b84ee8a28d..4ff8aeb621cc 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -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) {
@@ -6475,6 +6479,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);
@@ -7418,6 +7429,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",
@@ -7499,6 +7515,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 */
@@ -9366,6 +9387,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);
@@ -9586,6 +9609,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);
}
@@ -9615,6 +9640,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) {
/*
@@ -9977,6 +10003,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);
--
2.6.0
^ permalink raw reply related [flat|nested] 27+ messages in thread* [PATCH v4 9/9] Btrfs: add free space tree mount option
2015-09-30 3:50 [PATCH v4 0/9] Btrfs: free space B-tree Omar Sandoval
` (7 preceding siblings ...)
2015-09-30 3:50 ` [PATCH v4 8/9] Btrfs: wire up the free space tree to the extent tree Omar Sandoval
@ 2015-09-30 3:50 ` Omar Sandoval
2015-09-30 3:51 ` [PATCH v4 1/2] btrfs-progs: add basic awareness of the free space tree Omar Sandoval
` (2 subsequent siblings)
11 siblings, 0 replies; 27+ messages in thread
From: Omar Sandoval @ 2015-09-30 3:50 UTC (permalink / raw)
To: linux-btrfs; +Cc: Omar Sandoval
From: Omar Sandoval <osandov@fb.com>
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.
Signed-off-by: Omar Sandoval <osandov@fb.com>
---
fs/btrfs/ctree.h | 7 ++++++-
fs/btrfs/disk-io.c | 38 ++++++++++++++++++++++++++++++++++++++
fs/btrfs/super.c | 53 ++++++++++++++++++++++++++++++++++++++++++++---------
3 files changed, 88 insertions(+), 10 deletions(-)
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 0888c3e2cc7d..ed610f9c04b2 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -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
@@ -2203,6 +2206,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)
@@ -3744,6 +3748,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);
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 295795aebe0b..5295de1e3e2c 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -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"
@@ -1647,6 +1648,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) {
@@ -2144,6 +2148,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)
@@ -2445,6 +2450,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;
}
@@ -3069,6 +3083,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);
diff --git a/fs/btrfs/super.c b/fs/btrfs/super.c
index 442bf434b783..bfdaf123f4e9 100644
--- a/fs/btrfs/super.c
+++ b/fs/btrfs/super.c
@@ -312,10 +312,11 @@ enum {
Opt_nossd, Opt_ssd_spread, Opt_thread_pool, Opt_noacl, Opt_compress,
Opt_compress_type, Opt_compress_force, Opt_compress_force_type,
Opt_notreelog, Opt_ratio, Opt_flushoncommit, Opt_discard,
- Opt_space_cache, Opt_clear_cache, Opt_user_subvol_rm_allowed,
- 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_space_cache, Opt_space_cache_version, Opt_clear_cache,
+ Opt_user_subvol_rm_allowed, 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_rescan_uuid_tree,
Opt_commit_interval, Opt_barrier, Opt_nodefrag, Opt_nodiscard,
Opt_noenospc_debug, Opt_noflushoncommit, Opt_acl, Opt_datacow,
@@ -354,6 +355,7 @@ static match_table_t tokens = {
{Opt_discard, "discard"},
{Opt_nodiscard, "nodiscard"},
{Opt_space_cache, "space_cache"},
+ {Opt_space_cache_version, "space_cache=%s"},
{Opt_clear_cache, "clear_cache"},
{Opt_user_subvol_rm_allowed, "user_subvol_rm_allowed"},
{Opt_enospc_debug, "enospc_debug"},
@@ -392,7 +394,9 @@ int btrfs_parse_options(struct btrfs_root *root, char *options)
bool compress_force = false;
cache_gen = btrfs_super_cache_generation(root->fs_info->super_copy);
- if (cache_gen)
+ if (btrfs_fs_compat_ro(root->fs_info, FREE_SPACE_TREE))
+ btrfs_set_opt(info->mount_opt, FREE_SPACE_TREE);
+ else if (cache_gen)
btrfs_set_opt(info->mount_opt, SPACE_CACHE);
if (!options)
@@ -626,15 +630,35 @@ int btrfs_parse_options(struct btrfs_root *root, char *options)
"turning off discard");
break;
case Opt_space_cache:
- btrfs_set_and_info(root, SPACE_CACHE,
- "enabling disk space caching");
+ case Opt_space_cache_version:
+ if (token == Opt_space_cache ||
+ strcmp(args[0].from, "v1") == 0) {
+ btrfs_clear_opt(root->fs_info->mount_opt,
+ FREE_SPACE_TREE);
+ btrfs_set_and_info(root, SPACE_CACHE,
+ "enabling disk space caching");
+ } else if (strcmp(args[0].from, "v2") == 0) {
+ btrfs_clear_opt(root->fs_info->mount_opt,
+ SPACE_CACHE);
+ btrfs_set_and_info(root, FREE_SPACE_TREE,
+ "enabling free space tree");
+ } else {
+ ret = -EINVAL;
+ goto out;
+ }
break;
case Opt_rescan_uuid_tree:
btrfs_set_opt(info->mount_opt, RESCAN_UUID_TREE);
break;
case Opt_no_space_cache:
- btrfs_clear_and_info(root, SPACE_CACHE,
- "disabling disk space caching");
+ if (btrfs_test_opt(root, SPACE_CACHE)) {
+ btrfs_clear_and_info(root, SPACE_CACHE,
+ "disabling disk space caching");
+ }
+ if (btrfs_test_opt(root, FREE_SPACE_TREE)) {
+ btrfs_clear_and_info(root, FREE_SPACE_TREE,
+ "disabling free space tree");
+ }
break;
case Opt_inode_cache:
btrfs_set_pending_and_info(info, INODE_MAP_CACHE,
@@ -747,8 +771,17 @@ int btrfs_parse_options(struct btrfs_root *root, char *options)
}
}
out:
+ if (btrfs_fs_compat_ro(root->fs_info, FREE_SPACE_TREE) &&
+ !btrfs_test_opt(root, FREE_SPACE_TREE) &&
+ !btrfs_test_opt(root, CLEAR_CACHE)) {
+ btrfs_err(root->fs_info, "cannot disable free space tree");
+ ret = -EINVAL;
+
+ }
if (!ret && btrfs_test_opt(root, SPACE_CACHE))
btrfs_info(root->fs_info, "disk space caching is enabled");
+ if (!ret && btrfs_test_opt(root, FREE_SPACE_TREE))
+ btrfs_info(root->fs_info, "using free space tree");
kfree(orig);
return ret;
}
@@ -1155,6 +1188,8 @@ static int btrfs_show_options(struct seq_file *seq, struct dentry *dentry)
seq_puts(seq, ",noacl");
if (btrfs_test_opt(root, SPACE_CACHE))
seq_puts(seq, ",space_cache");
+ else if (btrfs_test_opt(root, FREE_SPACE_TREE))
+ seq_puts(seq, ",space_cache=v2");
else
seq_puts(seq, ",nospace_cache");
if (btrfs_test_opt(root, RESCAN_UUID_TREE))
--
2.6.0
^ permalink raw reply related [flat|nested] 27+ messages in thread* [PATCH v4 1/2] btrfs-progs: add basic awareness of the free space tree
2015-09-30 3:50 [PATCH v4 0/9] Btrfs: free space B-tree Omar Sandoval
` (8 preceding siblings ...)
2015-09-30 3:50 ` [PATCH v4 9/9] Btrfs: add free space tree mount option Omar Sandoval
@ 2015-09-30 3:51 ` Omar Sandoval
2015-09-30 3:51 ` [PATCH v4 2/2] btrfs-progs: check the free space tree in btrfsck Omar Sandoval
2015-09-30 8:31 ` [PATCH v4 0/9] Btrfs: free space B-tree Omar Sandoval
2015-10-02 11:47 ` Austin S Hemmelgarn
11 siblings, 1 reply; 27+ messages in thread
From: Omar Sandoval @ 2015-09-30 3:51 UTC (permalink / raw)
To: linux-btrfs; +Cc: Omar Sandoval
From: Omar Sandoval <osandov@fb.com>
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.
Signed-off-by: Omar Sandoval <osandov@fb.com>
---
btrfs-debug-tree.c | 4 ++++
ctree.h | 49 ++++++++++++++++++++++++++++++++++++++++++++++++-
disk-io.c | 16 +++++++++++++++-
print-tree.c | 25 +++++++++++++++++++++++++
4 files changed, 92 insertions(+), 2 deletions(-)
diff --git a/btrfs-debug-tree.c b/btrfs-debug-tree.c
index 7d8e876f1a2d..2aa5bd11d1b6 100644
--- a/btrfs-debug-tree.c
+++ b/btrfs-debug-tree.c
@@ -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");
diff --git a/ctree.h b/ctree.h
index c57f9cad5082..a37f3d1fcc48 100644
--- a/ctree.h
+++ b/ctree.h
@@ -76,6 +76,9 @@ struct btrfs_free_space_ctl;
/* for storing items that use the BTRFS_UUID_KEY* */
#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
@@ -453,6 +456,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)
@@ -476,9 +481,10 @@ struct btrfs_super_block {
#define BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA (1ULL << 8)
#define BTRFS_FEATURE_INCOMPAT_NO_HOLES (1ULL << 9)
-
#define BTRFS_FEATURE_COMPAT_SUPP 0ULL
+
#define BTRFS_FEATURE_COMPAT_RO_SUPP 0ULL
+
#define BTRFS_FEATURE_INCOMPAT_SUPP \
(BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF | \
BTRFS_FEATURE_INCOMPAT_DEFAULT_SUBVOL | \
@@ -898,6 +904,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)
+
struct btrfs_qgroup_info_item {
__le64 generation;
__le64 referenced;
@@ -965,6 +978,7 @@ struct btrfs_fs_info {
struct btrfs_root *dev_root;
struct btrfs_root *csum_root;
struct btrfs_root *quota_root;
+ struct btrfs_root *free_space_root;
struct rb_root fs_root_tree;
@@ -1157,6 +1171,27 @@ struct btrfs_root {
*/
#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
@@ -1394,6 +1429,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_STACK_FUNCS(stack_inode_ref_name_len, struct btrfs_inode_ref, name_len, 16);
@@ -2193,6 +2233,13 @@ static inline int btrfs_fs_incompat(struct btrfs_fs_info *fs_info, u64 flag)
return !!(btrfs_super_incompat_flags(disk_super) & flag);
}
+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);
+}
+
/* helper function to cast into the data area of the leaf. */
#define btrfs_item_ptr(leaf, slot, type) \
((type *)(btrfs_leaf_data(leaf) + \
diff --git a/disk-io.c b/disk-io.c
index 8496aded31c4..ae9d6e1abb23 100644
--- a/disk-io.c
+++ b/disk-io.c
@@ -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)
diff --git a/print-tree.c b/print-tree.c
index dc1d2764ae91..9dc058b58bde 100644
--- a/print-tree.c
+++ b/print-tree.c
@@ -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;
--
2.6.0
^ permalink raw reply related [flat|nested] 27+ messages in thread* [PATCH v4 2/2] btrfs-progs: check the free space tree in btrfsck
2015-09-30 3:51 ` [PATCH v4 1/2] btrfs-progs: add basic awareness of the free space tree Omar Sandoval
@ 2015-09-30 3:51 ` Omar Sandoval
0 siblings, 0 replies; 27+ messages in thread
From: Omar Sandoval @ 2015-09-30 3:51 UTC (permalink / raw)
To: linux-btrfs; +Cc: Omar Sandoval
From: Omar Sandoval <osandov@fb.com>
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.
Signed-off-by: Omar Sandoval <osandov@fb.com>
---
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
diff --git a/Makefile.in b/Makefile.in
index 514a76f2a667..a4d353e54376 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -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 \
diff --git a/cmds-check.c b/cmds-check.c
index fe3f782b2172..19e1a3fe083a 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -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;
diff --git a/ctree.h b/ctree.h
index a37f3d1fcc48..2e1e631728c1 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2329,6 +2329,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,
diff --git a/extent-tree.c b/extent-tree.c
index 0c8152a336b1..ffd2cf0c86b2 100644
--- a/extent-tree.c
+++ b/extent-tree.c
@@ -4001,3 +4001,121 @@ fail:
btrfs_release_path(&path);
return ret;
}
+
+
+static int add_excluded_extent(struct btrfs_root *root,
+ u64 start, u64 num_bytes)
+{
+ u64 end = start + num_bytes - 1;
+ set_extent_bits(&root->fs_info->pinned_extents,
+ start, end, EXTENT_UPTODATE, GFP_NOFS);
+ return 0;
+}
+
+void free_excluded_extents(struct btrfs_root *root,
+ struct btrfs_block_group_cache *cache)
+{
+ u64 start, end;
+
+ start = cache->key.objectid;
+ end = start + cache->key.offset - 1;
+
+ clear_extent_bits(&root->fs_info->pinned_extents,
+ start, end, EXTENT_UPTODATE, GFP_NOFS);
+}
+
+int exclude_super_stripes(struct btrfs_root *root,
+ struct btrfs_block_group_cache *cache)
+{
+ u64 bytenr;
+ u64 *logical;
+ int stripe_len;
+ int i, nr, ret;
+
+ if (cache->key.objectid < BTRFS_SUPER_INFO_OFFSET) {
+ stripe_len = BTRFS_SUPER_INFO_OFFSET - cache->key.objectid;
+ cache->bytes_super += stripe_len;
+ ret = add_excluded_extent(root, cache->key.objectid,
+ stripe_len);
+ if (ret)
+ return ret;
+ }
+
+ for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
+ bytenr = btrfs_sb_offset(i);
+ ret = btrfs_rmap_block(&root->fs_info->mapping_tree,
+ cache->key.objectid, bytenr,
+ 0, &logical, &nr, &stripe_len);
+ if (ret)
+ return ret;
+
+ while (nr--) {
+ u64 start, len;
+
+ if (logical[nr] > cache->key.objectid +
+ cache->key.offset)
+ continue;
+
+ if (logical[nr] + stripe_len <= cache->key.objectid)
+ continue;
+
+ start = logical[nr];
+ if (start < cache->key.objectid) {
+ start = cache->key.objectid;
+ len = (logical[nr] + stripe_len) - start;
+ } else {
+ len = min_t(u64, stripe_len,
+ cache->key.objectid +
+ cache->key.offset - start);
+ }
+
+ cache->bytes_super += len;
+ ret = add_excluded_extent(root, start, len);
+ if (ret) {
+ kfree(logical);
+ return ret;
+ }
+ }
+
+ kfree(logical);
+ }
+ return 0;
+}
+
+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;
+
+ while (start < end) {
+ ret = find_first_extent_bit(&info->pinned_extents, start,
+ &extent_start, &extent_end,
+ EXTENT_DIRTY | EXTENT_UPTODATE);
+ if (ret)
+ break;
+
+ if (extent_start <= start) {
+ start = extent_end + 1;
+ } else if (extent_start > start && extent_start < end) {
+ size = extent_start - start;
+ total_added += size;
+ ret = btrfs_add_free_space(block_group->free_space_ctl,
+ start, size);
+ BUG_ON(ret); /* -ENOMEM or logic error */
+ start = extent_end + 1;
+ } else {
+ break;
+ }
+ }
+
+ if (start < end) {
+ size = end - start;
+ total_added += size;
+ ret = btrfs_add_free_space(block_group->free_space_ctl, start,
+ size);
+ BUG_ON(ret); /* -ENOMEM or logic error */
+ }
+
+ return total_added;
+}
diff --git a/extent_io.c b/extent_io.c
index 07695ef8a097..079ab7f2fb7d 100644
--- a/extent_io.c
+++ b/extent_io.c
@@ -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));
+}
diff --git a/extent_io.h b/extent_io.h
index 27c4b6931c97..a9a7353556a7 100644
--- a/extent_io.h
+++ b/extent_io.h
@@ -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,
diff --git a/free-space-cache.c b/free-space-cache.c
index 19ab0c904a71..d10a5f517b10 100644
--- a/free-space-cache.c
+++ b/free-space-cache.c
@@ -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;
diff --git a/free-space-cache.h b/free-space-cache.h
index 85411a10e64b..9214077a1b27 100644
--- a/free-space-cache.h
+++ b/free-space-cache.h
@@ -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
diff --git a/free-space-tree.c b/free-space-tree.c
new file mode 100644
index 000000000000..a323e8aae997
--- /dev/null
+++ b/free-space-tree.c
@@ -0,0 +1,267 @@
+/*
+ * 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.
+ */
+
+#include "ctree.h"
+#include "disk-io.h"
+#include "free-space-cache.h"
+#include "free-space-tree.h"
+
+static struct btrfs_free_space_info *
+search_free_space_info(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path, int cow)
+{
+ struct btrfs_root *root = fs_info->free_space_root;
+ struct btrfs_key key;
+ int ret;
+
+ key.objectid = block_group->key.objectid;
+ key.type = BTRFS_FREE_SPACE_INFO_KEY;
+ key.offset = block_group->key.offset;
+
+ ret = btrfs_search_slot(trans, root, &key, path, 0, cow);
+ if (ret < 0)
+ return ERR_PTR(ret);
+ if (ret != 0)
+ return ERR_PTR(-ENOENT);
+
+ return btrfs_item_ptr(path->nodes[0], path->slots[0],
+ struct btrfs_free_space_info);
+}
+
+static int free_space_test_bit(struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path, u64 offset,
+ u64 sectorsize)
+{
+ struct extent_buffer *leaf;
+ struct btrfs_key key;
+ u64 found_start, found_end;
+ unsigned long ptr, i;
+
+ leaf = path->nodes[0];
+ btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
+ ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
+
+ found_start = key.objectid;
+ found_end = key.objectid + key.offset;
+ ASSERT(offset >= found_start && offset < found_end);
+
+ ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
+ i = (offset - found_start) / sectorsize;
+ return !!extent_buffer_test_bit(leaf, ptr, i);
+}
+
+static int load_free_space_bitmaps(struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path,
+ u32 expected_extent_count,
+ int *errors)
+{
+ struct btrfs_root *root = fs_info->free_space_root;
+ struct btrfs_key key;
+ int prev_bit = 0, bit;
+ u64 extent_start = 0;
+ u64 start, end, offset;
+ u32 extent_count = 0;
+ int ret;
+
+ start = block_group->key.objectid;
+ end = block_group->key.objectid + block_group->key.offset;
+
+ while (1) {
+ ret = btrfs_next_item(root, path);
+ if (ret < 0)
+ goto out;
+ if (ret)
+ break;
+
+ btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+
+ if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
+ break;
+
+ if (key.type != BTRFS_FREE_SPACE_BITMAP_KEY) {
+ fprintf(stderr, "unexpected key of type %u\n", key.type);
+ (*errors)++;
+ break;
+ }
+ if (key.objectid >= end) {
+ fprintf(stderr, "free space bitmap starts at %Lu, beyond end of block group %Lu-%Lu\n",
+ key.objectid, start, end);
+ (*errors)++;
+ break;
+ }
+ if (key.objectid + key.offset > end) {
+ fprintf(stderr, "free space bitmap ends at %Lu, beyond end of block group %Lu-%Lu\n",
+ key.objectid, start, end);
+ (*errors)++;
+ break;
+ }
+
+ offset = key.objectid;
+ while (offset < key.objectid + key.offset) {
+ bit = free_space_test_bit(block_group, path, offset,
+ root->sectorsize);
+ if (prev_bit == 0 && bit == 1) {
+ extent_start = offset;
+ } else if (prev_bit == 1 && bit == 0) {
+ add_new_free_space(block_group, fs_info, extent_start, offset);
+ extent_count++;
+ }
+ prev_bit = bit;
+ offset += root->sectorsize;
+ }
+ }
+
+ if (prev_bit == 1) {
+ add_new_free_space(block_group, fs_info, extent_start, end);
+ extent_count++;
+ }
+
+ if (extent_count != expected_extent_count) {
+ fprintf(stderr, "free space info recorded %u extents, counted %u\n",
+ expected_extent_count, extent_count);
+ (*errors)++;
+ }
+
+ ret = 0;
+out:
+ return ret;
+}
+
+static int load_free_space_extents(struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group,
+ struct btrfs_path *path,
+ u32 expected_extent_count,
+ int *errors)
+{
+ struct btrfs_root *root = fs_info->free_space_root;
+ struct btrfs_key key, prev_key;
+ int have_prev = 0;
+ u64 start, end;
+ u32 extent_count = 0;
+ int ret;
+
+ start = block_group->key.objectid;
+ end = block_group->key.objectid + block_group->key.offset;
+
+ while (1) {
+ ret = btrfs_next_item(root, path);
+ if (ret < 0)
+ goto out;
+ if (ret)
+ break;
+
+ btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+
+ if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
+ break;
+
+ if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
+ fprintf(stderr, "unexpected key of type %u\n", key.type);
+ (*errors)++;
+ break;
+ }
+ if (key.objectid >= end) {
+ fprintf(stderr, "free space extent starts at %Lu, beyond end of block group %Lu-%Lu\n",
+ key.objectid, start, end);
+ (*errors)++;
+ break;
+ }
+ if (key.objectid + key.offset > end) {
+ fprintf(stderr, "free space extent ends at %Lu, beyond end of block group %Lu-%Lu\n",
+ key.objectid, start, end);
+ (*errors)++;
+ break;
+ }
+
+ if (have_prev) {
+ u64 cur_start = key.objectid;
+ u64 cur_end = cur_start + key.offset;
+ u64 prev_start = prev_key.objectid;
+ u64 prev_end = prev_start + prev_key.offset;
+
+ if (cur_start < prev_end) {
+ fprintf(stderr, "free space extent %Lu-%Lu overlaps with previous %Lu-%Lu\n",
+ cur_start, cur_end,
+ prev_start, prev_end);
+ (*errors)++;
+ } else if (cur_start == prev_end) {
+ fprintf(stderr, "free space extent %Lu-%Lu is unmerged with previous %Lu-%Lu\n",
+ cur_start, cur_end,
+ prev_start, prev_end);
+ (*errors)++;
+ }
+ }
+
+ add_new_free_space(block_group, fs_info, key.objectid, key.objectid + key.offset);
+ extent_count++;
+
+ prev_key = key;
+ have_prev = 1;
+ }
+
+ if (extent_count != expected_extent_count) {
+ fprintf(stderr, "free space info recorded %u extents, counted %u\n",
+ expected_extent_count, extent_count);
+ (*errors)++;
+ }
+
+ ret = 0;
+out:
+ return ret;
+}
+
+int load_free_space_tree(struct btrfs_fs_info *fs_info,
+ struct btrfs_block_group_cache *block_group)
+{
+ struct btrfs_free_space_info *info;
+ struct btrfs_path *path;
+ u32 extent_count, flags;
+ int errors = 0;
+ int ret;
+
+ path = btrfs_alloc_path();
+ if (!path)
+ return -ENOMEM;
+ path->reada = 1;
+
+ info = search_free_space_info(NULL, fs_info, block_group, path, 0);
+ if (IS_ERR(info)) {
+ ret = PTR_ERR(info);
+ goto out;
+ }
+ extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
+ flags = btrfs_free_space_flags(path->nodes[0], info);
+
+ if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
+ ret = load_free_space_bitmaps(fs_info, block_group, path,
+ extent_count, &errors);
+ } else {
+ ret = load_free_space_extents(fs_info, block_group, path,
+ extent_count, &errors);
+ }
+ if (ret)
+ goto out;
+
+ ret = 0;
+out:
+ btrfs_free_path(path);
+ return ret ? ret : errors;
+}
diff --git a/free-space-tree.h b/free-space-tree.h
new file mode 100644
index 000000000000..7529a46890da
--- /dev/null
+++ b/free-space-tree.h
@@ -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
--
2.6.0
^ permalink raw reply related [flat|nested] 27+ messages in thread
* Re: [PATCH v4 0/9] Btrfs: free space B-tree
2015-09-30 3:50 [PATCH v4 0/9] Btrfs: free space B-tree Omar Sandoval
` (9 preceding siblings ...)
2015-09-30 3:51 ` [PATCH v4 1/2] btrfs-progs: add basic awareness of the free space tree Omar Sandoval
@ 2015-09-30 8:31 ` Omar Sandoval
2015-10-02 11:47 ` Austin S Hemmelgarn
11 siblings, 0 replies; 27+ messages in thread
From: Omar Sandoval @ 2015-09-30 8:31 UTC (permalink / raw)
To: linux-btrfs
On Tue, Sep 29, 2015 at 08:50:29PM -0700, Omar Sandoval wrote:
> Hi,
>
> Here's one more reroll of the free space B-tree patches, a more scalable
> alternative to the free space cache. Minimal changes this time around, I
> mainly wanted to resend this after Holger and I cleared up his bug
> report here: http://www.spinics.net/lists/linux-btrfs/msg47165.html. It
> initially looked like it was a bug in a patch that Josef sent, then in
> this series, but finally Holger and I figured out that it was something
> else in the queue of patches he carries around, we just don't know what
> yet (I'm in the middle of looking into it).
Okay, I tracked down Holger's bug to a bad merge in his patch queue, so
we're off the hook.
> While trying to reproduce
> that bug, I ran xfstests about a trillion times and a bunch of stress
> tests, so this is fairly well tested now. Additionally, the last time
> around, Holger and Austin both bravely offered their Tested-bys on the
> series. I wasn't sure which patch(es) to tack them onto so here they
> are:
>
> Tested-by: Holger Hoffstätte <holger.hoffstaette@googlemail.com>
> Tested-by: Austin S. Hemmelgarn <ahferroin7@gmail.com>
>
> Thanks, everyone!
>
> Omar
>
> Changes from v3->v4:
>
> - Added a missing btrfs_end_transaction() to btrfs_create_free_space_tree() and
> btrfs_clear_free_space_tree() in the error cases after we abort the
> transaction (see http://www.spinics.net/lists/linux-btrfs/msg47545.html)
> - Rebased the kernel patches on v4.3-rc3
> - Rebased the progs patches on v4.2.1
>
> v3: http://www.spinics.net/lists/linux-btrfs/msg47095.html
>
> 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 | 1584 ++++++++++++++++++++++++++++++++
> 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, 2925 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
>
> --
> 2.6.0
>
--
Omar
^ permalink raw reply [flat|nested] 27+ messages in thread* Re: [PATCH v4 0/9] Btrfs: free space B-tree
2015-09-30 3:50 [PATCH v4 0/9] Btrfs: free space B-tree Omar Sandoval
` (10 preceding siblings ...)
2015-09-30 8:31 ` [PATCH v4 0/9] Btrfs: free space B-tree Omar Sandoval
@ 2015-10-02 11:47 ` Austin S Hemmelgarn
2015-11-03 18:13 ` Tobias Holst
11 siblings, 1 reply; 27+ messages in thread
From: Austin S Hemmelgarn @ 2015-10-02 11:47 UTC (permalink / raw)
To: Omar Sandoval, linux-btrfs
[-- Attachment #1: Type: text/plain, Size: 5220 bytes --]
On 2015-09-29 23:50, Omar Sandoval wrote:
> Hi,
>
> Here's one more reroll of the free space B-tree patches, a more scalable
> alternative to the free space cache. Minimal changes this time around, I
> mainly wanted to resend this after Holger and I cleared up his bug
> report here: http://www.spinics.net/lists/linux-btrfs/msg47165.html. It
> initially looked like it was a bug in a patch that Josef sent, then in
> this series, but finally Holger and I figured out that it was something
> else in the queue of patches he carries around, we just don't know what
> yet (I'm in the middle of looking into it). While trying to reproduce
> that bug, I ran xfstests about a trillion times and a bunch of stress
> tests, so this is fairly well tested now. Additionally, the last time
> around, Holger and Austin both bravely offered their Tested-bys on the
> series. I wasn't sure which patch(es) to tack them onto so here they
> are:
>
> Tested-by: Holger Hoffstätte <holger.hoffstaette@googlemail.com>
> Tested-by: Austin S. Hemmelgarn <ahferroin7@gmail.com>
I've re-run the same testing I did for the last iteration, and also
tested that the btrfs_end_transaction thing mentioned below works right
now (Ironically that's one of the few things I didn't think of testing
last time :)), so the Tested-by from me is current now.
>
> Thanks, everyone!
>
> Omar
>
> Changes from v3->v4:
>
> - Added a missing btrfs_end_transaction() to btrfs_create_free_space_tree() and
> btrfs_clear_free_space_tree() in the error cases after we abort the
> transaction (see http://www.spinics.net/lists/linux-btrfs/msg47545.html)
> - Rebased the kernel patches on v4.3-rc3
> - Rebased the progs patches on v4.2.1
>
> v3: http://www.spinics.net/lists/linux-btrfs/msg47095.html
>
> 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 | 1584 ++++++++++++++++++++++++++++++++
> 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, 2925 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
>
[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 3019 bytes --]
^ permalink raw reply [flat|nested] 27+ messages in thread* Re: [PATCH v4 0/9] Btrfs: free space B-tree
2015-10-02 11:47 ` Austin S Hemmelgarn
@ 2015-11-03 18:13 ` Tobias Holst
2015-11-03 18:34 ` Chris Mason
0 siblings, 1 reply; 27+ messages in thread
From: Tobias Holst @ 2015-11-03 18:13 UTC (permalink / raw)
To: Austin S Hemmelgarn; +Cc: Omar Sandoval, linux-btrfs@vger.kernel.org
Hi
Anything new on this topic?
I think it would be a great thing and should be merged as soon as it
is stable. :)
Regards,
Tobias
2015-10-02 13:47 GMT+02:00 Austin S Hemmelgarn <ahferroin7@gmail.com>:
> On 2015-09-29 23:50, Omar Sandoval wrote:
>>
>> Hi,
>>
>> Here's one more reroll of the free space B-tree patches, a more scalable
>> alternative to the free space cache. Minimal changes this time around, I
>> mainly wanted to resend this after Holger and I cleared up his bug
>> report here: http://www.spinics.net/lists/linux-btrfs/msg47165.html. It
>> initially looked like it was a bug in a patch that Josef sent, then in
>> this series, but finally Holger and I figured out that it was something
>> else in the queue of patches he carries around, we just don't know what
>> yet (I'm in the middle of looking into it). While trying to reproduce
>> that bug, I ran xfstests about a trillion times and a bunch of stress
>> tests, so this is fairly well tested now. Additionally, the last time
>> around, Holger and Austin both bravely offered their Tested-bys on the
>> series. I wasn't sure which patch(es) to tack them onto so here they
>> are:
>>
>> Tested-by: Holger Hoffstätte <holger.hoffstaette@googlemail.com>
>> Tested-by: Austin S. Hemmelgarn <ahferroin7@gmail.com>
>
> I've re-run the same testing I did for the last iteration, and also tested
> that the btrfs_end_transaction thing mentioned below works right now
> (Ironically that's one of the few things I didn't think of testing last time
> :)), so the Tested-by from me is current now.
>
>>
>> Thanks, everyone!
>>
>> Omar
>>
>> Changes from v3->v4:
>>
>> - Added a missing btrfs_end_transaction() to
>> btrfs_create_free_space_tree() and
>> btrfs_clear_free_space_tree() in the error cases after we abort the
>> transaction (see
>> http://www.spinics.net/lists/linux-btrfs/msg47545.html)
>> - Rebased the kernel patches on v4.3-rc3
>> - Rebased the progs patches on v4.2.1
>>
>> v3: http://www.spinics.net/lists/linux-btrfs/msg47095.html
>>
>> 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 | 1584
>> ++++++++++++++++++++++++++++++++
>> 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, 2925 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
>>
>
>
^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: [PATCH v4 0/9] Btrfs: free space B-tree
2015-11-03 18:13 ` Tobias Holst
@ 2015-11-03 18:34 ` Chris Mason
2015-11-03 18:59 ` Tobias Holst
0 siblings, 1 reply; 27+ messages in thread
From: Chris Mason @ 2015-11-03 18:34 UTC (permalink / raw)
To: Tobias Holst
Cc: Austin S Hemmelgarn, Omar Sandoval, linux-btrfs@vger.kernel.org
On Tue, Nov 03, 2015 at 07:13:37PM +0100, Tobias Holst wrote:
> Hi
>
> Anything new on this topic?
>
> I think it would be a great thing and should be merged as soon as it
> is stable. :)
I've been testing it, but my plan is 4.5.
-chris
^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: [PATCH v4 0/9] Btrfs: free space B-tree
2015-11-03 18:34 ` Chris Mason
@ 2015-11-03 18:59 ` Tobias Holst
0 siblings, 0 replies; 27+ messages in thread
From: Tobias Holst @ 2015-11-03 18:59 UTC (permalink / raw)
To: Chris Mason, Tobias Holst, Austin S Hemmelgarn, Omar Sandoval,
linux-btrfs@vger.kernel.org
Ah, thanks for the information!
Happy testing :)
2015-11-03 19:34 GMT+01:00 Chris Mason <clm@fb.com>:
> On Tue, Nov 03, 2015 at 07:13:37PM +0100, Tobias Holst wrote:
>> Hi
>>
>> Anything new on this topic?
>>
>> I think it would be a great thing and should be merged as soon as it
>> is stable. :)
>
> I've been testing it, but my plan is 4.5.
>
> -chris
^ permalink raw reply [flat|nested] 27+ messages in thread