[PATCH 0/6] Cleanup super block stripe exclusion code

[PATCH 0/6] Cleanup super block stripe exclusion code

[Nikolay Borisov]

This series aims to cleanup the code necessary to exclude io stripes within a
chunk that can contain a superblock. To achieve this following actions are taken
(in order of appearance) :

1. Make btrfs_rmap_block private to block-group.c since it's only used by
exclude_super_stripes.

2. Extend btrfs selftest framework to accommodate testing of btrfs_rmap_block's
functionality

3. Add tests for btrfs_rmap_block

4. With tests in place perform surgery on btrfs_rmap_block to make it more readable,
this is achieved by renamring variables, making code more linear, getting rid
of a BUG_ON.

5. After btrfs_rmap_block is sane it's easier to reason about some of its
invariants, allowing me to simplify exclude_super_stripes.

This series survived full xfstest with no visible regressions.

Nikolay Borisov (6):
  btrfs: Move and unexport btrfs_rmap_block
  btrfs: selftests: Add support for dummy devices
  btrfs: Add self-tests for btrfs_rmap_block
  btrfs: Refactor btrfs_rmap_block to improve readability
  btrfs: Read stripe len directly in btrfs_rmap_block
  btrfs: Remove dead code exclude_super_stripes

 fs/btrfs/block-group.c            | 107 +++++++++++++++++++++----
 fs/btrfs/tests/btrfs-tests.c      |  28 +++++++
 fs/btrfs/tests/btrfs-tests.h      |   1 +
 fs/btrfs/tests/extent-map-tests.c | 128 +++++++++++++++++++++++++++++-
 fs/btrfs/volumes.c                |  69 ----------------
 fs/btrfs/volumes.h                |   2 -
 6 files changed, 246 insertions(+), 89 deletions(-)

--
2.17.1

[PATCH 1/6] btrfs: Move and unexport btrfs_rmap_block

[Nikolay Borisov]

It's used only during initial block group reading to map physical
address of super block to a list of logical ones. Make it private to
block-group.c and while at it add proper kernel doc.

Signed-off-by: Nikolay Borisov <nborisov@suse.com>
---
 fs/btrfs/block-group.c | 82 ++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/volumes.c     | 69 -----------------------------------
 fs/btrfs/volumes.h     |  2 --
 3 files changed, 82 insertions(+), 71 deletions(-)

diff --git a/fs/btrfs/block-group.c b/fs/btrfs/block-group.c
index d96561d1ce90..902c246a9d38 100644
--- a/fs/btrfs/block-group.c
+++ b/fs/btrfs/block-group.c
@@ -14,6 +14,7 @@
 #include "sysfs.h"
 #include "tree-log.h"
 #include "delalloc-space.h"
+#include "raid56.h"
 
 /*
  * Return target flags in extended format or 0 if restripe for this chunk_type
@@ -1516,6 +1517,87 @@ static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
 	write_sequnlock(&fs_info->profiles_lock);
 }
 
+/*
+ * btrfs_rmap_block - Maps a particular @physical disk address to a list of @logical
+ * addresses. Used primarily to exclude those portions of a block group that
+ * contain super block copies.
+ *
+ * chunk_start - Logical address of block group
+ * physical - Physical address to map to logical addresses
+ * logical - Return array of logical addresses which map to @physical
+ * naddrs - Length of @logical
+ * stripe_len - size of IO stripe for the given block group
+ */
+EXPORT_FOR_TESTS
+int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
+		     u64 physical, u64 **logical, int *naddrs, int *stripe_len)
+{
+	struct extent_map *em;
+	struct map_lookup *map;
+	u64 *buf;
+	u64 bytenr;
+	u64 length;
+	u64 stripe_nr;
+	u64 rmap_len;
+	int i, j, nr = 0;
+
+	em = btrfs_get_chunk_map(fs_info, chunk_start, 1);
+	if (IS_ERR(em))
+		return -EIO;
+
+	map = em->map_lookup;
+	length = em->len;
+	rmap_len = map->stripe_len;
+
+	if (map->type & BTRFS_BLOCK_GROUP_RAID10)
+		length = div_u64(length, map->num_stripes / map->sub_stripes);
+	else if (map->type & BTRFS_BLOCK_GROUP_RAID0)
+		length = div_u64(length, map->num_stripes);
+	else if (map->type & BTRFS_BLOCK_GROUP_RAID56_MASK) {
+		length = div_u64(length, nr_data_stripes(map));
+		rmap_len = map->stripe_len * nr_data_stripes(map);
+	}
+
+	buf = kcalloc(map->num_stripes, sizeof(u64), GFP_NOFS);
+	BUG_ON(!buf); /* -ENOMEM */
+
+	for (i = 0; i < map->num_stripes; i++) {
+		if (map->stripes[i].physical > physical ||
+		    map->stripes[i].physical + length <= physical)
+			continue;
+
+		stripe_nr = physical - map->stripes[i].physical;
+		stripe_nr = div64_u64(stripe_nr, map->stripe_len);
+
+		if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
+			stripe_nr = stripe_nr * map->num_stripes + i;
+			stripe_nr = div_u64(stripe_nr, map->sub_stripes);
+		} else if (map->type & BTRFS_BLOCK_GROUP_RAID0) {
+			stripe_nr = stripe_nr * map->num_stripes + i;
+		} /* else if RAID[56], multiply by nr_data_stripes().
+		   * Alternatively, just use rmap_len below instead of
+		   * map->stripe_len */
+
+		bytenr = chunk_start + stripe_nr * rmap_len;
+		WARN_ON(nr >= map->num_stripes);
+		for (j = 0; j < nr; j++) {
+			if (buf[j] == bytenr)
+				break;
+		}
+		if (j == nr) {
+			WARN_ON(nr >= map->num_stripes);
+			buf[nr++] = bytenr;
+		}
+	}
+
+	*logical = buf;
+	*naddrs = nr;
+	*stripe_len = rmap_len;
+
+	free_extent_map(em);
+	return 0;
+}
+
 static int exclude_super_stripes(struct btrfs_block_group *cache)
 {
 	struct btrfs_fs_info *fs_info = cache->fs_info;
diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c
index d8e5560db285..a1a7b543e465 100644
--- a/fs/btrfs/volumes.c
+++ b/fs/btrfs/volumes.c
@@ -6107,75 +6107,6 @@ int btrfs_map_sblock(struct btrfs_fs_info *fs_info, enum btrfs_map_op op,
 	return __btrfs_map_block(fs_info, op, logical, length, bbio_ret, 0, 1);
 }
 
-int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
-		     u64 physical, u64 **logical, int *naddrs, int *stripe_len)
-{
-	struct extent_map *em;
-	struct map_lookup *map;
-	u64 *buf;
-	u64 bytenr;
-	u64 length;
-	u64 stripe_nr;
-	u64 rmap_len;
-	int i, j, nr = 0;
-
-	em = btrfs_get_chunk_map(fs_info, chunk_start, 1);
-	if (IS_ERR(em))
-		return -EIO;
-
-	map = em->map_lookup;
-	length = em->len;
-	rmap_len = map->stripe_len;
-
-	if (map->type & BTRFS_BLOCK_GROUP_RAID10)
-		length = div_u64(length, map->num_stripes / map->sub_stripes);
-	else if (map->type & BTRFS_BLOCK_GROUP_RAID0)
-		length = div_u64(length, map->num_stripes);
-	else if (map->type & BTRFS_BLOCK_GROUP_RAID56_MASK) {
-		length = div_u64(length, nr_data_stripes(map));
-		rmap_len = map->stripe_len * nr_data_stripes(map);
-	}
-
-	buf = kcalloc(map->num_stripes, sizeof(u64), GFP_NOFS);
-	BUG_ON(!buf); /* -ENOMEM */
-
-	for (i = 0; i < map->num_stripes; i++) {
-		if (map->stripes[i].physical > physical ||
-		    map->stripes[i].physical + length <= physical)
-			continue;
-
-		stripe_nr = physical - map->stripes[i].physical;
-		stripe_nr = div64_u64(stripe_nr, map->stripe_len);
-
-		if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
-			stripe_nr = stripe_nr * map->num_stripes + i;
-			stripe_nr = div_u64(stripe_nr, map->sub_stripes);
-		} else if (map->type & BTRFS_BLOCK_GROUP_RAID0) {
-			stripe_nr = stripe_nr * map->num_stripes + i;
-		} /* else if RAID[56], multiply by nr_data_stripes().
-		   * Alternatively, just use rmap_len below instead of
-		   * map->stripe_len */
-
-		bytenr = chunk_start + stripe_nr * rmap_len;
-		WARN_ON(nr >= map->num_stripes);
-		for (j = 0; j < nr; j++) {
-			if (buf[j] == bytenr)
-				break;
-		}
-		if (j == nr) {
-			WARN_ON(nr >= map->num_stripes);
-			buf[nr++] = bytenr;
-		}
-	}
-
-	*logical = buf;
-	*naddrs = nr;
-	*stripe_len = rmap_len;
-
-	free_extent_map(em);
-	return 0;
-}
-
 static inline void btrfs_end_bbio(struct btrfs_bio *bbio, struct bio *bio)
 {
 	bio->bi_private = bbio->private;
diff --git a/fs/btrfs/volumes.h b/fs/btrfs/volumes.h
index fc1b564b9cfe..12a7e0dd26bd 100644
--- a/fs/btrfs/volumes.h
+++ b/fs/btrfs/volumes.h
@@ -417,8 +417,6 @@ int btrfs_map_sblock(struct btrfs_fs_info *fs_info, enum btrfs_map_op op,
 		     struct btrfs_bio **bbio_ret);
 int btrfs_get_io_geometry(struct btrfs_fs_info *fs_info, enum btrfs_map_op op,
 		u64 logical, u64 len, struct btrfs_io_geometry *io_geom);
-int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
-		     u64 physical, u64 **logical, int *naddrs, int *stripe_len);
 int btrfs_read_sys_array(struct btrfs_fs_info *fs_info);
 int btrfs_read_chunk_tree(struct btrfs_fs_info *fs_info);
 int btrfs_alloc_chunk(struct btrfs_trans_handle *trans, u64 type);
-- 
2.17.1

[PATCH 2/6] btrfs: selftests: Add support for dummy devices

[Nikolay Borisov]

Add basic infrastructure to create and link dummy btrfs_devices. This
will be used in the pending btrfs_rmap_block test which deals with
the  block groups.

Calling btrfs_alloc_dummy_device will link the newly created device to
the passed fs_info and the test framework will free dem once the test
is finished.

Signed-off-by: Nikolay Borisov <nborisov@suse.com>
---
 fs/btrfs/tests/btrfs-tests.c | 28 ++++++++++++++++++++++++++++
 fs/btrfs/tests/btrfs-tests.h |  1 +
 2 files changed, 29 insertions(+)

diff --git a/fs/btrfs/tests/btrfs-tests.c b/fs/btrfs/tests/btrfs-tests.c
index a7aca4141788..1710f2533d04 100644
--- a/fs/btrfs/tests/btrfs-tests.c
+++ b/fs/btrfs/tests/btrfs-tests.c
@@ -86,6 +86,28 @@ static void btrfs_destroy_test_fs(void)
 	unregister_filesystem(&test_type);
 }
 
+struct btrfs_device *btrfs_alloc_dummy_device(struct btrfs_fs_info *fs_info)
+{
+	struct btrfs_device *dev;
+
+	dev = kzalloc(sizeof(*dev),GFP_KERNEL);
+	if (!dev)
+		return ERR_PTR(-ENOMEM);
+
+	extent_io_tree_init(NULL, &dev->alloc_state, 0, NULL);
+	INIT_LIST_HEAD(&dev->dev_list);
+
+	list_add(&dev->dev_list, &fs_info->fs_devices->devices);
+
+	return dev;
+}
+
+static void btrfs_free_dummy_device(struct btrfs_device *dev)
+{
+	extent_io_tree_release(&dev->alloc_state);
+	kfree(dev);
+}
+
 struct btrfs_fs_info *btrfs_alloc_dummy_fs_info(u32 nodesize, u32 sectorsize)
 {
 	struct btrfs_fs_info *fs_info = kzalloc(sizeof(struct btrfs_fs_info),
@@ -132,12 +154,14 @@ struct btrfs_fs_info *btrfs_alloc_dummy_fs_info(u32 nodesize, u32 sectorsize)
 	INIT_LIST_HEAD(&fs_info->dirty_qgroups);
 	INIT_LIST_HEAD(&fs_info->dead_roots);
 	INIT_LIST_HEAD(&fs_info->tree_mod_seq_list);
+	INIT_LIST_HEAD(&fs_info->fs_devices->devices);
 	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, &fs_info->freed_extents[0],
 			    IO_TREE_FS_INFO_FREED_EXTENTS0, NULL);
 	extent_io_tree_init(fs_info, &fs_info->freed_extents[1],
 			    IO_TREE_FS_INFO_FREED_EXTENTS1, NULL);
+	extent_map_tree_init(&fs_info->mapping_tree);
 	fs_info->pinned_extents = &fs_info->freed_extents[0];
 	set_bit(BTRFS_FS_STATE_DUMMY_FS_INFO, &fs_info->fs_state);
 
@@ -150,6 +174,7 @@ void btrfs_free_dummy_fs_info(struct btrfs_fs_info *fs_info)
 {
 	struct radix_tree_iter iter;
 	void **slot;
+	struct btrfs_device *dev, *temp;
 
 	if (!fs_info)
 		return;
@@ -180,6 +205,9 @@ void btrfs_free_dummy_fs_info(struct btrfs_fs_info *fs_info)
 	}
 	spin_unlock(&fs_info->buffer_lock);
 
+	btrfs_mapping_tree_free(&fs_info->mapping_tree);
+	list_for_each_entry_safe(dev, temp, &fs_info->fs_devices->devices, dev_list)
+		btrfs_free_dummy_device(dev);
 	btrfs_free_qgroup_config(fs_info);
 	btrfs_free_fs_roots(fs_info);
 	cleanup_srcu_struct(&fs_info->subvol_srcu);
diff --git a/fs/btrfs/tests/btrfs-tests.h b/fs/btrfs/tests/btrfs-tests.h
index 9e52527357d8..7a2d7ffbe30e 100644
--- a/fs/btrfs/tests/btrfs-tests.h
+++ b/fs/btrfs/tests/btrfs-tests.h
@@ -46,6 +46,7 @@ btrfs_alloc_dummy_block_group(struct btrfs_fs_info *fs_info, unsigned long lengt
 void btrfs_free_dummy_block_group(struct btrfs_block_group *cache);
 void btrfs_init_dummy_trans(struct btrfs_trans_handle *trans,
 			    struct btrfs_fs_info *fs_info);
+struct btrfs_device *btrfs_alloc_dummy_device(struct btrfs_fs_info *fs_info);
 #else
 static inline int btrfs_run_sanity_tests(void)
 {
-- 
2.17.1

[PATCH 3/6] btrfs: Add self-tests for btrfs_rmap_block

[Nikolay Borisov]

This is enough to exercise out of boundary address exclusion as well as
address matching.

Signed-off-by: Nikolay Borisov <nborisov@suse.com>
---
 fs/btrfs/tests/extent-map-tests.c | 128 +++++++++++++++++++++++++++++-
 1 file changed, 127 insertions(+), 1 deletion(-)

diff --git a/fs/btrfs/tests/extent-map-tests.c b/fs/btrfs/tests/extent-map-tests.c
index 4a7f796c9900..e6a6417e87d2 100644
--- a/fs/btrfs/tests/extent-map-tests.c
+++ b/fs/btrfs/tests/extent-map-tests.c
@@ -6,6 +6,12 @@
 #include <linux/types.h>
 #include "btrfs-tests.h"
 #include "../ctree.h"
+#include "../volumes.h"
+#include "../disk-io.h"
+
+extern int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
+                            u64 physical, u64 **logical, int *naddrs,
+                            int *stripe_len);
 
 static void free_extent_map_tree(struct extent_map_tree *em_tree)
 {
@@ -437,11 +443,125 @@ static int test_case_4(struct btrfs_fs_info *fs_info,
 	return ret;
 }
 
+struct rmap_test_vector {
+	u64 raid_type;
+	u64 physical_start;
+	u64 data_stripe_size;
+	u64 num_data_stripes;
+	u64 num_stripes;
+	u64 data_stripe_phys_start[5]; /* Hacky, but convenient */
+	int expected_mapped_addr; /* number of expected mapped addresses */
+	u64 mapped_logical[5]; /* mapped addresses */
+};
+
+static int test_rmap_block(struct btrfs_fs_info *fs_info,
+			   struct rmap_test_vector *test)
+{
+	struct extent_map *em;
+	struct map_lookup *map = NULL;
+	u64 *logical;
+	int i, out_ndaddrs, out_stripe_len;
+	int ret = -EINVAL;
+
+	em = alloc_extent_map();
+	if (!em) {
+		test_std_err(TEST_ALLOC_EXTENT_MAP);
+		return -ENOMEM;
+	}
+
+	map = kmalloc(map_lookup_size(test->num_stripes), GFP_KERNEL);
+	if (!map) {
+		kfree(em);
+		test_std_err(TEST_ALLOC_EXTENT_MAP);
+		return -ENOMEM;
+	}
+
+	set_bit(EXTENT_FLAG_FS_MAPPING, &em->flags);
+	em->start = SZ_4G; /* Start at 4gb logical address */
+	em->len = test->data_stripe_size * test->num_data_stripes;
+	em->block_len = em->len;
+	em->orig_block_len = test->data_stripe_size;
+	em->map_lookup = map;
+
+	map->num_stripes = test->num_stripes;
+	map->stripe_len = BTRFS_STRIPE_LEN;
+	map->type = test->raid_type;
+
+	for (i = 0; i < map->num_stripes; i++)
+	{
+		struct btrfs_device *dev = btrfs_alloc_dummy_device(fs_info);
+		if (!dev)
+			BUG();
+		map->stripes[i].dev = dev;
+		map->stripes[i].physical = test->data_stripe_phys_start[i];
+	}
+
+	write_lock(&fs_info->mapping_tree.lock);
+	ret = add_extent_mapping(&fs_info->mapping_tree, em, 0);
+	write_unlock(&fs_info->mapping_tree.lock);
+	if (ret) {
+		test_err("Error adding block group mapping to mapping tree");
+	}
+
+	ret = btrfs_rmap_block(fs_info, em->start, btrfs_sb_offset(1),
+			       &logical, &out_ndaddrs, &out_stripe_len);
+	if (ret || (out_ndaddrs == 0 && test->expected_mapped_addr)) {
+		test_err("Didn't rmap anything");
+		goto out;
+	}
+
+	if (out_stripe_len != BTRFS_STRIPE_LEN) {
+		test_err("Calculated stripe len doesn't match");
+		goto out;
+	}
+
+	if (out_ndaddrs != test->expected_mapped_addr) {
+		for (i = 0; i < out_ndaddrs; i++)
+			test_msg("Mapped %llu", logical[i]);
+		test_err("Unexpected number of mapped addresses: %d\n", out_ndaddrs);
+		goto out;
+	}
+
+	for (i = 0; i < out_ndaddrs; i++) {
+		if (logical[i] != test->mapped_logical[i]) {
+			test_err("Unexpected logical address mapped");
+			goto out;
+		}
+	}
+
+	ret = 0;
+out:
+	write_lock(&fs_info->mapping_tree.lock);
+	remove_extent_mapping(&fs_info->mapping_tree, em);
+	write_unlock(&fs_info->mapping_tree.lock);
+	/* For us */
+	free_extent_map(em);
+	/* For the tree */
+	free_extent_map(em);
+	return ret;
+}
+
 int btrfs_test_extent_map(void)
 {
 	struct btrfs_fs_info *fs_info = NULL;
 	struct extent_map_tree *em_tree;
-	int ret = 0;
+	int ret = 0, i;
+	struct rmap_test_vector rmap_tests[] = {
+		{
+			/* Tests a chunk with 2 data stripes one of which
+			 * interesects the physical address of the super block
+			 * is correctly recognised.
+			 */
+			BTRFS_BLOCK_GROUP_RAID1, SZ_64M - SZ_4M, SZ_256M, 2, 2,
+			{SZ_64M - SZ_4M, SZ_64M - SZ_4M + SZ_256M}, 1,
+			{SZ_4G + SZ_4M}
+		},
+		{
+			/* test that out of range physical addresses are ignored */
+			0 /* SINGLE chunk type */, SZ_4G, SZ_256M, 1, 1,
+			{SZ_256M}, 0, {0}
+		}
+	};
 
 	test_msg("running extent_map tests");
 
@@ -474,6 +594,12 @@ int btrfs_test_extent_map(void)
 		goto out;
 	ret = test_case_4(fs_info, em_tree);
 
+	for (i = 0; i < ARRAY_SIZE(rmap_tests); i++) {
+		ret = test_rmap_block(fs_info, &rmap_tests[i]);
+		if (ret)
+			goto out;
+	}
+
 out:
 	kfree(em_tree);
 	btrfs_free_dummy_fs_info(fs_info);
-- 
2.17.1

[PATCH 4/6] btrfs: Refactor btrfs_rmap_block to improve readability

[Nikolay Borisov]

Move variables to appropriate scope. Remove last BUG_ON in the function
and rework error handling accordingly. Make the duplicate detection code
more straightforward. Use in_range macro. And give variables more
descriptive name by explicitly distinguishing between IO stripe size
(size recorded in the chunk item) and data stripe size (the size of
an actual stripe, constituting a logical chunk/block group).

Signed-off-by: Nikolay Borisov <nborisov@suse.com>
---
 fs/btrfs/block-group.c | 53 ++++++++++++++++++++++++------------------
 1 file changed, 31 insertions(+), 22 deletions(-)

diff --git a/fs/btrfs/block-group.c b/fs/btrfs/block-group.c
index 902c246a9d38..c3b1f304bc70 100644
--- a/fs/btrfs/block-group.c
+++ b/fs/btrfs/block-group.c
@@ -1536,34 +1536,41 @@ int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
 	struct map_lookup *map;
 	u64 *buf;
 	u64 bytenr;
-	u64 length;
-	u64 stripe_nr;
-	u64 rmap_len;
-	int i, j, nr = 0;
+	u64 data_stripe_length;
+	u64 io_stripe_size;
+	int i, nr = 0;
+	int ret = 0;
 
 	em = btrfs_get_chunk_map(fs_info, chunk_start, 1);
 	if (IS_ERR(em))
 		return -EIO;
 
 	map = em->map_lookup;
-	length = em->len;
-	rmap_len = map->stripe_len;
+	data_stripe_length = em->len;
+	io_stripe_size = map->stripe_len;
 
 	if (map->type & BTRFS_BLOCK_GROUP_RAID10)
-		length = div_u64(length, map->num_stripes / map->sub_stripes);
+		data_stripe_length = div_u64(data_stripe_length, map->num_stripes / map->sub_stripes);
 	else if (map->type & BTRFS_BLOCK_GROUP_RAID0)
-		length = div_u64(length, map->num_stripes);
+		data_stripe_length = div_u64(data_stripe_length, map->num_stripes);
 	else if (map->type & BTRFS_BLOCK_GROUP_RAID56_MASK) {
-		length = div_u64(length, nr_data_stripes(map));
-		rmap_len = map->stripe_len * nr_data_stripes(map);
+		data_stripe_length = div_u64(data_stripe_length, nr_data_stripes(map));
+		io_stripe_size = map->stripe_len * nr_data_stripes(map);
 	}
 
 	buf = kcalloc(map->num_stripes, sizeof(u64), GFP_NOFS);
-	BUG_ON(!buf); /* -ENOMEM */
+	if (!buf) {
+		ret = -ENOMEM;
+		goto out;
+	}
 
 	for (i = 0; i < map->num_stripes; i++) {
-		if (map->stripes[i].physical > physical ||
-		    map->stripes[i].physical + length <= physical)
+		bool already_inserted = false;
+		u64 stripe_nr;
+		int j;
+
+		if (!in_range(physical, map->stripes[i].physical,
+			      data_stripe_length))
 			continue;
 
 		stripe_nr = physical - map->stripes[i].physical;
@@ -1575,25 +1582,27 @@ int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
 		} else if (map->type & BTRFS_BLOCK_GROUP_RAID0) {
 			stripe_nr = stripe_nr * map->num_stripes + i;
 		} /* else if RAID[56], multiply by nr_data_stripes().
-		   * Alternatively, just use rmap_len below instead of
+		   * Alternatively, just use io_stripe_size below instead of
 		   * map->stripe_len */
 
-		bytenr = chunk_start + stripe_nr * rmap_len;
-		WARN_ON(nr >= map->num_stripes);
+		bytenr = chunk_start + stripe_nr * io_stripe_size;
+
+		/* Ensure we don't add duplicate addresses */
 		for (j = 0; j < nr; j++) {
-			if (buf[j] == bytenr)
+			if (buf[j] == bytenr) {
+				already_inserted = true;
 				break;
+			}
 		}
-		if (j == nr) {
-			WARN_ON(nr >= map->num_stripes);
+
+		if (!already_inserted)
 			buf[nr++] = bytenr;
-		}
 	}
 
 	*logical = buf;
 	*naddrs = nr;
-	*stripe_len = rmap_len;
-
+	*stripe_len = io_stripe_size;
+out:
 	free_extent_map(em);
 	return 0;
 }
-- 
2.17.1

[PATCH 5/6] btrfs: Read stripe len directly in btrfs_rmap_block

[Nikolay Borisov]

extent_map::orig_block_len contains the size of a physical stripe when
it's used to describe block groups. So get the size directly in
btrfs_rmap_block rather than open-coding the calculations. No
functional changes.

Signed-off-by: Nikolay Borisov <nborisov@suse.com>
---
 fs/btrfs/block-group.c | 11 +++--------
 1 file changed, 3 insertions(+), 8 deletions(-)

diff --git a/fs/btrfs/block-group.c b/fs/btrfs/block-group.c
index c3b1f304bc70..2ab4d9cb598a 100644
--- a/fs/btrfs/block-group.c
+++ b/fs/btrfs/block-group.c
@@ -1546,17 +1546,12 @@ int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
 		return -EIO;
 
 	map = em->map_lookup;
-	data_stripe_length = em->len;
+	data_stripe_length = em->orig_block_len;
 	io_stripe_size = map->stripe_len;
 
-	if (map->type & BTRFS_BLOCK_GROUP_RAID10)
-		data_stripe_length = div_u64(data_stripe_length, map->num_stripes / map->sub_stripes);
-	else if (map->type & BTRFS_BLOCK_GROUP_RAID0)
-		data_stripe_length = div_u64(data_stripe_length, map->num_stripes);
-	else if (map->type & BTRFS_BLOCK_GROUP_RAID56_MASK) {
-		data_stripe_length = div_u64(data_stripe_length, nr_data_stripes(map));
+	/* For raid5/6 adjust to a full IO stripe length */
+	if (map->type & BTRFS_BLOCK_GROUP_RAID56_MASK)
 		io_stripe_size = map->stripe_len * nr_data_stripes(map);
-	}
 
 	buf = kcalloc(map->num_stripes, sizeof(u64), GFP_NOFS);
 	if (!buf) {
-- 
2.17.1

[PATCH 6/6] btrfs: Remove dead code exclude_super_stripes

[Nikolay Borisov]

Adresses held in 'logical' array are always guaranteed to fall within
the boundaries of the block group. That is, 'start' can never be
smaller than cache->start. This invariant follows from the way the
address are calculated in btrfs_rmap_block:

    stripe_nr = physical - map->stripes[i].physical;
    stripe_nr = div64_u64(stripe_nr, map->stripe_len);
    bytenr = chunk_start + stripe_nr * io_stripe_size;

I.e it's always some IO stripe within the given chunk.

Exploit this invariant to simplify the body of the loop by removing the
unnecessary 'if' since its 'else' part is the one always executed.

Signed-off-by: Nikolay Borisov <nborisov@suse.com>
---
 fs/btrfs/block-group.c | 21 ++++-----------------
 1 file changed, 4 insertions(+), 17 deletions(-)

diff --git a/fs/btrfs/block-group.c b/fs/btrfs/block-group.c
index 2ab4d9cb598a..3c7c34b6a0a8 100644
--- a/fs/btrfs/block-group.c
+++ b/fs/btrfs/block-group.c
@@ -1627,25 +1627,12 @@ static int exclude_super_stripes(struct btrfs_block_group *cache)
 			return ret;
 
 		while (nr--) {
-			u64 start, len;
-
-			if (logical[nr] > cache->start + cache->length)
-				continue;
-
-			if (logical[nr] + stripe_len <= cache->start)
-				continue;
-
-			start = logical[nr];
-			if (start < cache->start) {
-				start = cache->start;
-				len = (logical[nr] + stripe_len) - start;
-			} else {
-				len = min_t(u64, stripe_len,
-					    cache->start + cache->length - start);
-			}
+			u64 len = min_t(u64, stripe_len,
+				cache->start + cache->length - logical[nr]);
 
 			cache->bytes_super += len;
-			ret = btrfs_add_excluded_extent(fs_info, start, len);
+			ret = btrfs_add_excluded_extent(fs_info, logical[nr],
+							len);
 			if (ret) {
 				kfree(logical);
 				return ret;
-- 
2.17.1

Re: [PATCH 1/6] btrfs: Move and unexport btrfs_rmap_block

[David Sterba]

On Tue, Nov 19, 2019 at 02:05:50PM +0200, Nikolay Borisov wrote:
> --- a/fs/btrfs/volumes.h
> +++ b/fs/btrfs/volumes.h
> @@ -417,8 +417,6 @@ int btrfs_map_sblock(struct btrfs_fs_info *fs_info, enum btrfs_map_op op,
>  		     struct btrfs_bio **bbio_ret);
>  int btrfs_get_io_geometry(struct btrfs_fs_info *fs_info, enum btrfs_map_op op,
>  		u64 logical, u64 len, struct btrfs_io_geometry *io_geom);
> -int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
> -		     u64 physical, u64 **logical, int *naddrs, int *stripe_len);

Other functions that are exported for tests have the declaration in .h
under #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS, so this should follow the
pattern and not declare the function inside the tests.

Re: [PATCH 3/6] btrfs: Add self-tests for btrfs_rmap_block

[David Sterba]

On Tue, Nov 19, 2019 at 02:05:52PM +0200, Nikolay Borisov wrote:
> This is enough to exercise out of boundary address exclusion as well as
> address matching.
> 
> Signed-off-by: Nikolay Borisov <nborisov@suse.com>
> ---
>  fs/btrfs/tests/extent-map-tests.c | 128 +++++++++++++++++++++++++++++-
>  1 file changed, 127 insertions(+), 1 deletion(-)
> 
> diff --git a/fs/btrfs/tests/extent-map-tests.c b/fs/btrfs/tests/extent-map-tests.c
> index 4a7f796c9900..e6a6417e87d2 100644
> --- a/fs/btrfs/tests/extent-map-tests.c
> +++ b/fs/btrfs/tests/extent-map-tests.c
> @@ -6,6 +6,12 @@
>  #include <linux/types.h>
>  #include "btrfs-tests.h"
>  #include "../ctree.h"
> +#include "../volumes.h"
> +#include "../disk-io.h"
> +
> +extern int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
> +                            u64 physical, u64 **logical, int *naddrs,
> +                            int *stripe_len);
>  
>  static void free_extent_map_tree(struct extent_map_tree *em_tree)
>  {
> @@ -437,11 +443,125 @@ static int test_case_4(struct btrfs_fs_info *fs_info,
>  	return ret;
>  }
>  
> +struct rmap_test_vector {
> +	u64 raid_type;
> +	u64 physical_start;
> +	u64 data_stripe_size;
> +	u64 num_data_stripes;
> +	u64 num_stripes;
> +	u64 data_stripe_phys_start[5]; /* Hacky, but convenient */

Please put the comment on own line and explain what is hacky here.

> +	int expected_mapped_addr; /* number of expected mapped addresses */
> +	u64 mapped_logical[5]; /* mapped addresses */

The comments do not say more than the names, they should be dropped or
expanded.

> +};
> +
> +static int test_rmap_block(struct btrfs_fs_info *fs_info,
> +			   struct rmap_test_vector *test)
> +{
> +	struct extent_map *em;
> +	struct map_lookup *map = NULL;
> +	u64 *logical;
> +	int i, out_ndaddrs, out_stripe_len;
> +	int ret = -EINVAL;
> +
> +	em = alloc_extent_map();
> +	if (!em) {
> +		test_std_err(TEST_ALLOC_EXTENT_MAP);
> +		return -ENOMEM;
> +	}
> +
> +	map = kmalloc(map_lookup_size(test->num_stripes), GFP_KERNEL);
> +	if (!map) {
> +		kfree(em);
> +		test_std_err(TEST_ALLOC_EXTENT_MAP);
> +		return -ENOMEM;
> +	}
> +
> +	set_bit(EXTENT_FLAG_FS_MAPPING, &em->flags);
> +	em->start = SZ_4G; /* Start at 4gb logical address */

Please avoid the in-line comments.

> +	em->len = test->data_stripe_size * test->num_data_stripes;
> +	em->block_len = em->len;
> +	em->orig_block_len = test->data_stripe_size;
> +	em->map_lookup = map;
> +
> +	map->num_stripes = test->num_stripes;
> +	map->stripe_len = BTRFS_STRIPE_LEN;
> +	map->type = test->raid_type;
> +
> +	for (i = 0; i < map->num_stripes; i++)
> +	{
> +		struct btrfs_device *dev = btrfs_alloc_dummy_device(fs_info);
> +		if (!dev)
> +			BUG();

No way to handle the error?

> +		map->stripes[i].dev = dev;
> +		map->stripes[i].physical = test->data_stripe_phys_start[i];
> +	}
> +
> +	write_lock(&fs_info->mapping_tree.lock);
> +	ret = add_extent_mapping(&fs_info->mapping_tree, em, 0);
> +	write_unlock(&fs_info->mapping_tree.lock);
> +	if (ret) {
> +		test_err("Error adding block group mapping to mapping tree");
> +	}

No need for { }, no capital letter at the beginnin of the string.

> +
> +	ret = btrfs_rmap_block(fs_info, em->start, btrfs_sb_offset(1),
> +			       &logical, &out_ndaddrs, &out_stripe_len);
> +	if (ret || (out_ndaddrs == 0 && test->expected_mapped_addr)) {
> +		test_err("Didn't rmap anything");

That's a good example of a useless error message

> +		goto out;
> +	}
> +
> +	if (out_stripe_len != BTRFS_STRIPE_LEN) {
> +		test_err("Calculated stripe len doesn't match");
> +		goto out;
> +	}
> +
> +	if (out_ndaddrs != test->expected_mapped_addr) {
> +		for (i = 0; i < out_ndaddrs; i++)
> +			test_msg("Mapped %llu", logical[i]);
> +		test_err("Unexpected number of mapped addresses: %d\n", out_ndaddrs);

No "\n"

> +		goto out;
> +	}
> +
> +	for (i = 0; i < out_ndaddrs; i++) {
> +		if (logical[i] != test->mapped_logical[i]) {
> +			test_err("Unexpected logical address mapped");
> +			goto out;
> +		}
> +	}
> +
> +	ret = 0;
> +out:
> +	write_lock(&fs_info->mapping_tree.lock);
> +	remove_extent_mapping(&fs_info->mapping_tree, em);
> +	write_unlock(&fs_info->mapping_tree.lock);
> +	/* For us */
> +	free_extent_map(em);
> +	/* For the tree */
> +	free_extent_map(em);
> +	return ret;
> +}
> +
>  int btrfs_test_extent_map(void)
>  {
>  	struct btrfs_fs_info *fs_info = NULL;
>  	struct extent_map_tree *em_tree;
> -	int ret = 0;
> +	int ret = 0, i;
> +	struct rmap_test_vector rmap_tests[] = {
> +		{
> +			/* Tests a chunk with 2 data stripes one of which
> +			 * interesects the physical address of the super block
> +			 * is correctly recognised.
> +			 */

Comment style from net/

> +			BTRFS_BLOCK_GROUP_RAID1, SZ_64M - SZ_4M, SZ_256M, 2, 2,
> +			{SZ_64M - SZ_4M, SZ_64M - SZ_4M + SZ_256M}, 1,
> +			{SZ_4G + SZ_4M}
> +		},
> +		{
> +			/* test that out of range physical addresses are ignored */
> +			0 /* SINGLE chunk type */, SZ_4G, SZ_256M, 1, 1,
> +			{SZ_256M}, 0, {0}
> +		}

Looking at the number of values it's hard to say what's being
initialized, please convert it to the designated initializers.

> +	};
>  
>  	test_msg("running extent_map tests");
>  
> @@ -474,6 +594,12 @@ int btrfs_test_extent_map(void)
>  		goto out;
>  	ret = test_case_4(fs_info, em_tree);

Maybe put a test_msg("running rmap tests") here so it's clear that any
following error message belongs to rmap anot not just extent_map tests.

>  
> +	for (i = 0; i < ARRAY_SIZE(rmap_tests); i++) {
> +		ret = test_rmap_block(fs_info, &rmap_tests[i]);
> +		if (ret)
> +			goto out;
> +	}
> +
>  out:
>  	kfree(em_tree);
>  	btrfs_free_dummy_fs_info(fs_info);

[PATCH v2] btrfs: Move and unexport btrfs_rmap_block

[Nikolay Borisov]

It's used only during initial block group reading to map physical
address of super block to a list of logical ones. Make it private to
block-group.c, add proper kernel doc and ensure it's exported only for
tests.

Signed-off-by: Nikolay Borisov <nborisov@suse.com>
---

V2:
 * Export btrfs_rmap_block only if CONFIG_BTRFS_FS_RUN_SANITY_TESTS is set.
 fs/btrfs/block-group.c | 82 ++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/block-group.h |  5 +++
 fs/btrfs/volumes.c     | 69 -----------------------------------
 fs/btrfs/volumes.h     |  2 --
 4 files changed, 87 insertions(+), 71 deletions(-)

diff --git a/fs/btrfs/block-group.c b/fs/btrfs/block-group.c
index 66fa39632cde..41217be64bf5 100644
--- a/fs/btrfs/block-group.c
+++ b/fs/btrfs/block-group.c
@@ -14,6 +14,7 @@
 #include "sysfs.h"
 #include "tree-log.h"
 #include "delalloc-space.h"
+#include "raid56.h"

 /*
  * Return target flags in extended format or 0 if restripe for this chunk_type
@@ -1502,6 +1503,87 @@ static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
 	write_sequnlock(&fs_info->profiles_lock);
 }

+/*
+ * btrfs_rmap_block - Maps a particular @physical disk address to a list of @logical
+ * addresses. Used primarily to exclude those portions of a block group that
+ * contain super block copies.
+ *
+ * chunk_start - Logical address of block group
+ * physical - Physical address to map to logical addresses
+ * logical - Return array of logical addresses which map to @physical
+ * naddrs - Length of @logical
+ * stripe_len - size of IO stripe for the given block group
+ */
+EXPORT_FOR_TESTS
+int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
+		     u64 physical, u64 **logical, int *naddrs, int *stripe_len)
+{
+	struct extent_map *em;
+	struct map_lookup *map;
+	u64 *buf;
+	u64 bytenr;
+	u64 length;
+	u64 stripe_nr;
+	u64 rmap_len;
+	int i, j, nr = 0;
+
+	em = btrfs_get_chunk_map(fs_info, chunk_start, 1);
+	if (IS_ERR(em))
+		return -EIO;
+
+	map = em->map_lookup;
+	length = em->len;
+	rmap_len = map->stripe_len;
+
+	if (map->type & BTRFS_BLOCK_GROUP_RAID10)
+		length = div_u64(length, map->num_stripes / map->sub_stripes);
+	else if (map->type & BTRFS_BLOCK_GROUP_RAID0)
+		length = div_u64(length, map->num_stripes);
+	else if (map->type & BTRFS_BLOCK_GROUP_RAID56_MASK) {
+		length = div_u64(length, nr_data_stripes(map));
+		rmap_len = map->stripe_len * nr_data_stripes(map);
+	}
+
+	buf = kcalloc(map->num_stripes, sizeof(u64), GFP_NOFS);
+	BUG_ON(!buf); /* -ENOMEM */
+
+	for (i = 0; i < map->num_stripes; i++) {
+		if (map->stripes[i].physical > physical ||
+		    map->stripes[i].physical + length <= physical)
+			continue;
+
+		stripe_nr = physical - map->stripes[i].physical;
+		stripe_nr = div64_u64(stripe_nr, map->stripe_len);
+
+		if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
+			stripe_nr = stripe_nr * map->num_stripes + i;
+			stripe_nr = div_u64(stripe_nr, map->sub_stripes);
+		} else if (map->type & BTRFS_BLOCK_GROUP_RAID0) {
+			stripe_nr = stripe_nr * map->num_stripes + i;
+		} /* else if RAID[56], multiply by nr_data_stripes().
+		   * Alternatively, just use rmap_len below instead of
+		   * map->stripe_len */
+
+		bytenr = chunk_start + stripe_nr * rmap_len;
+		WARN_ON(nr >= map->num_stripes);
+		for (j = 0; j < nr; j++) {
+			if (buf[j] == bytenr)
+				break;
+		}
+		if (j == nr) {
+			WARN_ON(nr >= map->num_stripes);
+			buf[nr++] = bytenr;
+		}
+	}
+
+	*logical = buf;
+	*naddrs = nr;
+	*stripe_len = rmap_len;
+
+	free_extent_map(em);
+	return 0;
+}
+
 static int exclude_super_stripes(struct btrfs_block_group *cache)
 {
 	struct btrfs_fs_info *fs_info = cache->fs_info;
diff --git a/fs/btrfs/block-group.h b/fs/btrfs/block-group.h
index 9b409676c4b2..ef982c8921c8 100644
--- a/fs/btrfs/block-group.h
+++ b/fs/btrfs/block-group.h
@@ -248,4 +248,9 @@ static inline int btrfs_block_group_done(struct btrfs_block_group *cache)
 		cache->cached == BTRFS_CACHE_ERROR;
 }

+#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
+int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
+		     u64 physical, u64 **logical, int *naddrs, int *stripe_len);
+#endif
+
 #endif /* BTRFS_BLOCK_GROUP_H */
diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c
index f5c0c401c330..99ba3540186d 100644
--- a/fs/btrfs/volumes.c
+++ b/fs/btrfs/volumes.c
@@ -6108,75 +6108,6 @@ int btrfs_map_sblock(struct btrfs_fs_info *fs_info, enum btrfs_map_op op,
 	return __btrfs_map_block(fs_info, op, logical, length, bbio_ret, 0, 1);
 }

-int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
-		     u64 physical, u64 **logical, int *naddrs, int *stripe_len)
-{
-	struct extent_map *em;
-	struct map_lookup *map;
-	u64 *buf;
-	u64 bytenr;
-	u64 length;
-	u64 stripe_nr;
-	u64 rmap_len;
-	int i, j, nr = 0;
-
-	em = btrfs_get_chunk_map(fs_info, chunk_start, 1);
-	if (IS_ERR(em))
-		return -EIO;
-
-	map = em->map_lookup;
-	length = em->len;
-	rmap_len = map->stripe_len;
-
-	if (map->type & BTRFS_BLOCK_GROUP_RAID10)
-		length = div_u64(length, map->num_stripes / map->sub_stripes);
-	else if (map->type & BTRFS_BLOCK_GROUP_RAID0)
-		length = div_u64(length, map->num_stripes);
-	else if (map->type & BTRFS_BLOCK_GROUP_RAID56_MASK) {
-		length = div_u64(length, nr_data_stripes(map));
-		rmap_len = map->stripe_len * nr_data_stripes(map);
-	}
-
-	buf = kcalloc(map->num_stripes, sizeof(u64), GFP_NOFS);
-	BUG_ON(!buf); /* -ENOMEM */
-
-	for (i = 0; i < map->num_stripes; i++) {
-		if (map->stripes[i].physical > physical ||
-		    map->stripes[i].physical + length <= physical)
-			continue;
-
-		stripe_nr = physical - map->stripes[i].physical;
-		stripe_nr = div64_u64(stripe_nr, map->stripe_len);
-
-		if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
-			stripe_nr = stripe_nr * map->num_stripes + i;
-			stripe_nr = div_u64(stripe_nr, map->sub_stripes);
-		} else if (map->type & BTRFS_BLOCK_GROUP_RAID0) {
-			stripe_nr = stripe_nr * map->num_stripes + i;
-		} /* else if RAID[56], multiply by nr_data_stripes().
-		   * Alternatively, just use rmap_len below instead of
-		   * map->stripe_len */
-
-		bytenr = chunk_start + stripe_nr * rmap_len;
-		WARN_ON(nr >= map->num_stripes);
-		for (j = 0; j < nr; j++) {
-			if (buf[j] == bytenr)
-				break;
-		}
-		if (j == nr) {
-			WARN_ON(nr >= map->num_stripes);
-			buf[nr++] = bytenr;
-		}
-	}
-
-	*logical = buf;
-	*naddrs = nr;
-	*stripe_len = rmap_len;
-
-	free_extent_map(em);
-	return 0;
-}
-
 static inline void btrfs_end_bbio(struct btrfs_bio *bbio, struct bio *bio)
 {
 	bio->bi_private = bbio->private;
diff --git a/fs/btrfs/volumes.h b/fs/btrfs/volumes.h
index 3c56ef571b00..c929026bb70b 100644
--- a/fs/btrfs/volumes.h
+++ b/fs/btrfs/volumes.h
@@ -417,8 +417,6 @@ int btrfs_map_sblock(struct btrfs_fs_info *fs_info, enum btrfs_map_op op,
 		     struct btrfs_bio **bbio_ret);
 int btrfs_get_io_geometry(struct btrfs_fs_info *fs_info, enum btrfs_map_op op,
 		u64 logical, u64 len, struct btrfs_io_geometry *io_geom);
-int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
-		     u64 physical, u64 **logical, int *naddrs, int *stripe_len);
 int btrfs_read_sys_array(struct btrfs_fs_info *fs_info);
 int btrfs_read_chunk_tree(struct btrfs_fs_info *fs_info);
 int btrfs_alloc_chunk(struct btrfs_trans_handle *trans, u64 type);
--
2.17.1

[PATCH v2] btrfs: Add self-tests for btrfs_rmap_block

[Nikolay Borisov]

This is enough to exercise out of boundary address exclusion as well as
address matching.

Signed-off-by: Nikolay Borisov <nborisov@suse.com>
---
V2:
 * Adjusted comments about some members of struct rmap_test_vector
 * Fixed inline comments
 * Correctly handle error when initialising dummy device
 * Other minor cosmetic changes around comments/braces for single statement 'if'
 and structure initialization

 fs/btrfs/tests/extent-map-tests.c | 146 +++++++++++++++++++++++++++++-
 1 file changed, 145 insertions(+), 1 deletion(-)

diff --git a/fs/btrfs/tests/extent-map-tests.c b/fs/btrfs/tests/extent-map-tests.c
index 4a7f796c9900..4878904434af 100644
--- a/fs/btrfs/tests/extent-map-tests.c
+++ b/fs/btrfs/tests/extent-map-tests.c
@@ -6,6 +6,10 @@
 #include <linux/types.h>
 #include "btrfs-tests.h"
 #include "../ctree.h"
+#include "../volumes.h"
+#include "../disk-io.h"
+#include "../block-group.h"
+

 static void free_extent_map_tree(struct extent_map_tree *em_tree)
 {
@@ -437,11 +441,144 @@ static int test_case_4(struct btrfs_fs_info *fs_info,
 	return ret;
 }

+struct rmap_test_vector {
+	u64 raid_type;
+	u64 physical_start;
+	u64 data_stripe_size;
+	u64 num_data_stripes;
+	u64 num_stripes;
+	/* Assume we won't have more than 5 physical stripes */
+	u64 data_stripe_phys_start[5];
+	int expected_mapped_addr;
+	/* Physical to logical addresses */
+	u64 mapped_logical[5];
+};
+
+static int test_rmap_block(struct btrfs_fs_info *fs_info,
+			   struct rmap_test_vector *test)
+{
+	struct extent_map *em;
+	struct map_lookup *map = NULL;
+	u64 *logical;
+	int i, out_ndaddrs, out_stripe_len;
+	int ret = -EINVAL;
+
+	em = alloc_extent_map();
+	if (!em) {
+		test_std_err(TEST_ALLOC_EXTENT_MAP);
+		return -ENOMEM;
+	}
+
+	map = kmalloc(map_lookup_size(test->num_stripes), GFP_KERNEL);
+	if (!map) {
+		kfree(em);
+		test_std_err(TEST_ALLOC_EXTENT_MAP);
+		return -ENOMEM;
+	}
+
+	set_bit(EXTENT_FLAG_FS_MAPPING, &em->flags);
+	/* Start at 4gb logical address */
+	em->start = SZ_4G;
+	em->len = test->data_stripe_size * test->num_data_stripes;
+	em->block_len = em->len;
+	em->orig_block_len = test->data_stripe_size;
+	em->map_lookup = map;
+
+	map->num_stripes = test->num_stripes;
+	map->stripe_len = BTRFS_STRIPE_LEN;
+	map->type = test->raid_type;
+
+	for (i = 0; i < map->num_stripes; i++)
+	{
+		struct btrfs_device *dev = btrfs_alloc_dummy_device(fs_info);
+		if (!dev) {
+			test_err("ENOMEM while allocating dummy device");
+			goto out;
+		}
+		map->stripes[i].dev = dev;
+		map->stripes[i].physical = test->data_stripe_phys_start[i];
+	}
+
+	write_lock(&fs_info->mapping_tree.lock);
+	ret = add_extent_mapping(&fs_info->mapping_tree, em, 0);
+	write_unlock(&fs_info->mapping_tree.lock);
+	if (ret)
+		test_err("Error adding block group mapping to mapping tree");
+
+	ret = btrfs_rmap_block(fs_info, em->start, btrfs_sb_offset(1),
+			       &logical, &out_ndaddrs, &out_stripe_len);
+	if (ret || (out_ndaddrs == 0 && test->expected_mapped_addr)) {
+		test_err("Didn't rmap anything but expected %d",
+			 test->expected_mapped_addr);
+		goto out;
+	}
+
+	if (out_stripe_len != BTRFS_STRIPE_LEN) {
+		test_err("Calculated stripe len doesn't match");
+		goto out;
+	}
+
+	if (out_ndaddrs != test->expected_mapped_addr) {
+		for (i = 0; i < out_ndaddrs; i++)
+			test_msg("Mapped %llu", logical[i]);
+		test_err("Unexpected number of mapped addresses: %d", out_ndaddrs);
+		goto out;
+	}
+
+	for (i = 0; i < out_ndaddrs; i++) {
+		if (logical[i] != test->mapped_logical[i]) {
+			test_err("Unexpected logical address mapped");
+			goto out;
+		}
+	}
+
+	ret = 0;
+out:
+	write_lock(&fs_info->mapping_tree.lock);
+	remove_extent_mapping(&fs_info->mapping_tree, em);
+	write_unlock(&fs_info->mapping_tree.lock);
+	/* For us */
+	free_extent_map(em);
+	/* For the tree */
+	free_extent_map(em);
+	return ret;
+}
+
 int btrfs_test_extent_map(void)
 {
 	struct btrfs_fs_info *fs_info = NULL;
 	struct extent_map_tree *em_tree;
-	int ret = 0;
+	int ret = 0, i;
+	struct rmap_test_vector rmap_tests[] = {
+		{
+			/*
+			 * Tests a chunk with 2 data stripes one of which
+			 * interesects the physical address of the super block
+			 * is correctly recognised.
+			 */
+			.raid_type = BTRFS_BLOCK_GROUP_RAID1,
+			.physical_start = SZ_64M - SZ_4M,
+			.data_stripe_size = SZ_256M,
+			.num_data_stripes = 2,
+			.num_stripes = 2,
+			.data_stripe_phys_start = {SZ_64M - SZ_4M, SZ_64M - SZ_4M + SZ_256M},
+			.expected_mapped_addr = 1,
+			.mapped_logical= {SZ_4G + SZ_4M}
+		},
+		{
+			/* test that out of range physical addresses are ignored */
+
+			 /* SINGLE chunk type */
+			.raid_type = 0,
+			.physical_start = SZ_4G,
+			.data_stripe_size = SZ_256M,
+			.num_data_stripes = 1,
+			.num_stripes = 1,
+			.data_stripe_phys_start = {SZ_256M},
+			.expected_mapped_addr = 0,
+			.mapped_logical = {0}
+		}
+	};

 	test_msg("running extent_map tests");

@@ -474,6 +611,13 @@ int btrfs_test_extent_map(void)
 		goto out;
 	ret = test_case_4(fs_info, em_tree);

+	test_msg("Running rmap tests.");
+	for (i = 0; i < ARRAY_SIZE(rmap_tests); i++) {
+		ret = test_rmap_block(fs_info, &rmap_tests[i]);
+		if (ret)
+			goto out;
+	}
+
 out:
 	kfree(em_tree);
 	btrfs_free_dummy_fs_info(fs_info);
--
2.17.1

Re: [PATCH v2] btrfs: Move and unexport btrfs_rmap_block

[David Sterba]

On Tue, Dec 10, 2019 at 07:57:51PM +0200, Nikolay Borisov wrote:
> It's used only during initial block group reading to map physical
> address of super block to a list of logical ones. Make it private to
> block-group.c, add proper kernel doc and ensure it's exported only for
> tests.

Btw that's not proper kernel doc formatting, I've fixed it.

> +/*

/**

> + * btrfs_rmap_block - Maps a particular @physical disk address to a list of @logical

One line with brief description

> + * addresses. Used primarily to exclude those portions of a block group that
> + * contain super block copies.
> + *
> + * chunk_start - Logical address of block group

@argument: description

> + * physical - Physical address to map to logical addresses
> + * logical - Return array of logical addresses which map to @physical
> + * naddrs - Length of @logical
> + * stripe_len - size of IO stripe for the given block group

And the long description is here

> + */

Re: [PATCH v2] btrfs: Add self-tests for btrfs_rmap_block

[David Sterba]

On Tue, Dec 10, 2019 at 08:00:45PM +0200, Nikolay Borisov wrote:
> This is enough to exercise out of boundary address exclusion as well as
> address matching.
> 
> Signed-off-by: Nikolay Borisov <nborisov@suse.com>
> ---
> V2:
>  * Adjusted comments about some members of struct rmap_test_vector
>  * Fixed inline comments
>  * Correctly handle error when initialising dummy device
>  * Other minor cosmetic changes around comments/braces for single statement 'if'
>  and structure initialization

I still found issues unfixed from v1 and some that I did not notice
before

>  fs/btrfs/tests/extent-map-tests.c | 146 +++++++++++++++++++++++++++++-
>  1 file changed, 145 insertions(+), 1 deletion(-)
> 
> diff --git a/fs/btrfs/tests/extent-map-tests.c b/fs/btrfs/tests/extent-map-tests.c
> index 4a7f796c9900..4878904434af 100644
> --- a/fs/btrfs/tests/extent-map-tests.c
> +++ b/fs/btrfs/tests/extent-map-tests.c
> @@ -6,6 +6,10 @@
>  #include <linux/types.h>
>  #include "btrfs-tests.h"
>  #include "../ctree.h"
> +#include "../volumes.h"
> +#include "../disk-io.h"
> +#include "../block-group.h"
> +

Extra newline

> 
>  static void free_extent_map_tree(struct extent_map_tree *em_tree)
>  {
> @@ -437,11 +441,144 @@ static int test_case_4(struct btrfs_fs_info *fs_info,
>  	return ret;
>  }
> 
> +struct rmap_test_vector {
> +	u64 raid_type;
> +	u64 physical_start;
> +	u64 data_stripe_size;
> +	u64 num_data_stripes;
> +	u64 num_stripes;
> +	/* Assume we won't have more than 5 physical stripes */
> +	u64 data_stripe_phys_start[5];
> +	int expected_mapped_addr;

This should be bool

> +	/* Physical to logical addresses */
> +	u64 mapped_logical[5];
> +};
> +
> +static int test_rmap_block(struct btrfs_fs_info *fs_info,
> +			   struct rmap_test_vector *test)
> +{
> +	struct extent_map *em;
> +	struct map_lookup *map = NULL;
> +	u64 *logical;
> +	int i, out_ndaddrs, out_stripe_len;
> +	int ret = -EINVAL;
> +
> +	em = alloc_extent_map();
> +	if (!em) {
> +		test_std_err(TEST_ALLOC_EXTENT_MAP);
> +		return -ENOMEM;
> +	}
> +
> +	map = kmalloc(map_lookup_size(test->num_stripes), GFP_KERNEL);
> +	if (!map) {
> +		kfree(em);
> +		test_std_err(TEST_ALLOC_EXTENT_MAP);
> +		return -ENOMEM;
> +	}
> +
> +	set_bit(EXTENT_FLAG_FS_MAPPING, &em->flags);
> +	/* Start at 4gb logical address */
> +	em->start = SZ_4G;
> +	em->len = test->data_stripe_size * test->num_data_stripes;
> +	em->block_len = em->len;
> +	em->orig_block_len = test->data_stripe_size;
> +	em->map_lookup = map;
> +
> +	map->num_stripes = test->num_stripes;
> +	map->stripe_len = BTRFS_STRIPE_LEN;
> +	map->type = test->raid_type;
> +
> +	for (i = 0; i < map->num_stripes; i++)
> +	{
> +		struct btrfs_device *dev = btrfs_alloc_dummy_device(fs_info);
> +		if (!dev) {
> +			test_err("ENOMEM while allocating dummy device");

			ret = -ENOMEM;

And the error message should follow the scheme of the other standard
error messages (defined in test_error)

> +			goto out;
> +		}
> +		map->stripes[i].dev = dev;
> +		map->stripes[i].physical = test->data_stripe_phys_start[i];
> +	}
> +
> +	write_lock(&fs_info->mapping_tree.lock);
> +	ret = add_extent_mapping(&fs_info->mapping_tree, em, 0);
> +	write_unlock(&fs_info->mapping_tree.lock);
> +	if (ret)
> +		test_err("Error adding block group mapping to mapping tree");

Error found but no exit, other selftests do that. And no capital letter
at the beginning of the string. I've added a label before the 2nd
free_extent_map.

> +
> +	ret = btrfs_rmap_block(fs_info, em->start, btrfs_sb_offset(1),
> +			       &logical, &out_ndaddrs, &out_stripe_len);
> +	if (ret || (out_ndaddrs == 0 && test->expected_mapped_addr)) {
> +		test_err("Didn't rmap anything but expected %d",

... in all strings passed to test_err

> +			 test->expected_mapped_addr);
> +		goto out;
> +	}
> +
> +	if (out_stripe_len != BTRFS_STRIPE_LEN) {
> +		test_err("Calculated stripe len doesn't match");

Here

> +		goto out;
> +	}
> +
> +	if (out_ndaddrs != test->expected_mapped_addr) {
> +		for (i = 0; i < out_ndaddrs; i++)
> +			test_msg("Mapped %llu", logical[i]);

Here

> +		test_err("Unexpected number of mapped addresses: %d", out_ndaddrs);

Here
> +		goto out;
> +	}
> +
> +	for (i = 0; i < out_ndaddrs; i++) {
> +		if (logical[i] != test->mapped_logical[i]) {
> +			test_err("Unexpected logical address mapped");

Here

> +			goto out;
> +		}
> +	}
> +
> +	ret = 0;
> +out:
> +	write_lock(&fs_info->mapping_tree.lock);
> +	remove_extent_mapping(&fs_info->mapping_tree, em);
> +	write_unlock(&fs_info->mapping_tree.lock);
> +	/* For us */
> +	free_extent_map(em);
> +	/* For the tree */
> +	free_extent_map(em);
> +	return ret;
> +}
> +
>  int btrfs_test_extent_map(void)
>  {
>  	struct btrfs_fs_info *fs_info = NULL;
>  	struct extent_map_tree *em_tree;
> -	int ret = 0;
> +	int ret = 0, i;
> +	struct rmap_test_vector rmap_tests[] = {
> +		{
> +			/*
> +			 * Tests a chunk with 2 data stripes one of which
> +			 * interesects the physical address of the super block
> +			 * is correctly recognised.
> +			 */
> +			.raid_type = BTRFS_BLOCK_GROUP_RAID1,
> +			.physical_start = SZ_64M - SZ_4M,
> +			.data_stripe_size = SZ_256M,
> +			.num_data_stripes = 2,
> +			.num_stripes = 2,
> +			.data_stripe_phys_start = {SZ_64M - SZ_4M, SZ_64M - SZ_4M + SZ_256M},

Formatting

> +			.expected_mapped_addr = 1,
> +			.mapped_logical= {SZ_4G + SZ_4M}
> +		},
> +		{
> +			/* test that out of range physical addresses are ignored */
> +
> +			 /* SINGLE chunk type */
> +			.raid_type = 0,
> +			.physical_start = SZ_4G,
> +			.data_stripe_size = SZ_256M,
> +			.num_data_stripes = 1,
> +			.num_stripes = 1,
> +			.data_stripe_phys_start = {SZ_256M},
> +			.expected_mapped_addr = 0,
> +			.mapped_logical = {0}
> +		}
> +	};
> 
>  	test_msg("running extent_map tests");
> 
> @@ -474,6 +611,13 @@ int btrfs_test_extent_map(void)
>  		goto out;
>  	ret = test_case_4(fs_info, em_tree);
> 
> +	test_msg("Running rmap tests.");

	test_msg("running rmap tests");

> +	for (i = 0; i < ARRAY_SIZE(rmap_tests); i++) {
> +		ret = test_rmap_block(fs_info, &rmap_tests[i]);
> +		if (ret)
> +			goto out;
> +	}
> +
>  out:
>  	kfree(em_tree);
>  	btrfs_free_dummy_fs_info(fs_info);
> --
> 2.17.1

Re: [PATCH v2] btrfs: Add self-tests for btrfs_rmap_block

[Nikolay Borisov]

On 2.01.20 г. 17:40 ч., David Sterba wrote:
> On Tue, Dec 10, 2019 at 08:00:45PM +0200, Nikolay Borisov wrote:
>> This is enough to exercise out of boundary address exclusion as well as
>> address matching.
>>
>> Signed-off-by: Nikolay Borisov <nborisov@suse.com>
>> ---
>> V2:
>>  * Adjusted comments about some members of struct rmap_test_vector
>>  * Fixed inline comments
>>  * Correctly handle error when initialising dummy device
>>  * Other minor cosmetic changes around comments/braces for single statement 'if'
>>  and structure initialization
> 
> I still found issues unfixed from v1 and some that I did not notice
> before
> 
>>  fs/btrfs/tests/extent-map-tests.c | 146 +++++++++++++++++++++++++++++-
>>  1 file changed, 145 insertions(+), 1 deletion(-)
>>
>> diff --git a/fs/btrfs/tests/extent-map-tests.c b/fs/btrfs/tests/extent-map-tests.c
>> index 4a7f796c9900..4878904434af 100644
>> --- a/fs/btrfs/tests/extent-map-tests.c
>> +++ b/fs/btrfs/tests/extent-map-tests.c
>> @@ -6,6 +6,10 @@
>>  #include <linux/types.h>
>>  #include "btrfs-tests.h"
>>  #include "../ctree.h"
>> +#include "../volumes.h"
>> +#include "../disk-io.h"
>> +#include "../block-group.h"
>> +
> 
> Extra newline
> 
>>
>>  static void free_extent_map_tree(struct extent_map_tree *em_tree)
>>  {
>> @@ -437,11 +441,144 @@ static int test_case_4(struct btrfs_fs_info *fs_info,
>>  	return ret;
>>  }
>>
>> +struct rmap_test_vector {
>> +	u64 raid_type;
>> +	u64 physical_start;
>> +	u64 data_stripe_size;
>> +	u64 num_data_stripes;
>> +	u64 num_stripes;
>> +	/* Assume we won't have more than 5 physical stripes */
>> +	u64 data_stripe_phys_start[5];
>> +	int expected_mapped_addr;
> 
> This should be bool

Actually the idea here is for expected_mapped_addr to contains the
number of addresses we are expected to map. Currently tests only expect
0 or 1 but if tests are expanded in the future  this might be 2 or 3.

THe body of the test does:

 if (out_ndaddrs != test->expected_mapped_addr) {
                  for (i = 0; i < out_ndaddrs; i++)

                          test_msg("Mapped %llu", logical[i]);


<snip>
>>  int btrfs_test_extent_map(void)
>>  {
>>  	struct btrfs_fs_info *fs_info = NULL;
>>  	struct extent_map_tree *em_tree;
>> -	int ret = 0;
>> +	int ret = 0, i;
>> +	struct rmap_test_vector rmap_tests[] = {
>> +		{
>> +			/*
>> +			 * Tests a chunk with 2 data stripes one of which
>> +			 * interesects the physical address of the super block
>> +			 * is correctly recognised.
>> +			 */
>> +			.raid_type = BTRFS_BLOCK_GROUP_RAID1,
>> +			.physical_start = SZ_64M - SZ_4M,
>> +			.data_stripe_size = SZ_256M,
>> +			.num_data_stripes = 2,
>> +			.num_stripes = 2,
>> +			.data_stripe_phys_start = {SZ_64M - SZ_4M, SZ_64M - SZ_4M + SZ_256M},
> 
> Formatting


What do you mean?

<snip>

Re: [PATCH v2] btrfs: Add self-tests for btrfs_rmap_block

[David Sterba]

On Fri, Jan 10, 2020 at 04:46:20PM +0200, Nikolay Borisov wrote:
> >> +	int expected_mapped_addr;
> > 
> > This should be bool
> 
> Actually the idea here is for expected_mapped_addr to contains the
> number of addresses we are expected to map. Currently tests only expect
> 0 or 1 but if tests are expanded in the future  this might be 2 or 3.
> 
> THe body of the test does:
> 
>  if (out_ndaddrs != test->expected_mapped_addr) {
>                   for (i = 0; i < out_ndaddrs; i++)
> 
>                           test_msg("Mapped %llu", logical[i]);

Ok, int is fine then.

> >> +	struct rmap_test_vector rmap_tests[] = {
> >> +		{
> >> +			/*
> >> +			 * Tests a chunk with 2 data stripes one of which
> >> +			 * interesects the physical address of the super block
> >> +			 * is correctly recognised.
> >> +			 */
> >> +			.raid_type = BTRFS_BLOCK_GROUP_RAID1,
> >> +			.physical_start = SZ_64M - SZ_4M,
> >> +			.data_stripe_size = SZ_256M,
> >> +			.num_data_stripes = 2,
> >> +			.num_stripes = 2,
> >> +			.data_stripe_phys_start = {SZ_64M - SZ_4M, SZ_64M - SZ_4M + SZ_256M},
> > 
> > Formatting
> 
> What do you mean?

Line over 80 cols

Re: [PATCH 5/6] btrfs: Read stripe len directly in btrfs_rmap_block

[David Sterba]

On Tue, Nov 19, 2019 at 02:05:54PM +0200, Nikolay Borisov wrote:
> extent_map::orig_block_len contains the size of a physical stripe when
> it's used to describe block groups. So get the size directly in
> btrfs_rmap_block rather than open-coding the calculations. No
> functional changes.
> 
> Signed-off-by: Nikolay Borisov <nborisov@suse.com>
> ---
>  fs/btrfs/block-group.c | 11 +++--------
>  1 file changed, 3 insertions(+), 8 deletions(-)
> 
> diff --git a/fs/btrfs/block-group.c b/fs/btrfs/block-group.c
> index c3b1f304bc70..2ab4d9cb598a 100644
> --- a/fs/btrfs/block-group.c
> +++ b/fs/btrfs/block-group.c
> @@ -1546,17 +1546,12 @@ int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
>  		return -EIO;
>  
>  	map = em->map_lookup;
> -	data_stripe_length = em->len;
> +	data_stripe_length = em->orig_block_len;
>  	io_stripe_size = map->stripe_len;
>  
> -	if (map->type & BTRFS_BLOCK_GROUP_RAID10)
> -		data_stripe_length = div_u64(data_stripe_length, map->num_stripes / map->sub_stripes);
> -	else if (map->type & BTRFS_BLOCK_GROUP_RAID0)
> -		data_stripe_length = div_u64(data_stripe_length, map->num_stripes);
> -	else if (map->type & BTRFS_BLOCK_GROUP_RAID56_MASK) {
> -		data_stripe_length = div_u64(data_stripe_length, nr_data_stripes(map));
> +	/* For raid5/6 adjust to a full IO stripe length */
> +	if (map->type & BTRFS_BLOCK_GROUP_RAID56_MASK)
>  		io_stripe_size = map->stripe_len * nr_data_stripes(map);

I'm not convinced this is 'no functional change' so will merge only
patches 1-4 for now as I have reviewed them and want to add them to
misc-next before the 5.6 freeze.

Re: [PATCH 5/6] btrfs: Read stripe len directly in btrfs_rmap_block

[Nikolay Borisov]

On 14.01.20 г. 18:54 ч., David Sterba wrote:
> On Tue, Nov 19, 2019 at 02:05:54PM +0200, Nikolay Borisov wrote:
>> extent_map::orig_block_len contains the size of a physical stripe when
>> it's used to describe block groups. So get the size directly in
>> btrfs_rmap_block rather than open-coding the calculations. No
>> functional changes.
>>
>> Signed-off-by: Nikolay Borisov <nborisov@suse.com>
>> ---
>>  fs/btrfs/block-group.c | 11 +++--------
>>  1 file changed, 3 insertions(+), 8 deletions(-)
>>
>> diff --git a/fs/btrfs/block-group.c b/fs/btrfs/block-group.c
>> index c3b1f304bc70..2ab4d9cb598a 100644
>> --- a/fs/btrfs/block-group.c
>> +++ b/fs/btrfs/block-group.c
>> @@ -1546,17 +1546,12 @@ int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
>>  		return -EIO;
>>  
>>  	map = em->map_lookup;
>> -	data_stripe_length = em->len;
>> +	data_stripe_length = em->orig_block_len;
>>  	io_stripe_size = map->stripe_len;
>>  
>> -	if (map->type & BTRFS_BLOCK_GROUP_RAID10)
>> -		data_stripe_length = div_u64(data_stripe_length, map->num_stripes / map->sub_stripes);
>> -	else if (map->type & BTRFS_BLOCK_GROUP_RAID0)
>> -		data_stripe_length = div_u64(data_stripe_length, map->num_stripes);
>> -	else if (map->type & BTRFS_BLOCK_GROUP_RAID56_MASK) {
>> -		data_stripe_length = div_u64(data_stripe_length, nr_data_stripes(map));
>> +	/* For raid5/6 adjust to a full IO stripe length */
>> +	if (map->type & BTRFS_BLOCK_GROUP_RAID56_MASK)
>>  		io_stripe_size = map->stripe_len * nr_data_stripes(map);
> 
> I'm not convinced this is 'no functional change' so will merge only
> patches 1-4 for now as I have reviewed them and want to add them to
> misc-next before the 5.6 freeze.
> 

THe easiest way to convince yourself is to work out the maths happening
in __btrfs_alloc_chunk, since orig_block_len for chunks is set there.