[PATCH 0/5] Rework/enhance btrfs-map-logical

[PATCH 0/5] Rework/enhance btrfs-map-logical

[Qu Wenruo]

Although btrfs-map-logical is mainly a tool for developers, but even as
a developer, I feel quite frustrated about the bug I found:

1) Assert if pass bytenr of a tree root
The most annoying one.
---
$ btrfs-map-logical  -l 29425664 /dev/sda6 
mirror 1 logical 29425664 physical 37814272 device /dev/sda6
mirror 2 logical 29425664 physical 1111556096 device /dev/sda6
extent_io.c:582: free_extent_buffer: Assertion `eb->refs < 0` failed.
btrfs-map-logical[0x41c464]
btrfs-map-logical(free_extent_buffer+0xc0)[0x41cf10]
btrfs-map-logical(btrfs_release_all_roots+0x59)[0x40e649]
btrfs-map-logical(close_ctree+0x1aa)[0x40f51a]
btrfs-map-logical(main+0x387)[0x4077c7]
/usr/lib/libc.so.6(__libc_start_main+0xf0)[0x7f1e7f619790]
btrfs-map-logical(_start+0x29)[0x4078f9]
---

2) Strange logical offset and non-exist mapping
---
$ btrfs-map-logical  -l 1 -b 8192 /dev/sda6 
mirror 1 logical 1 physical 1 device /dev/sda6
mirror 1 logical 4097 physical 4097 device /dev/sda6
---
There is no extents in that range normally.
Despite that, for the first mirror, it's OK to start from 1 as I passed an
unaligned bytenr.
But why the 2nd non-exist mapping is also unaligned?

For all the fix, see the commit message of the 5th patch.

Qu Wenruo (5):
  btrfs-progs: Export read_extent_data function.
  btrfs-progs: map-logical: Introduce map_one_extent function.
  Btrfs-progs: map-logical: Introduce print_mapping_info function.
  Btrfs-progs: map-logical: Introduce write_extent_content function.
  btrfs-progs: map-logical: Rework map-logical logics.

 btrfs-map-logical.c | 273 +++++++++++++++++++++++++++++++++++++++-------------
 cmds-check.c        |  34 -------
 disk-io.c           |  34 +++++++
 disk-io.h           |   2 +
 4 files changed, 243 insertions(+), 100 deletions(-)

-- 
2.4.3

[PATCH 1/5] btrfs-progs: Export read_extent_data function.

[Qu Wenruo]

Export it for later btrfs-map-logical cleanup.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 34 ----------------------------------
 disk-io.c    | 34 ++++++++++++++++++++++++++++++++++
 disk-io.h    |  2 ++
 3 files changed, 36 insertions(+), 34 deletions(-)

diff --git a/cmds-check.c b/cmds-check.c
index db121b1..778f141 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -5235,40 +5235,6 @@ static int check_space_cache(struct btrfs_root *root)
 	return error ? -EINVAL : 0;
 }
 
-static int read_extent_data(struct btrfs_root *root, char *data,
-			u64 logical, u64 *len, int mirror)
-{
-	u64 offset = 0;
-	struct btrfs_multi_bio *multi = NULL;
-	struct btrfs_fs_info *info = root->fs_info;
-	struct btrfs_device *device;
-	int ret = 0;
-	u64 max_len = *len;
-
-	ret = btrfs_map_block(&info->mapping_tree, READ, logical, len,
-			      &multi, mirror, NULL);
-	if (ret) {
-		fprintf(stderr, "Couldn't map the block %llu\n",
-				logical + offset);
-		goto err;
-	}
-	device = multi->stripes[0].dev;
-
-	if (device->fd == 0)
-		goto err;
-	if (*len > max_len)
-		*len = max_len;
-
-	ret = pread64(device->fd, data, *len, multi->stripes[0].physical);
-	if (ret != *len)
-		ret = -EIO;
-	else
-		ret = 0;
-err:
-	kfree(multi);
-	return ret;
-}
-
 static int check_extent_csums(struct btrfs_root *root, u64 bytenr,
 			u64 num_bytes, unsigned long leaf_offset,
 			struct extent_buffer *eb) {
diff --git a/disk-io.c b/disk-io.c
index 2a7feb0..720fee4 100644
--- a/disk-io.c
+++ b/disk-io.c
@@ -340,6 +340,40 @@ struct extent_buffer *read_tree_block(struct btrfs_root *root, u64 bytenr,
 	return ERR_PTR(ret);
 }
 
+int read_extent_data(struct btrfs_root *root, char *data,
+			   u64 logical, u64 *len, int mirror)
+{
+	u64 offset = 0;
+	struct btrfs_multi_bio *multi = NULL;
+	struct btrfs_fs_info *info = root->fs_info;
+	struct btrfs_device *device;
+	int ret = 0;
+	u64 max_len = *len;
+
+	ret = btrfs_map_block(&info->mapping_tree, READ, logical, len,
+			      &multi, mirror, NULL);
+	if (ret) {
+		fprintf(stderr, "Couldn't map the block %llu\n",
+				logical + offset);
+		goto err;
+	}
+	device = multi->stripes[0].dev;
+
+	if (device->fd == 0)
+		goto err;
+	if (*len > max_len)
+		*len = max_len;
+
+	ret = pread64(device->fd, data, *len, multi->stripes[0].physical);
+	if (ret != *len)
+		ret = -EIO;
+	else
+		ret = 0;
+err:
+	kfree(multi);
+	return ret;
+}
+
 int write_and_map_eb(struct btrfs_trans_handle *trans,
 		     struct btrfs_root *root,
 		     struct extent_buffer *eb)
diff --git a/disk-io.h b/disk-io.h
index 62eb566..87e1cd9 100644
--- a/disk-io.h
+++ b/disk-io.h
@@ -66,6 +66,8 @@ struct btrfs_device;
 int read_whole_eb(struct btrfs_fs_info *info, struct extent_buffer *eb, int mirror);
 struct extent_buffer *read_tree_block(struct btrfs_root *root, u64 bytenr,
 				      u32 blocksize, u64 parent_transid);
+int read_extent_data(struct btrfs_root *root, char *data, u64 logical,
+		     u64 *len, int mirror);
 void readahead_tree_block(struct btrfs_root *root, u64 bytenr, u32 blocksize,
 			  u64 parent_transid);
 struct extent_buffer *btrfs_find_create_tree_block(struct btrfs_root *root,
-- 
2.4.3

[PATCH 2/5] btrfs-progs: map-logical: Introduce map_one_extent function.

[Qu Wenruo]

Introduce the function to get accurate extent length based on extent
tree search.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 btrfs-map-logical.c | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 58 insertions(+)

diff --git a/btrfs-map-logical.c b/btrfs-map-logical.c
index e5e2da5..8442779 100644
--- a/btrfs-map-logical.c
+++ b/btrfs-map-logical.c
@@ -35,6 +35,64 @@
  * */
 static FILE *info_file;
 
+static int map_one_extent(struct btrfs_fs_info *fs_info,
+			  u64 *logical_ret, u64 *len_ret, int search_foward)
+{
+	struct btrfs_path *path;
+	struct btrfs_key key;
+	u64 logical;
+	u64 len = 0;
+	int ret = 0;
+
+	BUG_ON(!logical_ret);
+	logical = *logical_ret;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	key.objectid = logical;
+	key.type = 0;
+	key.offset = 0;
+
+	ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path,
+				0, 0);
+	if (ret < 0)
+		goto out;
+	BUG_ON(ret == 0);
+	ret = 0;
+
+again:
+	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+	if ((search_foward && key.objectid < logical) ||
+	    (!search_foward && key.objectid > logical) ||
+	    (key.type != BTRFS_EXTENT_ITEM_KEY &&
+	     key.type != BTRFS_METADATA_ITEM_KEY)) {
+		if (!search_foward)
+			ret = btrfs_previous_extent_item(fs_info->extent_root,
+							 path, 0);
+		else
+			ret = btrfs_next_item(fs_info->extent_root, path);
+		if (ret)
+			goto out;
+		goto again;
+	}
+	logical = key.objectid;
+	if (key.type == BTRFS_METADATA_ITEM_KEY)
+		len = fs_info->tree_root->leafsize;
+	else
+		len = key.offset;
+
+out:
+	btrfs_free_path(path);
+	if (!ret) {
+		*logical_ret = logical;
+		if (len_ret)
+			*len_ret = len;
+	}
+	return ret;
+}
+
 static struct extent_buffer * debug_read_block(struct btrfs_root *root,
 		u64 bytenr, u32 blocksize, u64 copy)
 {
-- 
2.4.3

[PATCH 3/5] Btrfs-progs: map-logical: Introduce print_mapping_info function.

[Qu Wenruo]

The new function will print the mapping info of given range
[logical, logical+len).

Note, caller must ensure the range are completely inside an extent.
Or btrfs_map_block can return -ENOENT.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 btrfs-map-logical.c | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 63 insertions(+)

diff --git a/btrfs-map-logical.c b/btrfs-map-logical.c
index 8442779..22ece82 100644
--- a/btrfs-map-logical.c
+++ b/btrfs-map-logical.c
@@ -93,6 +93,69 @@ out:
 	return ret;
 }
 
+static int __print_mapping_info(struct btrfs_fs_info *fs_info, u64 logical,
+				u64 len, int mirror_num)
+{
+	struct btrfs_multi_bio *multi = NULL;
+	u64 cur_offset = 0;
+	u64 cur_len;
+	int ret = 0;
+
+	while (cur_offset < len) {
+		struct btrfs_device *device;
+		int i;
+
+		cur_len = len - cur_offset;
+		ret = btrfs_map_block(&fs_info->mapping_tree, READ,
+				logical + cur_offset, &cur_len,
+				&multi, mirror_num, NULL);
+		if (ret) {
+			fprintf(info_file,
+				"Error: fails to map mirror%d logical %llu: %s\n",
+				mirror_num, logical, strerror(-ret));
+			return ret;
+		}
+		for (i = 0; i < multi->num_stripes; i++) {
+			device = multi->stripes[i].dev;
+			fprintf(info_file,
+				"mirror %d logical %Lu physical %Lu device %s\n",
+				mirror_num, logical + cur_offset,
+				multi->stripes[0].physical,
+				device->name);
+		}
+		kfree(multi);
+		multi = NULL;
+		cur_offset += cur_len;
+	}
+	return ret;
+}
+
+/*
+ * Logical and len is the exact value of a extent.
+ * And offset is the offset inside the extent. It's only used for case
+ * where user only want to print part of the extent.
+ *
+ * Caller *MUST* ensure the range [logical,logical+len) are in one extent.
+ * Or we can encounter the following case, causing a -ENOENT error:
+ * |<-----given parameter------>|
+ *		|<------ Extent A ----->|
+ */
+static int print_mapping_info(struct btrfs_fs_info *fs_info, u64 logical,
+			      u64 len)
+{
+	int num_copies;
+	int mirror_num;
+	int ret = 0;
+
+	num_copies = btrfs_num_copies(&fs_info->mapping_tree, logical, len);
+	for (mirror_num = 1; mirror_num <= num_copies; mirror_num++) {
+		ret = __print_mapping_info(fs_info, logical, len, mirror_num);
+		if (ret < 0)
+			return ret;
+	}
+	return ret;
+}
+
 static struct extent_buffer * debug_read_block(struct btrfs_root *root,
 		u64 bytenr, u32 blocksize, u64 copy)
 {
-- 
2.4.3

[PATCH 4/5] Btrfs-progs: map-logical: Introduce write_extent_content function.

[Qu Wenruo]

This function will write extent content info desired file.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 btrfs-map-logical.c | 34 ++++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)

diff --git a/btrfs-map-logical.c b/btrfs-map-logical.c
index 22ece82..1ee101c 100644
--- a/btrfs-map-logical.c
+++ b/btrfs-map-logical.c
@@ -30,6 +30,8 @@
 #include "list.h"
 #include "utils.h"
 
+#define BUFFER_SIZE (64 * 1024)
+
 /* we write the mirror info to stdout unless they are dumping the data
  * to stdout
  * */
@@ -156,6 +158,38 @@ static int print_mapping_info(struct btrfs_fs_info *fs_info, u64 logical,
 	return ret;
 }
 
+/* Same requisition as print_mapping_info function */
+static int write_extent_content(struct btrfs_fs_info *fs_info, int out_fd,
+				u64 logical, u64 length, int mirror)
+{
+	char buffer[BUFFER_SIZE];
+	u64 cur_offset = 0;
+	u64 cur_len;
+	int ret = 0;
+
+	while (cur_offset < length) {
+		cur_len = min_t(u64, length - cur_offset, BUFFER_SIZE);
+		ret = read_extent_data(fs_info->tree_root, buffer,
+				       logical + cur_offset, &cur_len, mirror);
+		if (ret < 0) {
+			fprintf(stderr,
+				"Failed to read extent at [%llu, %llu]: %s\n",
+				logical, logical + length, strerror(-ret));
+			return ret;
+		}
+		ret = write(out_fd, buffer, cur_len);
+		if (ret < 0 || ret != cur_len) {
+			if (ret > 0)
+				ret = -EINTR;
+			fprintf(stderr, "output file write failed: %s\n",
+				strerror(-ret));
+			return ret;
+		}
+		cur_offset += cur_len;
+	}
+	return ret;
+}
+
 static struct extent_buffer * debug_read_block(struct btrfs_root *root,
 		u64 bytenr, u32 blocksize, u64 copy)
 {
-- 
2.4.3

[PATCH 5/5] btrfs-progs: map-logical: Rework map-logical logics.

[Qu Wenruo]

[[BUG]]
The original map-logical has the following problems:
1) Assert if we pass any tree root bytenr.
The problem is easy to trigger, here the number 29622272 is the bytenr of tree root:

 # btrfs-map-logical -l 29622272 /dev/sda6
 mirror 1 logical 29622272 physical 38010880 device /dev/sda6
 mirror 2 logical 29622272 physical 1111752704 device /dev/sda6
 extent_io.c:582: free_extent_buffer: Assertion `eb->refs < 0` failed.
 btrfs-map-logical[0x41c464]
 btrfs-map-logical(free_extent_buffer+0xc0)[0x41cf10]
 btrfs-map-logical(btrfs_release_all_roots+0x59)[0x40e649]
 btrfs-map-logical(close_ctree+0x1aa)[0x40f51a]
 btrfs-map-logical(main+0x387)[0x4077c7]
 /usr/lib/libc.so.6(__libc_start_main+0xf0)[0x7f80a5562790]
 btrfs-map-logical(_start+0x29)[0x4078f9]

The problem is that, btrfs-map-logical always use sectorsize as default
block size to call alloc_extent_buffer.
And when it failes to find the block with the same size, it will free
the extent buffer in a incorrect method(Free and create a new one with
refs == 1).

2) Will return map result for non-exist extent.

 # btrfs-map-logical -l 1 -b 123456 /dev/sda6
 mirror 1 logical 1 physical 1 device /dev/sda6
 mirror 1 logical 4097 physical 4097 device /dev/sda6
 mirror 1 logical 8193 physical 8193 device /dev/sda6
 ...

Normally, before bytenr 12582912, there should be no extent as that's
the mkfs time temp metadata/system chunk.

But map-logical will still map them out.

Not to mention the 1 offset among all results.

[[FIX]]
This patch will rework the whole map logical by the following methods:
1) Always do things inside a extent
Even under the following case, map logical will only return covered
range in existing extents.

	|<------ range given ------->|
|<-Extent A->|	|<-Extent B->|	|<---Extent C->|
Result:
	|<-->|	|<---------->|	|<-->|

So with this patch, we will search extent tree to ensure all operation
are inside a extent before we do some stupid things.

2) No direct call on alloc_extent_buffer function.

That low-level function shouldn't be called at such high level.
It's only designed for low-level tree operation.

So in this patch we will only use safe high level functions avoid such
problem.

[[RESULT]]
With this patch, no assert will be triggered and better handle on
non-exist extents.

 # btrfs-map-logical -l 29622272 /dev/sda6
 mirror 1 logical 29622272 physical 38010880 device /dev/sda6
 mirror 2 logical 29622272 physical 1111752704 device /dev/sda6

 # btrfs-map-logical -l 1 -b 123456 /dev/sda6
 No extent found at range [1,123457)

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 btrfs-map-logical.c | 148 ++++++++++++++++++++++++----------------------------
 1 file changed, 67 insertions(+), 81 deletions(-)

diff --git a/btrfs-map-logical.c b/btrfs-map-logical.c
index 1ee101c..a88e56e 100644
--- a/btrfs-map-logical.c
+++ b/btrfs-map-logical.c
@@ -190,69 +190,6 @@ static int write_extent_content(struct btrfs_fs_info *fs_info, int out_fd,
 	return ret;
 }
 
-static struct extent_buffer * debug_read_block(struct btrfs_root *root,
-		u64 bytenr, u32 blocksize, u64 copy)
-{
-	int ret;
-	struct extent_buffer *eb;
-	u64 length;
-	struct btrfs_multi_bio *multi = NULL;
-	struct btrfs_device *device;
-	int num_copies;
-	int mirror_num = 1;
-
-	eb = btrfs_find_create_tree_block(root, bytenr, blocksize);
-	if (!eb)
-		return NULL;
-
-	length = blocksize;
-	while (1) {
-		ret = btrfs_map_block(&root->fs_info->mapping_tree, READ,
-				      eb->start, &length, &multi,
-				      mirror_num, NULL);
-		if (ret) {
-			fprintf(info_file,
-				"Error: fails to map mirror%d logical %llu: %s\n",
-				mirror_num, (unsigned long long)eb->start,
-				strerror(-ret));
-			free_extent_buffer(eb);
-			return NULL;
-		}
-		device = multi->stripes[0].dev;
-		eb->fd = device->fd;
-		device->total_ios++;
-		eb->dev_bytenr = multi->stripes[0].physical;
-
-		fprintf(info_file, "mirror %d logical %Lu physical %Lu "
-			"device %s\n", mirror_num, (unsigned long long)bytenr,
-			(unsigned long long)eb->dev_bytenr, device->name);
-		kfree(multi);
-
-		if (!copy || mirror_num == copy) {
-			ret = read_extent_from_disk(eb, 0, eb->len);
-			if (ret) {
-				fprintf(info_file,
-					"Error: failed to read extent: mirror %d logical %llu: %s\n",
-					mirror_num, (unsigned long long)eb->start,
-					strerror(-ret));
-				free_extent_buffer(eb);
-				eb = NULL;
-				break;
-			}
-		}
-
-		num_copies = btrfs_num_copies(&root->fs_info->mapping_tree,
-					      eb->start, eb->len);
-		if (num_copies == 1)
-			break;
-
-		mirror_num++;
-		if (mirror_num > num_copies)
-			break;
-	}
-	return eb;
-}
-
 static void print_usage(void) __attribute__((noreturn));
 static void print_usage(void)
 {
@@ -268,14 +205,16 @@ int main(int ac, char **av)
 {
 	struct cache_tree root_cache;
 	struct btrfs_root *root;
-	struct extent_buffer *eb;
 	char *dev;
 	char *output_file = NULL;
-	u64 logical = 0;
-	int ret = 0;
 	u64 copy = 0;
+	u64 logical = 0;
 	u64 bytes = 0;
-	int out_fd = 0;
+	u64 cur_logical = 0;
+	u64 cur_len = 0;
+	int out_fd = -1;
+	int found = 0;
+	int ret = 0;
 
 	while(1) {
 		int c;
@@ -346,30 +285,77 @@ int main(int ac, char **av)
 	}
 
 	if (bytes == 0)
-		bytes = root->sectorsize;
+		bytes = root->nodesize;
+	cur_logical = logical;
+	cur_len = bytes;
+
+	/* First find the nearest extent */
+	ret = map_one_extent(root->fs_info, &cur_logical, &cur_len, 0);
+	if (ret < 0) {
+		fprintf(stderr, "Failed to find extent at [%llu,%llu): %s\n",
+			cur_logical, cur_logical + cur_len, strerror(-ret));
+		goto out_close_fd;
+	}
+	/*
+	 * Normally, search backward should be OK, but for special case like
+	 * given logical is quite small where no extents are before it,
+	 * we need to search forward.
+	 */
+	if (ret > 0) {
+		ret = map_one_extent(root->fs_info, &cur_logical, &cur_len, 1);
+		if (ret < 0) {
+			fprintf(stderr,
+				"Failed to find extent at [%llu,%llu): %s\n",
+				cur_logical, cur_logical + cur_len,
+				strerror(-ret));
+			goto out_close_fd;
+		}
+		if (ret > 0) {
+			fprintf(stderr,
+				"Failed to find any extent at [%llu,%llu)\n",
+				cur_logical, cur_logical + cur_len);
+			goto out_close_fd;
+		}
+	}
 
-	bytes = (bytes + root->sectorsize - 1) / root->sectorsize;
-	bytes *= root->sectorsize;
+	while (cur_logical + cur_len >= logical && cur_logical < logical +
+	       bytes) {
+		u64 real_logical;
+		u64 real_len;
 
-	while (bytes > 0) {
-		eb = debug_read_block(root, logical, root->sectorsize, copy);
-		if (eb && output_file) {
-			ret = write(out_fd, eb->data, eb->len);
-			if (ret < 0 || ret != eb->len) {
-				ret = 1;
-				fprintf(stderr, "output file write failed\n");
+		found = 1;
+		ret = map_one_extent(root->fs_info, &cur_logical, &cur_len, 1);
+		if (ret < 0)
+			goto out_close_fd;
+		if (ret > 0)
+			break;
+		real_logical = max(logical, cur_logical);
+		real_len = min(logical + bytes, cur_logical + cur_len) -
+			   real_logical;
+
+		ret = print_mapping_info(root->fs_info, real_logical, real_len);
+		if (ret < 0)
+			goto out_close_fd;
+		if (output_file && out_fd != -1) {
+			ret = write_extent_content(root->fs_info, out_fd,
+					real_logical, real_len, copy);
+			if (ret < 0)
 				goto out_close_fd;
-			}
 		}
-		free_extent_buffer(eb);
-		logical += root->sectorsize;
-		bytes -= root->sectorsize;
+
+		cur_logical += cur_len;
 	}
 
+	if (!found) {
+		fprintf(stderr, "No extent found at range [%llu,%llu)\n",
+			logical, logical + bytes);
+	}
 out_close_fd:
 	if (output_file && out_fd != 1)
 		close(out_fd);
 close:
 	close_ctree(root);
+	if (ret < 0)
+		ret = 1;
 	return ret;
 }
-- 
2.4.3

Re: [PATCH 0/5] Rework/enhance btrfs-map-logical

[David Sterba]

On Wed, Jun 17, 2015 at 03:48:59PM +0800, Qu Wenruo wrote:
> Although btrfs-map-logical is mainly a tool for developers, but even as
> a developer, I feel quite frustrated about the bug I found:

Thanks, I'll queue it for 4.1.