[PATCH v2 00/10] Enhance btrfs-find-root and open_ctree() to provide better chance on damaged btrfs.

[PATCH v2 00/10] Enhance btrfs-find-root and open_ctree() to provide better chance on damaged btrfs.

[Qu Wenruo]

The patchset first enhance btrfs-find-root command and then use it to
enhance open_ctree to provide a better chance to open heavily damaged
btrfs.

Patch 1~9 are all enhancement/cleanup for btrfs-find-root in the following
concepts.
1) Reuse existing infrastructure.
Use existing or slightly modified infrastructure other than
copy-n-modify codes.

2) Enhanced root search logic
The old root search logic have many problems, like ignore newer root
with smaller level and use wrong generation/level for searching.

The new logic will keep a per-generation record to deal the tree search,
and use different level/generation for different tree.

3) Make the find-root infrastructure exported to other commands.
Allow other btrfs-progs components to use find-root infrastructure, e.g.
open_ctree can use it if all primary/backup tree roots are corrupted.

Patch 10 is enhancement for open_ctree to use find-root infrastructure.

To: David Sterba <dsterba@suse.cz>
I also created a pull request at github if it's OK for you.
https://github.com/kdave/btrfs-progs/pull/4

Qu Wenruo (10):
  btrfs-progs: Cleanup, use bitshift instead of immediate number in
    btrfs_open_ctree_flags.
  btrfs-progs: Add support to suppress tree block csum error output.
  btrfs-progs: Add new btrfs_open_ctree_flags CHUNK_ONLY.
  btrfs-progs: Add new find-root.[ch] infrastructure.
  btrfs-progs: Swith btrfs-find-root to use the new open_ctree flags.
  btrfs-progs: Add better search generation judgment for
    btrfs-find-root.
  btrfs-progs: Swith btrfs-find-root to use the find-root
    infrastructure.
  btrfs-progs: Cleanup unneeded btrfs-find-root codes.
  btrfs-progs: Add new option for btrfs-find-root to search through all
    the metadata extents.
  btrfs-progs: Allow open_ctree use backup tree root or search it
    automatically if primary tree root is corrupted.

 Documentation/btrfs-find-root.txt |   2 +
 Makefile                          |   2 +-
 btrfs-find-root.c                 | 379 +++++++++++++-------------------------
 ctree.h                           |   2 +
 disk-io.c                         | 128 +++++++++++--
 disk-io.h                         |  24 ++-
 find-root.c                       | 139 ++++++++++++++
 find-root.h                       |  84 +++++++++
 8 files changed, 486 insertions(+), 274 deletions(-)
 create mode 100644 find-root.c
 create mode 100644 find-root.h

-- 
2.2.2

[PATCH v2 01/10] btrfs-progs: Cleanup, use bitshift instead of immediate number in btrfs_open_ctree_flags.

[Qu Wenruo]

Change the immediate number in btrfs_open_ctree_flags to bit shift.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 disk-io.h | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

diff --git a/disk-io.h b/disk-io.h
index 4818109..e12870e 100644
--- a/disk-io.h
+++ b/disk-io.h
@@ -26,13 +26,13 @@
 #define BTRFS_SUPER_MIRROR_SHIFT 12
 
 enum btrfs_open_ctree_flags {
-	OPEN_CTREE_WRITES		= 1,
-	OPEN_CTREE_PARTIAL		= 2,
-	OPEN_CTREE_BACKUP_ROOT		= 4,
-	OPEN_CTREE_RECOVER_SUPER	= 8,
-	OPEN_CTREE_RESTORE		= 16,
-	OPEN_CTREE_NO_BLOCK_GROUPS	= 32,
-	OPEN_CTREE_EXCLUSIVE		= 64,
+	OPEN_CTREE_WRITES		= (1 << 0),
+	OPEN_CTREE_PARTIAL		= (1 << 1),
+	OPEN_CTREE_BACKUP_ROOT		= (1 << 2),
+	OPEN_CTREE_RECOVER_SUPER	= (1 << 3),
+	OPEN_CTREE_RESTORE		= (1 << 4),
+	OPEN_CTREE_NO_BLOCK_GROUPS	= (1 << 5),
+	OPEN_CTREE_EXCLUSIVE		= (1 << 6),
 };
 
 static inline u64 btrfs_sb_offset(int mirror)
-- 
2.2.2

[PATCH v2 02/10] btrfs-progs: Add support to suppress tree block csum error output.

[Qu Wenruo]

Add new open ctree flag OPEN_CTREE_SUPPRESS_ERROR to suppress tree block
csum error output.

Provides the basis for new btrfs-find-root and other enhancement on
btrfs offline tools output.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 ctree.h   |  2 ++
 disk-io.c | 18 +++++++++++++-----
 disk-io.h |  1 +
 3 files changed, 16 insertions(+), 5 deletions(-)

diff --git a/ctree.h b/ctree.h
index 7861940..805b64e 100644
--- a/ctree.h
+++ b/ctree.h
@@ -996,6 +996,7 @@ struct btrfs_fs_info {
 	unsigned int on_restoring:1;
 	unsigned int is_chunk_recover:1;
 	unsigned int quota_enabled:1;
+	unsigned int suppress_error:1;
 
 	int (*free_extent_hook)(struct btrfs_trans_handle *trans,
 				struct btrfs_root *root,
@@ -1004,6 +1005,7 @@ struct btrfs_fs_info {
 				int refs_to_drop);
 	struct cache_tree *fsck_extent_cache;
 	struct cache_tree *corrupt_blocks;
+
 };
 
 /*
diff --git a/disk-io.c b/disk-io.c
index b853f66..f08f612 100644
--- a/disk-io.c
+++ b/disk-io.c
@@ -42,7 +42,8 @@ static int check_tree_block(struct btrfs_root *root, struct extent_buffer *buf)
 	struct btrfs_fs_devices *fs_devices;
 	int ret = 1;
 
-	if (buf->start != btrfs_header_bytenr(buf)) {
+	if (buf->start != btrfs_header_bytenr(buf) &&
+	    !root->fs_info->suppress_error) {
 		printk("Check tree block failed, want=%Lu, have=%Lu\n",
 		       buf->start, btrfs_header_bytenr(buf));
 		return ret;
@@ -118,6 +119,8 @@ int csum_tree_block(struct btrfs_root *root, struct extent_buffer *buf,
 {
 	u16 csum_size =
 		btrfs_super_csum_size(root->fs_info->super_copy);
+	if (verify && root->fs_info->suppress_error)
+		return verify_tree_block_csum_silent(buf, csum_size);
 	return csum_tree_block_size(buf, csum_size, verify);
 }
 
@@ -282,10 +285,13 @@ struct extent_buffer *read_tree_block(struct btrfs_root *root, u64 bytenr,
 			return eb;
 		}
 		if (ignore) {
-			if (check_tree_block(root, eb))
-				printk("read block failed check_tree_block\n");
-			else
-				printk("Csum didn't match\n");
+			if (check_tree_block(root, eb)) {
+				if (!root->fs_info->suppress_error)
+					printk("read block failed check_tree_block\n");
+			} else {
+				if (!root->fs_info->suppress_error)
+					printk("Csum didn't match\n");
+			}
 			break;
 		}
 		num_copies = btrfs_num_copies(&root->fs_info->mapping_tree,
@@ -1112,6 +1118,8 @@ static struct btrfs_fs_info *__open_ctree_fd(int fp, const char *path,
 	}
 	if (flags & OPEN_CTREE_RESTORE)
 		fs_info->on_restoring = 1;
+	if (flags & OPEN_CTREE_SUPPRESS_ERROR)
+		fs_info->suppress_error = 1;
 
 	ret = btrfs_scan_fs_devices(fp, path, &fs_devices, sb_bytenr,
 				    (flags & OPEN_CTREE_RECOVER_SUPER));
diff --git a/disk-io.h b/disk-io.h
index e12870e..90ede6b 100644
--- a/disk-io.h
+++ b/disk-io.h
@@ -33,6 +33,7 @@ enum btrfs_open_ctree_flags {
 	OPEN_CTREE_RESTORE		= (1 << 4),
 	OPEN_CTREE_NO_BLOCK_GROUPS	= (1 << 5),
 	OPEN_CTREE_EXCLUSIVE		= (1 << 6),
+	OPEN_CTREE_SUPPRESS_ERROR	= (1 << 7), /* Suppress csum error */
 };
 
 static inline u64 btrfs_sb_offset(int mirror)
-- 
2.2.2

Re: [PATCH v2 02/10] btrfs-progs: Add support to suppress tree block csum error output.

[David Sterba]

On Mon, Jan 19, 2015 at 02:45:04PM +0800, Qu Wenruo wrote:
> Add new open ctree flag OPEN_CTREE_SUPPRESS_ERROR to suppress tree block
> csum error output.
> 
> @@ -996,6 +996,7 @@ struct btrfs_fs_info {
>  	unsigned int on_restoring:1;
>  	unsigned int is_chunk_recover:1;
>  	unsigned int quota_enabled:1;
> +	unsigned int suppress_error:1;

This is confusing, it suppresses only csum errors.

> --- a/disk-io.c
> +++ b/disk-io.c
> @@ -42,7 +42,8 @@ static int check_tree_block(struct btrfs_root *root, struct extent_buffer *buf)
>  	struct btrfs_fs_devices *fs_devices;
>  	int ret = 1;
>  
> -	if (buf->start != btrfs_header_bytenr(buf)) {
> +	if (buf->start != btrfs_header_bytenr(buf) &&
> +	    !root->fs_info->suppress_error) {

Though here it's used to skip block start mismatch error. But looking at
the rest of the code, it's better to put this check to the caller and
keep check_tree_block as is.

>  		printk("Check tree block failed, want=%Lu, have=%Lu\n",
>  		       buf->start, btrfs_header_bytenr(buf));
>  		return ret;
> @@ -118,6 +119,8 @@ int csum_tree_block(struct btrfs_root *root, struct extent_buffer *buf,
>  {
>  	u16 csum_size =
>  		btrfs_super_csum_size(root->fs_info->super_copy);
> +	if (verify && root->fs_info->suppress_error)
> +		return verify_tree_block_csum_silent(buf, csum_size);
>  	return csum_tree_block_size(buf, csum_size, verify);
>  }
>  
> @@ -282,10 +285,13 @@ struct extent_buffer *read_tree_block(struct btrfs_root *root, u64 bytenr,
>  			return eb;
>  		}
>  		if (ignore) {
> -			if (check_tree_block(root, eb))
> -				printk("read block failed check_tree_block\n");
> -			else
> -				printk("Csum didn't match\n");
> +			if (check_tree_block(root, eb)) {
> +				if (!root->fs_info->suppress_error)
> +					printk("read block failed check_tree_block\n");
> +			} else {
> +				if (!root->fs_info->suppress_error)
> +					printk("Csum didn't match\n");
> +			}
>  			break;
>  		}
>  		num_copies = btrfs_num_copies(&root->fs_info->mapping_tree,
> @@ -1112,6 +1118,8 @@ static struct btrfs_fs_info *__open_ctree_fd(int fp, const char *path,
>  	}
>  	if (flags & OPEN_CTREE_RESTORE)
>  		fs_info->on_restoring = 1;
> +	if (flags & OPEN_CTREE_SUPPRESS_ERROR)
> +		fs_info->suppress_error = 1;
>  
>  	ret = btrfs_scan_fs_devices(fp, path, &fs_devices, sb_bytenr,
>  				    (flags & OPEN_CTREE_RECOVER_SUPER));
> diff --git a/disk-io.h b/disk-io.h
> index e12870e..90ede6b 100644
> --- a/disk-io.h
> +++ b/disk-io.h
> @@ -33,6 +33,7 @@ enum btrfs_open_ctree_flags {
>  	OPEN_CTREE_RESTORE		= (1 << 4),
>  	OPEN_CTREE_NO_BLOCK_GROUPS	= (1 << 5),
>  	OPEN_CTREE_EXCLUSIVE		= (1 << 6),
> +	OPEN_CTREE_SUPPRESS_ERROR	= (1 << 7), /* Suppress csum error */
>  };
>  
>  static inline u64 btrfs_sb_offset(int mirror)

Re: [PATCH v2 02/10] btrfs-progs: Add support to suppress tree block csum error output.

[Qu Wenruo]

-------- Original Message --------
Subject: Re: [PATCH v2 02/10] btrfs-progs: Add support to suppress tree 
block csum error output.
From: David Sterba <dsterba@suse.cz>
To: Qu Wenruo <quwenruo@cn.fujitsu.com>
Date: 2015年01月29日 02:16
> On Mon, Jan 19, 2015 at 02:45:04PM +0800, Qu Wenruo wrote:
>> Add new open ctree flag OPEN_CTREE_SUPPRESS_ERROR to suppress tree block
>> csum error output.
>>
>> @@ -996,6 +996,7 @@ struct btrfs_fs_info {
>>   	unsigned int on_restoring:1;
>>   	unsigned int is_chunk_recover:1;
>>   	unsigned int quota_enabled:1;
>> +	unsigned int suppress_error:1;
> This is confusing, it suppresses only csum errors.
Indeed, what about suprress_csum_err?
>
>> --- a/disk-io.c
>> +++ b/disk-io.c
>> @@ -42,7 +42,8 @@ static int check_tree_block(struct btrfs_root *root, struct extent_buffer *buf)
>>   	struct btrfs_fs_devices *fs_devices;
>>   	int ret = 1;
>>   
>> -	if (buf->start != btrfs_header_bytenr(buf)) {
>> +	if (buf->start != btrfs_header_bytenr(buf) &&
>> +	    !root->fs_info->suppress_error) {
> Though here it's used to skip block start mismatch error. But looking at
> the rest of the code, it's better to put this check to the caller and
> keep check_tree_block as is.
Did you mean move the bytenr check out of check_tree_block() and caller 
do the bytenr check?
If so, I'll change it soon.

Thanks,
Qu
>
>>   		printk("Check tree block failed, want=%Lu, have=%Lu\n",
>>   		       buf->start, btrfs_header_bytenr(buf));
>>   		return ret;
>> @@ -118,6 +119,8 @@ int csum_tree_block(struct btrfs_root *root, struct extent_buffer *buf,
>>   {
>>   	u16 csum_size =
>>   		btrfs_super_csum_size(root->fs_info->super_copy);
>> +	if (verify && root->fs_info->suppress_error)
>> +		return verify_tree_block_csum_silent(buf, csum_size);
>>   	return csum_tree_block_size(buf, csum_size, verify);
>>   }
>>   
>> @@ -282,10 +285,13 @@ struct extent_buffer *read_tree_block(struct btrfs_root *root, u64 bytenr,
>>   			return eb;
>>   		}
>>   		if (ignore) {
>> -			if (check_tree_block(root, eb))
>> -				printk("read block failed check_tree_block\n");
>> -			else
>> -				printk("Csum didn't match\n");
>> +			if (check_tree_block(root, eb)) {
>> +				if (!root->fs_info->suppress_error)
>> +					printk("read block failed check_tree_block\n");
>> +			} else {
>> +				if (!root->fs_info->suppress_error)
>> +					printk("Csum didn't match\n");
>> +			}
>>   			break;
>>   		}
>>   		num_copies = btrfs_num_copies(&root->fs_info->mapping_tree,
>> @@ -1112,6 +1118,8 @@ static struct btrfs_fs_info *__open_ctree_fd(int fp, const char *path,
>>   	}
>>   	if (flags & OPEN_CTREE_RESTORE)
>>   		fs_info->on_restoring = 1;
>> +	if (flags & OPEN_CTREE_SUPPRESS_ERROR)
>> +		fs_info->suppress_error = 1;
>>   
>>   	ret = btrfs_scan_fs_devices(fp, path, &fs_devices, sb_bytenr,
>>   				    (flags & OPEN_CTREE_RECOVER_SUPER));
>> diff --git a/disk-io.h b/disk-io.h
>> index e12870e..90ede6b 100644
>> --- a/disk-io.h
>> +++ b/disk-io.h
>> @@ -33,6 +33,7 @@ enum btrfs_open_ctree_flags {
>>   	OPEN_CTREE_RESTORE		= (1 << 4),
>>   	OPEN_CTREE_NO_BLOCK_GROUPS	= (1 << 5),
>>   	OPEN_CTREE_EXCLUSIVE		= (1 << 6),
>> +	OPEN_CTREE_SUPPRESS_ERROR	= (1 << 7), /* Suppress csum error */
>>   };
>>   
>>   static inline u64 btrfs_sb_offset(int mirror)

[PATCH v2 03/10] btrfs-progs: Add new btrfs_open_ctree_flags CHUNK_ONLY.

[Qu Wenruo]

Add new flag CHUNK_ONLY and internal used only flag __RETURN_CHUNK.

CHUNK_ONLY will imply __RETURN_CHUNK, SUPPRESS_ERROR and PARTIAL, which
will allow the fs to be opened with only chunk tree OK.

This will improve the usability for btrfs-find-root.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 disk-io.c | 6 +++++-
 disk-io.h | 9 +++++++++
 2 files changed, 14 insertions(+), 1 deletion(-)

diff --git a/disk-io.c b/disk-io.c
index f08f612..71ca31f 100644
--- a/disk-io.c
+++ b/disk-io.c
@@ -1167,7 +1167,7 @@ static struct btrfs_fs_info *__open_ctree_fd(int fp, const char *path,
 			   BTRFS_UUID_SIZE);
 
 	ret = btrfs_setup_all_roots(fs_info, root_tree_bytenr, flags);
-	if (ret)
+	if (ret && !(flags & __RETURN_CHUNK_ROOT))
 		goto out_chunk;
 
 	return fs_info;
@@ -1212,6 +1212,8 @@ struct btrfs_root *open_ctree(const char *filename, u64 sb_bytenr,
 	info = open_ctree_fs_info(filename, sb_bytenr, 0, flags);
 	if (!info)
 		return NULL;
+	if (flags & __RETURN_CHUNK_ROOT)
+		return info->chunk_root;
 	return info->fs_root;
 }
 
@@ -1222,6 +1224,8 @@ struct btrfs_root *open_ctree_fd(int fp, const char *path, u64 sb_bytenr,
 	info = __open_ctree_fd(fp, path, sb_bytenr, 0, flags);
 	if (!info)
 		return NULL;
+	if (flags & __RETURN_CHUNK_ROOT)
+		return info->chunk_root;
 	return info->fs_root;
 }
 
diff --git a/disk-io.h b/disk-io.h
index 90ede6b..2d23cc3 100644
--- a/disk-io.h
+++ b/disk-io.h
@@ -34,6 +34,15 @@ enum btrfs_open_ctree_flags {
 	OPEN_CTREE_NO_BLOCK_GROUPS	= (1 << 5),
 	OPEN_CTREE_EXCLUSIVE		= (1 << 6),
 	OPEN_CTREE_SUPPRESS_ERROR	= (1 << 7), /* Suppress csum error */
+	__RETURN_CHUNK_ROOT		= (1 << 8), /* Return chunk root */
+	OPEN_CTREE_CHUNK_ONLY		= OPEN_CTREE_PARTIAL +
+					  OPEN_CTREE_SUPPRESS_ERROR +
+					  __RETURN_CHUNK_ROOT,
+	/*
+	 * TODO: cleanup: Split the open_ctree_flags into more indepent
+	 * tree bits.
+	 * Like split PARTIAL into SKIP_CSUM/SKIP_EXTENT
+	 */
 };
 
 static inline u64 btrfs_sb_offset(int mirror)
-- 
2.2.2

[PATCH v2 04/10] btrfs-progs: Add new find-root.[ch] infrastructure.

[Qu Wenruo]

Introduce new find-root.[ch] infrastructure which has better tree root
judgment and uses much less codes to do it.

The new infrastructure will only record tree blocks with highest level
among its generation, and do better judgment whether the found tree block
is the desired one(level + generation check other than the original
generation only check).

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 Makefile    |   2 +-
 find-root.c | 139 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 find-root.h |  84 ++++++++++++++++++++++++++++++++++++
 3 files changed, 224 insertions(+), 1 deletion(-)
 create mode 100644 find-root.c
 create mode 100644 find-root.h

diff --git a/Makefile b/Makefile
index 8b843bb..b0d0c3f 100644
--- a/Makefile
+++ b/Makefile
@@ -12,7 +12,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
+	  inode.o find-root.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/find-root.c b/find-root.c
new file mode 100644
index 0000000..a5ad777
--- /dev/null
+++ b/find-root.c
@@ -0,0 +1,139 @@
+/*
+ * Copyright (C) 2015 Fujitsu.  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.
+ */
+
+#define _XOPEN_SOURCE 500
+#define _GNU_SOURCE 1
+#include <stdio.h>
+#include <stdlib.h>
+#include "kerncompat.h"
+#include "ctree.h"
+#include "utils.h"
+#include "find-root.h"
+#include "volumes.h"
+#include "disk-io.h"
+#include "extent-cache.h"
+
+/* Return value is the same as btrfs_find_root_search(). */
+static int add_eb_to_result(struct extent_buffer *eb,
+			    struct cache_tree *result,
+			    u32 leafsize,
+			    struct btrfs_find_root_filter *filter,
+			    struct cache_extent **match)
+{
+	u64 generation = btrfs_header_generation(eb);
+	u64 level = btrfs_header_level(eb);
+	u64 owner = btrfs_header_owner(eb);
+	u64 start = eb->start;
+	struct cache_extent *cache;
+	struct btrfs_find_root_gen_cache *gen_cache = NULL;
+	int ret = 0;
+
+	if (owner != filter->objectid || level < filter->level ||
+	    generation < filter->generation)
+		return ret;
+
+	/* Get the generation cache or create one */
+	cache = search_cache_extent(result, generation);
+	if (!cache) {
+		gen_cache = malloc(sizeof(*gen_cache));
+		cache = &gen_cache->cache;
+		cache->start = generation;
+		cache->size = 1;
+		cache->objectid = 0;
+		gen_cache->highest_level = 0;
+		cache_tree_init(&gen_cache->eb_tree);
+
+		ret = insert_cache_extent(result, cache);
+		if (ret < 0)
+			return ret;
+	}
+	gen_cache = container_of(cache, struct btrfs_find_root_gen_cache,
+				 cache);
+
+	/* Higher level, clean tree and insert the new one */
+	if (level > gen_cache->highest_level) {
+		free_extent_cache_tree(&gen_cache->eb_tree);
+		gen_cache->highest_level = level;
+		/* Fall into the insert routine */
+	}
+
+	/* Same level, insert it into the eb_tree */
+	if (level == gen_cache->highest_level) {
+		ret = add_cache_extent(&gen_cache->eb_tree,
+				       start, leafsize);
+		if (ret < 0 && ret != -EEXIST)
+			return ret;
+		ret = 0;
+	}
+	if (generation == filter->match_gen &&
+	    level == filter->match_level &&
+	    !filter->search_all) {
+		ret = 1;
+		if (match)
+			*match = search_cache_extent(&gen_cache->eb_tree,
+						     start);
+	}
+	return ret;
+}
+
+/*
+ * Return 0 if iterating all the metadata extents.
+ * Return 1 if found root with given gen/level and set *match to it.
+ * Return <0 if error happens
+ */
+int btrfs_find_root_search(struct btrfs_root *chunk_root,
+			   struct btrfs_find_root_filter *filter,
+			   struct cache_tree *result,
+			   struct cache_extent **match)
+{
+	struct btrfs_fs_info *fs_info = chunk_root->fs_info;
+	struct extent_buffer *eb;
+	u64 metadata_offset = 0;
+	u64 metadata_size = 0;
+	u64 offset = 0;
+	u32 leafsize = chunk_root->leafsize;
+	int suppress_error = 0;
+	int ret = 0;
+
+	suppress_error = fs_info->suppress_error;
+	fs_info->suppress_error = 1;
+	while (1) {
+		ret = btrfs_next_metadata(&fs_info->mapping_tree,
+					  &metadata_offset, &metadata_size);
+		if (ret) {
+			if (ret == -ENOENT)
+				ret = 0;
+			break;
+		}
+		for (offset = metadata_offset;
+		     offset < metadata_offset + metadata_size;
+		     offset += chunk_root->leafsize) {
+			eb = read_tree_block(chunk_root, offset, leafsize, 0);
+			if (!eb || IS_ERR(eb))
+				continue;
+			ret = add_eb_to_result(eb, result, leafsize, filter,
+					       match);
+			free_extent_buffer(eb);
+			if (ret)
+				goto out;
+		}
+	}
+out:
+	fs_info->suppress_error = suppress_error;
+	return ret;
+}
diff --git a/find-root.h b/find-root.h
new file mode 100644
index 0000000..81f3786
--- /dev/null
+++ b/find-root.h
@@ -0,0 +1,84 @@
+/*
+ * Copyright (C) 2015 Fujitsu.  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_FIND_ROOT_H
+#define __BTRFS_FIND_ROOT_H
+#include "ctree.h"
+#include "list.h"
+#include "kerncompat.h"
+#include "extent-cache.h"
+/*
+ * Find-root will restore the search result in a 2-level trees.
+ * Search result is a cache_tree consisted of generation_cache.
+ * Each generation cache records the highest level of this generation
+ * and all the tree blocks with this generation.
+ *
+ * <result>
+ * cache_tree ----> generation_cache: gen:1 level: 2  eb_tree ----> eb1
+ *		|						|-> eb2
+ *		|						......
+ *		|-> generation_cache: gen:2 level: 3  eb_tree ---> eb3
+ *
+ * In the above example, generation 1's highest level is 2, but have multiple
+ * eb with same generation, so the root of generation 1 must be missing,
+ * possibly has already been overwritten.
+ * On the other hand, generation 2's highest level is 3 and we find only one
+ * eb for it, so it may be the root of generation 2.
+ */
+
+struct btrfs_find_root_gen_cache {
+	struct cache_extent cache;	/* cache->start is generation */
+	u64 highest_level;
+	struct cache_tree eb_tree;
+};
+
+struct btrfs_find_root_filter {
+	u64 objectid;	/* Only search tree with this objectid */
+	u64 generation; /* Only record tree block with higher or
+			   equal generation */
+	u8 level;	/* Only record tree block with higher or
+			   equal level */
+	u8 match_level;
+	u64 match_gen;
+	unsigned int search_all:1;
+	/*
+	 * If set search_all, even the tree block matches match_gen
+	 * and match_level and objectid, still continue searching
+	 * This *WILL* takes *TONS* of extra time.
+	 */
+};
+int btrfs_find_root_search(struct btrfs_root *chunk_root,
+			   struct btrfs_find_root_filter *filter,
+			   struct cache_tree *result,
+			   struct cache_extent **match);
+static inline void btrfs_find_root_free(struct cache_tree *result)
+{
+	struct btrfs_find_root_gen_cache *gen_cache;
+	struct cache_extent *cache;
+
+	cache = first_cache_extent(result);
+	while (cache) {
+		gen_cache = container_of(cache,
+				struct btrfs_find_root_gen_cache, cache);
+		free_extent_cache_tree(&gen_cache->eb_tree);
+		remove_cache_extent(result, cache);
+		free(gen_cache);
+		cache = first_cache_extent(result);
+	}
+}
+#endif
-- 
2.2.2

[PATCH v2 05/10] btrfs-progs: Switch btrfs-find-root to use the new open_ctree flags.

[Qu Wenruo]

Since in previous patches, we introduced the new open_ctree flag
OPEN_CTREE_CHUNK_ONLY, switch btrfs-find-root to use it instead of the
open_ctree_broken().

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 btrfs-find-root.c | 10 +---------
 1 file changed, 1 insertion(+), 9 deletions(-)

diff --git a/btrfs-find-root.c b/btrfs-find-root.c
index 6fa61cc..bc2b344 100644
--- a/btrfs-find-root.c
+++ b/btrfs-find-root.c
@@ -281,7 +281,6 @@ static int find_root(struct btrfs_root *root)
 int main(int argc, char **argv)
 {
 	struct btrfs_root *root;
-	int dev_fd;
 	int opt;
 	int ret;
 
@@ -309,14 +308,7 @@ int main(int argc, char **argv)
 		exit(1);
 	}
 
-	dev_fd = open(argv[optind], O_RDONLY);
-	if (dev_fd < 0) {
-		fprintf(stderr, "Failed to open device %s\n", argv[optind]);
-		exit(1);
-	}
-
-	root = open_ctree_broken(dev_fd, argv[optind]);
-	close(dev_fd);
+	root = open_ctree(argv[optind], 0, OPEN_CTREE_CHUNK_ONLY);
 
 	if (!root) {
 		fprintf(stderr, "Open ctree failed\n");
-- 
2.2.2

[PATCH v2 06/10] btrfs-progs: Add better search generation judgment for btrfs-find-root.

[Qu Wenruo]

Before the patch, btrfs-find-root will only consider it find a good root
if its generation matches generation in superblock and its level is
currently found highest level.

But that's not correct in 2 ways.
1) Root with decreased level
Since tree level can decrease, like subvolume/file deletion.
Which will make the new root have higher generation but lower level.

2) Root not updated in latest transaction.
If there is some root not updated in latest transaction, its generation
will be smaller than the one in superblock, and btrfs-find-root will not
find it.

This patch will use different generation for different tree to search,
solving the above problems.

Currently, it only supports generation/level in superblock. Using tree
root level/generation if possible will be introduced later.

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

diff --git a/btrfs-find-root.c b/btrfs-find-root.c
index bc2b344..45c48c2 100644
--- a/btrfs-find-root.c
+++ b/btrfs-find-root.c
@@ -278,6 +278,61 @@ static int find_root(struct btrfs_root *root)
 	return ret;
 }
 
+/*
+ * Get reliable generation and level for given root.
+ *
+ * We have two sources of gen/level: superblock and tree root.
+ * superblock include the following level:
+ *   Root, chunk, log
+ * and the following generations:
+ *   Root, chunk, uuid
+ * Other gen/leven can only be read from its btrfs_tree_root if possible.
+ *
+ * Currently we only believe things from superblock.
+ */
+static void get_root_gen_and_level(u64 objectid, struct btrfs_fs_info *fs_info,
+				   u64 *ret_gen, u8 *ret_level)
+{
+	struct btrfs_super_block *super = fs_info->super_copy;
+	u64 gen = (u64)-1;
+	u8 level = (u8)-1;
+
+	switch (objectid) {
+	case BTRFS_ROOT_TREE_OBJECTID:
+		level = btrfs_super_root_level(super);
+		gen = btrfs_super_generation(super);
+		break;
+	case BTRFS_CHUNK_TREE_OBJECTID:
+		level = btrfs_super_chunk_root_level(super);
+		gen = btrfs_super_chunk_root_generation(super);
+		printf("Search for chunk root is not supported yet\n");
+		break;
+	case BTRFS_TREE_LOG_OBJECTID:
+		level = btrfs_super_log_root_level(super);
+		gen = btrfs_super_log_root_transid(super);
+		break;
+	case BTRFS_UUID_TREE_OBJECTID:
+		gen = btrfs_super_uuid_tree_generation(super);
+		break;
+	}
+	if (gen != (u64)-1) {
+		printf("Superblock thinks the generation is %llu\n", gen);
+		if (ret_gen)
+			*ret_gen = gen;
+	} else {
+		printf("Superblock doesn't contain generation info for root %llu\n",
+		       objectid);
+	}
+	if (level != (u8)-1) {
+		printf("Superblock thinks the level is %u\n", level);
+		if (ret_level)
+			*ret_level = level;
+	} else {
+		printf("Superblock doesn't contain the level info for root %llu\n",
+		       objectid);
+	}
+}
+
 int main(int argc, char **argv)
 {
 	struct btrfs_root *root;
@@ -316,7 +371,8 @@ int main(int argc, char **argv)
 	}
 
 	if (search_generation == 0)
-		search_generation = btrfs_super_generation(root->fs_info->super_copy);
+		get_root_gen_and_level(search_objectid, root->fs_info,
+				       &search_generation, NULL);
 
 	csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
 	ret = find_root(root);
-- 
2.2.2

[PATCH v2 07/10] btrfs-progs: Swith btrfs-find-root to use the find-root infrastructure.

[Qu Wenruo]

Since the new find-root infrastructure is here with better root
judgement with less codes, just switch to it.

To switch to the new infrastructure, new print function is added and
output format is slighted changed.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 btrfs-find-root.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 71 insertions(+), 10 deletions(-)

diff --git a/btrfs-find-root.c b/btrfs-find-root.c
index 45c48c2..c451c7b 100644
--- a/btrfs-find-root.c
+++ b/btrfs-find-root.c
@@ -34,6 +34,8 @@
 #include "volumes.h"
 #include "utils.h"
 #include "crc32c.h"
+#include "extent-cache.h"
+#include "find-root.h"
 
 static u16 csum_size = 0;
 static u64 search_objectid = BTRFS_ROOT_TREE_OBJECTID;
@@ -333,22 +335,70 @@ static void get_root_gen_and_level(u64 objectid, struct btrfs_fs_info *fs_info,
 	}
 }
 
+static void print_one_result(struct cache_extent *tree_block,
+			     u8 level, u64 generation,
+			     struct btrfs_find_root_filter *filter)
+{
+	int unsure = 0;
+
+	if (filter->match_gen == (u64)-1 || filter->match_level == (u8)-1)
+		unsure = 1;
+	printf("Well block %llu(gen: %llu level: %u) seems good, ",
+	       tree_block->start, generation, level);
+	if (unsure)
+		printf("but we are unsure about the correct generation/level\n");
+	else
+		printf("but generation/level doesn't match, want gen: %llu level: %u\n",
+		       filter->match_gen, filter->match_level);
+}
+
+static void print_find_root_result(struct cache_tree *result,
+				   struct btrfs_find_root_filter *filter)
+{
+	struct btrfs_find_root_gen_cache *gen_cache;
+	struct cache_extent *cache;
+	struct cache_extent *tree_block;
+	u64 generation = 0;
+	u8 level = 0;
+
+	for (cache = last_cache_extent(result);
+	     cache; cache = prev_cache_extent(cache)) {
+		gen_cache = container_of(cache,
+				struct btrfs_find_root_gen_cache, cache);
+		level = gen_cache->highest_level;
+		generation = cache->start;
+		if (level == filter->match_level &&
+		    generation == filter->match_gen)
+			continue;
+		for (tree_block = last_cache_extent(&gen_cache->eb_tree);
+		     tree_block; tree_block = prev_cache_extent(tree_block))
+			print_one_result(tree_block, level, generation, filter);
+	}
+}
+
 int main(int argc, char **argv)
 {
 	struct btrfs_root *root;
+	struct btrfs_find_root_filter filter = {0};
+	struct cache_tree result;
+	struct cache_extent *found;
 	int opt;
 	int ret;
 
+	/* Default to search root tree */
+	filter.objectid = BTRFS_ROOT_TREE_OBJECTID;
+	filter.match_gen = (u64)-1;
+	filter.match_level = (u8)-1;
 	while ((opt = getopt(argc, argv, "l:o:g:")) != -1) {
 		switch(opt) {
 			case 'o':
-				search_objectid = arg_strtou64(optarg);
+				filter.objectid = arg_strtou64(optarg);
 				break;
 			case 'g':
-				search_generation = arg_strtou64(optarg);
+				filter.generation = arg_strtou64(optarg);
 				break;
 			case 'l':
-				search_level = arg_strtou64(optarg);
+				filter.level = arg_strtou64(optarg);
 				break;
 			default:
 				usage();
@@ -369,13 +419,24 @@ int main(int argc, char **argv)
 		fprintf(stderr, "Open ctree failed\n");
 		exit(1);
 	}
-
-	if (search_generation == 0)
-		get_root_gen_and_level(search_objectid, root->fs_info,
-				       &search_generation, NULL);
-
-	csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
-	ret = find_root(root);
+	cache_tree_init(&result);
+
+	get_root_gen_and_level(filter.objectid, root->fs_info,
+			       &filter.match_gen, &filter.match_level);
+	ret = btrfs_find_root_search(root, &filter, &result, &found);
+	if (ret < 0) {
+		fprintf(stderr, "Fail to search the tree root: %s\n",
+			strerror(-ret));
+		goto out;
+	}
+	if (ret > 0) {
+		printf("Found tree root at %llu gen %llu level %u\n",
+		       found->start, filter.match_gen, filter.match_level);
+		ret = 0;
+	}
+	print_find_root_result(&result, &filter);
+out:
+	btrfs_find_root_free(&result);
 	close_ctree(root);
 	return ret;
 }
-- 
2.2.2

[PATCH v2 08/10] btrfs-progs: Cleanup unneeded btrfs-find-root codes.

[Qu Wenruo]

Since we switched to new open_ctree flag and new find-root facility,
there is no need to keep the old find-root codes.

Clean it up.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 btrfs-find-root.c | 237 ------------------------------------------------------
 1 file changed, 237 deletions(-)

diff --git a/btrfs-find-root.c b/btrfs-find-root.c
index c451c7b..31fe0ae 100644
--- a/btrfs-find-root.c
+++ b/btrfs-find-root.c
@@ -37,249 +37,12 @@
 #include "extent-cache.h"
 #include "find-root.h"
 
-static u16 csum_size = 0;
-static u64 search_objectid = BTRFS_ROOT_TREE_OBJECTID;
-static u64 search_generation = 0;
-static unsigned long search_level = 0;
-
 static void usage(void)
 {
 	fprintf(stderr, "Usage: find-roots [-o search_objectid] "
 		"[ -g search_generation ] [ -l search_level ] <device>\n");
 }
 
-static int csum_block(void *buf, u32 len)
-{
-	char *result;
-	u32 crc = ~(u32)0;
-	int ret = 0;
-
-	result = malloc(csum_size * sizeof(char));
-	if (!result) {
-		fprintf(stderr, "No memory\n");
-		return 1;
-	}
-
-	len -= BTRFS_CSUM_SIZE;
-	crc = crc32c(crc, buf + BTRFS_CSUM_SIZE, len);
-	btrfs_csum_final(crc, result);
-
-	if (memcmp(buf, result, csum_size))
-		ret = 1;
-	free(result);
-	return ret;
-}
-
-static struct btrfs_root *open_ctree_broken(int fd, const char *device)
-{
-	struct btrfs_fs_info *fs_info;
-	struct btrfs_super_block *disk_super;
-	struct btrfs_fs_devices *fs_devices = NULL;
-	struct extent_buffer *eb;
-	int ret;
-
-	fs_info = btrfs_new_fs_info(0, BTRFS_SUPER_INFO_OFFSET);
-	if (!fs_info) {
-		fprintf(stderr, "Failed to allocate memory for fs_info\n");
-		return NULL;
-	}
-
-	ret = btrfs_scan_fs_devices(fd, device, &fs_devices, 0, 1);
-	if (ret)
-		goto out;
-
-	fs_info->fs_devices = fs_devices;
-
-	ret = btrfs_open_devices(fs_devices, O_RDONLY);
-	if (ret)
-		goto out_devices;
-
-	disk_super = fs_info->super_copy;
-	ret = btrfs_read_dev_super(fs_devices->latest_bdev,
-				   disk_super, fs_info->super_bytenr, 1);
-	if (ret) {
-		printk("No valid btrfs found\n");
-		goto out_devices;
-	}
-
-	memcpy(fs_info->fsid, &disk_super->fsid, BTRFS_FSID_SIZE);
-
-	ret = btrfs_check_fs_compatibility(disk_super, 0);
-	if (ret)
-		goto out_devices;
-
-	ret = btrfs_setup_chunk_tree_and_device_map(fs_info);
-	if (ret)
-		goto out_chunk;
-
-	eb = fs_info->chunk_root->node;
-	read_extent_buffer(eb, fs_info->chunk_tree_uuid,
-			   btrfs_header_chunk_tree_uuid(eb), BTRFS_UUID_SIZE);
-
-	return fs_info->chunk_root;
-out_chunk:
-	free_extent_buffer(fs_info->chunk_root->node);
-	btrfs_cleanup_all_caches(fs_info);
-out_devices:
-	btrfs_close_devices(fs_info->fs_devices);
-out:
-	btrfs_free_fs_info(fs_info);
-	return NULL;
-}
-
-static int search_iobuf(struct btrfs_root *root, void *iobuf,
-			size_t iobuf_size, off_t offset)
-{
-	u64 gen = search_generation;
-	u64 objectid = search_objectid;
-	u32 size = btrfs_super_nodesize(root->fs_info->super_copy);
-	u8 level = search_level;
-	size_t block_off = 0;
-
-	while (block_off < iobuf_size) {
-		void *block = iobuf + block_off;
-		struct btrfs_header *header = block;
-		u64 h_byte, h_level, h_gen, h_owner;
-
-//		printf("searching %Lu\n", offset + block_off);
-		h_byte = btrfs_stack_header_bytenr(header);
-		h_owner = btrfs_stack_header_owner(header);
-		h_level = header->level;
-		h_gen = btrfs_stack_header_generation(header);
-
-		if (h_owner != objectid)
-			goto next;
-		if (h_byte != (offset + block_off))
-			goto next;
-		if (h_level < level)
-			goto next;
-		level = h_level;
-		if (csum_block(block, size)) {
-			fprintf(stderr, "Well block %Lu seems good, "
-				"but the csum doesn't match\n",
-				h_byte);
-			goto next;
-		}
-		if (h_gen != gen) {
-			fprintf(stderr, "Well block %Lu seems great, "
-				"but generation doesn't match, "
-				"have=%Lu, want=%Lu level %Lu\n", h_byte,
-				h_gen, gen, h_level);
-			goto next;
-		}
-		printf("Found tree root at %Lu gen %Lu level %Lu\n", h_byte,
-		       h_gen, h_level);
-		return 0;
-next:
-		block_off += size;
-	}
-
-	return 1;
-}
-
-static int read_physical(struct btrfs_root *root, int fd, u64 offset,
-			 u64 bytenr, u64 len)
-{
-	char *iobuf = malloc(len);
-	ssize_t done;
-	size_t total_read = 0;
-	int ret = 1;
-
-	if (!iobuf) {
-		fprintf(stderr, "No memory\n");
-		return -1;
-	}
-
-	while (total_read < len) {
-		done = pread64(fd, iobuf + total_read, len - total_read,
-			       bytenr + total_read);
-		if (done < 0) {
-			fprintf(stderr, "Failed to read: %s\n",
-				strerror(errno));
-			ret = -1;
-			goto out;
-		}
-		total_read += done;
-	}
-
-	ret = search_iobuf(root, iobuf, total_read, offset);
-out:
-	free(iobuf);
-	return ret;
-}
-
-static int find_root(struct btrfs_root *root)
-{
-	struct btrfs_multi_bio *multi = NULL;
-	struct btrfs_device *device;
-	u64 metadata_offset = 0, metadata_size = 0;
-	off_t offset = 0;
-	off_t bytenr;
-	int fd;
-	int err;
-	int ret = 1;
-
-	printf("Super think's the tree root is at %Lu, chunk root %Lu\n",
-	       btrfs_super_root(root->fs_info->super_copy),
-	       btrfs_super_chunk_root(root->fs_info->super_copy));
-
-	err = btrfs_next_metadata(&root->fs_info->mapping_tree,
-				  &metadata_offset, &metadata_size);
-	if (err)
-		return ret;
-
-	offset = metadata_offset;
-	while (1) {
-		u64 map_length = 4096;
-		u64 type;
-
-		if (offset >
-		    btrfs_super_total_bytes(root->fs_info->super_copy)) {
-			printf("Went past the fs size, exiting");
-			break;
-		}
-		if (offset >= (metadata_offset + metadata_size)) {
-			err = btrfs_next_metadata(&root->fs_info->mapping_tree,
-						  &metadata_offset,
-						  &metadata_size);
-			if (err) {
-				printf("No more metdata to scan, exiting\n");
-				break;
-			}
-			offset = metadata_offset;
-		}
-		err = __btrfs_map_block(&root->fs_info->mapping_tree, READ,
-				      offset, &map_length, &type,
-				      &multi, 0, NULL);
-		if (err) {
-			offset += map_length;
-			continue;
-		}
-
-		if (!(type & BTRFS_BLOCK_GROUP_METADATA)) {
-			offset += map_length;
-			kfree(multi);
-			continue;
-		}
-
-		device = multi->stripes[0].dev;
-		fd = device->fd;
-		bytenr = multi->stripes[0].physical;
-		kfree(multi);
-
-		err = read_physical(root, fd, offset, bytenr, map_length);
-		if (!err) {
-			ret = 0;
-			break;
-		} else if (err < 0) {
-			ret = err;
-			break;
-		}
-		offset += map_length;
-	}
-	return ret;
-}
-
 /*
  * Get reliable generation and level for given root.
  *
-- 
2.2.2

[PATCH v2 09/10] btrfs-progs: Add new option for btrfs-find-root to search through all the metadata extents.

[Qu Wenruo]

Add option '-a' for btrfs-find-root to iterate all the metadata extents
even the root is already found.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 Documentation/btrfs-find-root.txt |  2 ++
 btrfs-find-root.c                 | 31 +++++++++++++++++--------------
 2 files changed, 19 insertions(+), 14 deletions(-)

diff --git a/Documentation/btrfs-find-root.txt b/Documentation/btrfs-find-root.txt
index c934b4c..e04cd3e 100644
--- a/Documentation/btrfs-find-root.txt
+++ b/Documentation/btrfs-find-root.txt
@@ -16,6 +16,8 @@ root tree's objectid, generation, level.
 
 OPTIONS
 -------
+-a::
+Search through all the metadata extents, even the root is already found.
 -g <generation>::
 Filter root tree by it's original transaction id, tree root's generation in default.
 -o <objectid>::
diff --git a/btrfs-find-root.c b/btrfs-find-root.c
index 31fe0ae..1da5513 100644
--- a/btrfs-find-root.c
+++ b/btrfs-find-root.c
@@ -39,7 +39,7 @@
 
 static void usage(void)
 {
-	fprintf(stderr, "Usage: find-roots [-o search_objectid] "
+	fprintf(stderr, "Usage: find-roots [-a] [-o search_objectid] "
 		"[ -g search_generation ] [ -l search_level ] <device>\n");
 }
 
@@ -152,20 +152,23 @@ int main(int argc, char **argv)
 	filter.objectid = BTRFS_ROOT_TREE_OBJECTID;
 	filter.match_gen = (u64)-1;
 	filter.match_level = (u8)-1;
-	while ((opt = getopt(argc, argv, "l:o:g:")) != -1) {
+	while ((opt = getopt(argc, argv, "al:o:g:")) != -1) {
 		switch(opt) {
-			case 'o':
-				filter.objectid = arg_strtou64(optarg);
-				break;
-			case 'g':
-				filter.generation = arg_strtou64(optarg);
-				break;
-			case 'l':
-				filter.level = arg_strtou64(optarg);
-				break;
-			default:
-				usage();
-				exit(1);
+		case 'a':
+			filter.search_all = 1;
+			break;
+		case 'o':
+			filter.objectid = arg_strtou64(optarg);
+			break;
+		case 'g':
+			filter.generation = arg_strtou64(optarg);
+			break;
+		case 'l':
+			filter.level = arg_strtou64(optarg);
+			break;
+		default:
+			usage();
+			exit(1);
 		}
 	}
 
-- 
2.2.2

[PATCH v2 10/10] btrfs-progs: Allow open_ctree use backup tree root or search it automatically if primary tree root is corrupted.

[Qu Wenruo]

Allow open_ctree to try its best to open tree root on damaged file system.

With this patch, open_ctree will follow the below priority to read tree
root, providing better chance to open damaged btrfs fs.
1) Using root bytenr in SB to read tree root
Normal routine if not specified to use backup roots or specified root
tree bytenr.

2) Using backup root if specified or 1) fails
Backup will be automatically used without user specification if
normal routine fails

3) Try to search possible tree root in all its metadata chunks
The last chance, searching through all the metadata space.
May takes a long time but still worth a try since above methods all
fails.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
Signed-off-by: David Sterba <dsterba@suse.cz>
---
 disk-io.c | 104 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 96 insertions(+), 8 deletions(-)

diff --git a/disk-io.c b/disk-io.c
index 71ca31f..6673a99 100644
--- a/disk-io.c
+++ b/disk-io.c
@@ -35,6 +35,7 @@
 #include "utils.h"
 #include "print-tree.h"
 #include "rbtree-utils.h"
+#include "find-root.h"
 
 static int check_tree_block(struct btrfs_root *root, struct extent_buffer *buf)
 {
@@ -894,9 +895,33 @@ int btrfs_setup_all_roots(struct btrfs_fs_info *fs_info, u64 root_tree_bytenr,
 	blocksize = btrfs_level_size(root, btrfs_super_root_level(sb));
 	generation = btrfs_super_generation(sb);
 
-	if (!root_tree_bytenr && !(flags & OPEN_CTREE_BACKUP_ROOT)) {
+	/*
+	 * If root bytenr is specified, use it and if fails, just return error,
+	 * not to try other method.
+	 */
+	if (root_tree_bytenr) {
+		root->node = read_tree_block(root, root_tree_bytenr,
+					     blocksize, generation);
+		if (!extent_buffer_uptodate(root->node)) {
+			fprintf(stderr, "Couldn't read tree root at %llu\n",
+				root_tree_bytenr);
+			return -EIO;
+		} else
+			goto extent_tree;
+	}
+	/* Normal root bytenr from super */
+	if (!(flags & OPEN_CTREE_BACKUP_ROOT)) {
 		root_tree_bytenr = btrfs_super_root(sb);
-	} else if (flags & OPEN_CTREE_BACKUP_ROOT) {
+		root->node = read_tree_block(root, root_tree_bytenr,
+					     blocksize, generation);
+		if (!extent_buffer_uptodate(root->node)) {
+			fprintf(stderr,
+				"Couldn't read tree root, try backup\n");
+			ret = -EAGAIN;
+		} else
+			goto extent_tree;
+	}
+	if ((flags & OPEN_CTREE_BACKUP_ROOT) || ret == -EAGAIN) {
 		struct btrfs_root_backup *backup;
 		int index = find_best_backup_root(sb);
 		if (index >= BTRFS_NUM_BACKUP_ROOTS) {
@@ -906,15 +931,78 @@ int btrfs_setup_all_roots(struct btrfs_fs_info *fs_info, u64 root_tree_bytenr,
 		backup = fs_info->super_copy->super_roots + index;
 		root_tree_bytenr = btrfs_backup_tree_root(backup);
 		generation = btrfs_backup_tree_root_gen(backup);
+		root->node = read_tree_block(root, root_tree_bytenr,
+					     blocksize, generation);
+		if (!extent_buffer_uptodate(root->node)) {
+			fprintf(stderr,
+				"Couldn't read backup tree root, try searching tree root\n");
+			ret = -EAGAIN;
+		} else {
+			ret = 0;
+			goto extent_tree;
+		}
 	}
 
-	root->node = read_tree_block(root, root_tree_bytenr, blocksize,
-				     generation);
-	if (!extent_buffer_uptodate(root->node)) {
-		fprintf(stderr, "Couldn't read tree root\n");
-		return -EIO;
-	}
+	/* Last chance, search the tree root */
+	if (ret == -EAGAIN) {
+		struct btrfs_find_root_filter filter = {0};
+		struct btrfs_find_root_gen_cache *gen_cache;
+		struct cache_tree result;
+		struct cache_extent *cache;
+		struct cache_extent *tree_block;
+
+		filter.objectid = BTRFS_ROOT_TREE_OBJECTID;
+		cache_tree_init(&result);
+
+		printf("Searching tree root, may take some time\n");
+		ret = btrfs_find_root_search(fs_info->chunk_root, &filter,
+					     &result, NULL);
+		if (ret < 0) {
+			fprintf(stderr, "Couldn't search tree root: %s\n",
+				strerror(-ret));
+			btrfs_find_root_free(&result);
+			return ret;
+		}
+		if (cache_tree_empty(&result)) {
+			fprintf(stderr, "Fail to find any tree root\n");
+			btrfs_find_root_free(&result);
+			return -ENOENT;
+		}
 
+		/* Find the newest root as tree root */
+		root_tree_bytenr = 0;
+		cache = last_cache_extent(&result);
+		while (cache) {
+			gen_cache = container_of(cache,
+					struct btrfs_find_root_gen_cache,
+					cache);
+			if (last_cache_extent(&gen_cache->eb_tree) !=
+			    first_cache_extent(&gen_cache->eb_tree)) {
+				cache = prev_cache_extent(cache);
+				continue;
+			}
+			tree_block = first_cache_extent(&gen_cache->eb_tree);
+			root_tree_bytenr = tree_block->start;
+			generation = gen_cache->cache.start;
+			break;
+		}
+		btrfs_find_root_free(&result);
+		if (!root_tree_bytenr) {
+			fprintf(stderr,
+				"Couldn't find any valid old tree root\n");
+			return -EINVAL;
+		} else
+			printf("Using tree root at %llu, gen: %llu\n",
+			       root_tree_bytenr, generation);
+		root->node = read_tree_block(root, root_tree_bytenr,
+					     blocksize, generation);
+		if (!extent_buffer_uptodate(root->node)) {
+			fprintf(stderr,
+				"Couldn't read the most possible tree root\n");
+			return -EIO;
+		}
+	}
+extent_tree:
 	ret = setup_root_or_create_block(fs_info, flags, fs_info->extent_root,
 					 BTRFS_EXTENT_TREE_OBJECTID, "extent");
 	if (ret)
-- 
2.2.2

Re: [PATCH v2 10/10] btrfs-progs: Allow open_ctree use backup tree root or search it automatically if primary tree root is corrupted.

[David Sterba]

On Mon, Jan 19, 2015 at 02:45:12PM +0800, Qu Wenruo wrote:
> Allow open_ctree to try its best to open tree root on damaged file system.
> 
> With this patch, open_ctree will follow the below priority to read tree
> root, providing better chance to open damaged btrfs fs.
> 1) Using root bytenr in SB to read tree root
> Normal routine if not specified to use backup roots or specified root
> tree bytenr.
> 
> 2) Using backup root if specified or 1) fails
> Backup will be automatically used without user specification if
> normal routine fails
> 
> 3) Try to search possible tree root in all its metadata chunks
> The last chance, searching through all the metadata space.
> May takes a long time but still worth a try since above methods all
> fails.

I don't see this patch merged and there are no folowups. IIRC I had
objections against the automatic behaviour but cannot find the
discussion. Can we merge at least some bit of that patch? It does more
than one thing so it would be better to split it.

Re: [PATCH v2 10/10] btrfs-progs: Allow open_ctree use backup tree root or search it automatically if primary tree root is corrupted.

[Qu Wenruo]

David Sterba wrote on 2015/07/27 17:04 +0200:
> On Mon, Jan 19, 2015 at 02:45:12PM +0800, Qu Wenruo wrote:
>> Allow open_ctree to try its best to open tree root on damaged file system.
>>
>> With this patch, open_ctree will follow the below priority to read tree
>> root, providing better chance to open damaged btrfs fs.
>> 1) Using root bytenr in SB to read tree root
>> Normal routine if not specified to use backup roots or specified root
>> tree bytenr.
>>
>> 2) Using backup root if specified or 1) fails
>> Backup will be automatically used without user specification if
>> normal routine fails
>>
>> 3) Try to search possible tree root in all its metadata chunks
>> The last chance, searching through all the metadata space.
>> May takes a long time but still worth a try since above methods all
>> fails.
>
> I don't see this patch merged and there are no folowups. IIRC I had
> objections against the automatic behaviour but cannot find the
> discussion. Can we merge at least some bit of that patch? It does more
> than one thing so it would be better to split it.
>

I forgot this patchset again.
I must admit that I have a bad memory...

Yes, you were against the automatic use of backup root or especially 
iteration all metadata space to find the latest tree root.

I'll try to add a new option like "--full-scan" to enable the automatic 
search of all metadata space.

But I'm afraid it may be a little late as I'm recently debugging other 
things like in-band deduplication.

Thanks
Qu

Re: [PATCH v2 10/10] btrfs-progs: Allow open_ctree use backup tree root or search it automatically if primary tree root is corrupted.

[David Sterba]

On Tue, Jul 28, 2015 at 08:34:50AM +0800, Qu Wenruo wrote:
> Yes, you were against the automatic use of backup root or especially 
> iteration all metadata space to find the latest tree root.
> 
> I'll try to add a new option like "--full-scan" to enable the automatic 
> search of all metadata space.
> 
> But I'm afraid it may be a little late as I'm recently debugging other 
> things like in-band deduplication.

This is not anything urgent, I was going through my git branches with
pending patches and found this.