Merge branch 'qu/find-root-v3-part1' into v3.19.x

8 files changed, 427 insertions, 268 deletions

diff --git a/Documentation/btrfs-find-root.txt b/Documentation/btrfs-find-root.txt
index c934b4cb..e04cd3e8 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/Makefile.in b/Makefile.in
index 3a603983..ad4c56f0 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -35,7 +35,7 @@ objects = ctree.o disk-io.o radix-tree.o extent-tree.o print-tree.o \
 	  extent-cache.o extent_io.o volumes.o utils.o repair.o \
 	  qgroup.o raid6.o free-space-cache.o list_sort.o props.o \
 	  ulist.o qgroup-verify.o backref.o string-table.o task-utils.o \
-	  inode.o file.o
+	  inode.o file.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/btrfs-find-root.c b/btrfs-find-root.c
index c6e6b82f..9e56c81d 100644
--- a/btrfs-find-root.c
+++ b/btrfs-find-root.c
@@ -31,271 +31,141 @@
 #include "volumes.h"
 #include "utils.h"
 #include "crc32c.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;
+#include "extent-cache.h"
+#include "find-root.h"
 
 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");
 }
 
-static int csum_block(void *buf, u32 len)
+/*
+ * 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)
 {
-	char *result;
-	u32 crc = ~(u32)0;
-	int ret = 0;
-
-	result = malloc(csum_size * sizeof(char));
-	if (!result) {
-		fprintf(stderr, "No memory\n");
-		return 1;
+	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;
 	}
-
-	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;
+	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);
 	}
-
-	ret = btrfs_scan_fs_devices(fd, device, &fs_devices, 0, 1, 0);
-	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;
+	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);
 	}
-
-	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)
+static void print_one_result(struct cache_extent *tree_block,
+			     u8 level, u64 generation,
+			     struct btrfs_find_root_filter *filter)
 {
-	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;
+	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 int find_root(struct btrfs_root *root)
+static void print_find_root_result(struct cache_tree *result,
+				   struct btrfs_find_root_filter *filter)
 {
-	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;
+	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;
-		}
-
-		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;
+		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);
 	}
-	return ret;
 }
 
 int main(int argc, char **argv)
 {
 	struct btrfs_root *root;
-	int dev_fd;
+	struct btrfs_find_root_filter filter = {0};
+	struct cache_tree result;
+	struct cache_extent *found;
 	int opt;
 	int ret;
 
-	while ((opt = getopt(argc, argv, "l:o:g:")) != -1) {
+	/* 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, "al:o:g:")) != -1) {
 		switch(opt) {
-			case 'o':
-				search_objectid = arg_strtou64(optarg);
-				break;
-			case 'g':
-				search_generation = arg_strtou64(optarg);
-				break;
-			case 'l':
-				search_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);
 		}
 	}
 
@@ -306,25 +176,29 @@ 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_ROOT_ONLY);
 	if (!root) {
 		fprintf(stderr, "Open ctree failed\n");
 		exit(1);
 	}
-
-	if (search_generation == 0)
-		search_generation = btrfs_super_generation(root->fs_info->super_copy);
-
-	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;
 }
diff --git a/ctree.h b/ctree.h
index f4275d9f..901c3400 100644
--- a/ctree.h
+++ b/ctree.h
@@ -998,6 +998,7 @@ struct btrfs_fs_info {
 	unsigned int on_restoring:1;
 	unsigned int is_chunk_recover:1;
 	unsigned int quota_enabled:1;
+	unsigned int suppress_check_block_errors:1;
 
 	int (*free_extent_hook)(struct btrfs_trans_handle *trans,
 				struct btrfs_root *root,
@@ -1006,6 +1007,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 0aec56e0..b709ff5b 100644
--- a/disk-io.c
+++ b/disk-io.c
@@ -22,6 +22,7 @@
 #include <sys/stat.h>
 #include <fcntl.h>
 #include <unistd.h>
+#include <uuid/uuid.h>
 #include "kerncompat.h"
 #include "radix-tree.h"
 #include "ctree.h"
@@ -33,17 +34,18 @@
 #include "print-tree.h"
 #include "rbtree-utils.h"
 
+/* specified errno for check_tree_block */
+#define BTRFS_BAD_BYTENR		(-1)
+#define BTRFS_BAD_FSID			(-2)
+
 static int check_tree_block(struct btrfs_root *root, struct extent_buffer *buf)
 {
 
 	struct btrfs_fs_devices *fs_devices;
-	int ret = 1;
+	int ret = BTRFS_BAD_FSID;
 
-	if (buf->start != btrfs_header_bytenr(buf)) {
-		printk("Check tree block failed, want=%Lu, have=%Lu\n",
-		       buf->start, btrfs_header_bytenr(buf));
-		return ret;
-	}
+	if (buf->start != btrfs_header_bytenr(buf))
+		return BTRFS_BAD_BYTENR;
 
 	fs_devices = root->fs_info->fs_devices;
 	while (fs_devices) {
@@ -58,6 +60,30 @@ static int check_tree_block(struct btrfs_root *root, struct extent_buffer *buf)
 	return ret;
 }
 
+static void print_tree_block_error(struct btrfs_root *root,
+				struct extent_buffer *eb,
+				int err)
+{
+	char fs_uuid[BTRFS_UUID_UNPARSED_SIZE] = {'\0'};
+	char found_uuid[BTRFS_UUID_UNPARSED_SIZE] = {'\0'};
+	u8 buf[BTRFS_UUID_SIZE];
+
+	switch (err) {
+	case BTRFS_BAD_FSID:
+		read_extent_buffer(eb, buf, btrfs_header_fsid(),
+				   BTRFS_UUID_SIZE);
+		uuid_unparse(buf, found_uuid);
+		uuid_unparse(root->fs_info->fsid, fs_uuid);
+		fprintf(stderr, "fsid mismatch, want=%s, have=%s\n",
+			fs_uuid, found_uuid);
+		break;
+	case BTRFS_BAD_BYTENR:
+		fprintf(stderr, "bytenr mismatch, want=%llu, have=%llu\n",
+			eb->start, btrfs_header_bytenr(eb));
+		break;
+	}
+}
+
 u32 btrfs_csum_data(struct btrfs_root *root, char *data, u32 seed, size_t len)
 {
 	return crc32c(seed, data, len);
@@ -115,6 +141,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_check_block_errors)
+		return verify_tree_block_csum_silent(buf, csum_size);
 	return csum_tree_block_size(buf, csum_size, verify);
 }
 
@@ -265,8 +293,8 @@ struct extent_buffer *read_tree_block(struct btrfs_root *root, u64 bytenr,
 
 	while (1) {
 		ret = read_whole_eb(root->fs_info, eb, mirror_num);
-		if (ret == 0 && check_tree_block(root, eb) == 0 &&
-		    csum_tree_block(root, eb, 1) == 0 &&
+		if (ret == 0 && csum_tree_block(root, eb, 1) == 0 &&
+		    check_tree_block(root, eb) == 0 &&
 		    verify_parent_transid(eb->tree, eb, parent_transid, ignore)
 		    == 0) {
 			if (eb->flags & EXTENT_BAD_TRANSID &&
@@ -279,10 +307,14 @@ 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_check_block_errors)
+					print_tree_block_error(root, eb,
+						check_tree_block(root, eb));
+			} else {
+				if (!root->fs_info->suppress_check_block_errors)
+					fprintf(stderr, "Csum didn't match\n");
+			}
 			ret = -EIO;
 			break;
 		}
@@ -343,8 +375,10 @@ static int write_tree_block(struct btrfs_trans_handle *trans,
 		     struct btrfs_root *root,
 		     struct extent_buffer *eb)
 {
-	if (check_tree_block(root, eb))
+	if (check_tree_block(root, eb)) {
+		print_tree_block_error(root, eb, check_tree_block(root, eb));
 		BUG();
+	}
 
 	if (!btrfs_buffer_uptodate(eb, trans->transid))
 		BUG();
@@ -1113,6 +1147,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_CHECK_BLOCK_ERRORS)
+		fs_info->suppress_check_block_errors = 1;
 
 	ret = btrfs_scan_fs_devices(fp, path, &fs_devices, sb_bytenr,
 				    (flags & OPEN_CTREE_RECOVER_SUPER),
@@ -1161,7 +1197,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 & __OPEN_CTREEE_RETURN_CHUNK_ROOT))
 		goto out_chunk;
 
 	return fs_info;
@@ -1206,6 +1242,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 & __OPEN_CTREEE_RETURN_CHUNK_ROOT)
+		return info->chunk_root;
 	return info->fs_root;
 }
 
@@ -1216,6 +1254,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 & __OPEN_CTREEE_RETURN_CHUNK_ROOT)
+		return info->chunk_root;
 	return info->fs_root;
 }
 
diff --git a/disk-io.h b/disk-io.h
index 53df8f06..7a2a597f 100644
--- a/disk-io.h
+++ b/disk-io.h
@@ -34,6 +34,21 @@ enum btrfs_open_ctree_flags {
 	OPEN_CTREE_NO_BLOCK_GROUPS	= (1 << 5),
 	OPEN_CTREE_EXCLUSIVE		= (1 << 6),
 	OPEN_CTREE_NO_DEVICES		= (1 << 7),
+	/*
+	 * Don't print error messages if bytenr or checksums do not match in
+	 * tree block headers. Turn on by OPEN_CTREE_SUPPRESS_ERROR
+	 */
+	OPEN_CTREE_SUPPRESS_CHECK_BLOCK_ERRORS	= (1 << 8),
+	/* Return chunk root */
+	__OPEN_CTREEE_RETURN_CHUNK_ROOT	= (1 << 9),
+	OPEN_CTREE_CHUNK_ROOT_ONLY	= OPEN_CTREE_PARTIAL +
+					  OPEN_CTREE_SUPPRESS_CHECK_BLOCK_ERRORS +
+					  __OPEN_CTREEE_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)
diff --git a/find-root.c b/find-root.c
new file mode 100644
index 00000000..1af37b54
--- /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.
+ */
+
+#include "kerncompat.h"
+
+#include <stdio.h>
+#include <stdlib.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));
+		BUG_ON(!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_errors = 0;
+	int ret = 0;
+
+	suppress_errors = fs_info->suppress_check_block_errors;
+	fs_info->suppress_check_block_errors = 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_check_block_errors = suppress_errors;
+	return ret;
+}
diff --git a/find-root.h b/find-root.h
new file mode 100644
index 00000000..1c67ebcc
--- /dev/null
+++ b/find-root.h
@@ -0,0 +1,87 @@
+/*
+ * 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 "kerncompat.h"
+
+#include "ctree.h"
+#include "list.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;
+	int search_all;
+	/*
+	 * If set search_all, even the tree block matches match_gen
+	 * and match_level and objectid, still continue searching
+	 * This *WILL* take *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