[RFC PATCH 00/22] Btrfs-convert rework part 1

[RFC PATCH 00/22] Btrfs-convert rework part 1

[Qu Wenruo]

Here comes the first RFC version of btrfs-convert rework.
Any test is welcomed, and it can already pass the convert test from
btrfs-progs. (Since the test doesn't test rollback function)

The new btrfs-convert has the following bugfix/feature:
1. True separate meta/data chunk
   The converted filesystem will has correct chunk layout, and all ext*
   data will be covered by data chunk and metadata will be covered by
   metadata chunk.
   Allowing converted filesystem to pass latest btrfs check.

2. Structurized make_btrfs_v2()
   Unlike old make_btrfs() which is a mess of hand written codes, new
   make_btrfs_v2() is all structurized and should be easy for later
   expansion.

But it still has something to do:
1) No rollback implement yet
   The implement should be quite easy, but I hope we can check the
   convert patches as soon as possible.

2) No cleanup yet
   I didn't clean up the duplicated codes and unneeded codes yet.

3) Ability to handle TB level filesystem.
   Current implement rely on the initial system chunk to contain all
   chunks until we inserted all data chunks.
   However the initial system chunk are only 32M, in simple calculation,
   it can only hold at most 400K chunks.
   If every chunk is in the smallest size (16M), it can only handle
   less than 6T size in its worst case.
   Better calculate the initial system chunk size according to the
   filesystem size

4) Ability to create DUP metadata chunk without using balance
   Now the data and metadata chunk are all in SINGLE profile.
   User needs to convert metadata to DUP if they want DUP metadata
   profile.

   This is a little hard, as we must do it at make_btrfs() time, where
   we don't have full btrfs facilities to modify the metadata tree.

   This may need another rework on functions like btrfs_search_slot() to
   support temporary btrfs image without btrfs_root structure.

The new btrfs-convert will work like the following:

1) Scan ext2 for all used space

2) Calculate the following tree maps:
   convert_data_chunks:
     Ranges must be covered by data chunks
     Maps are batched to avoid small chunk and avoid reserved ranges
     like the first 1MB of the device and superblock space.
   free_space:
     Ranges that later allocation can allocate from
     With reserved ranges wiped.

3) Reserved space for superblock and system/metadata chunks
   Use free_space above to reserve space

4) Make a temporary btrfs, using above super/system/metadata position
   This is done by the new make_btrfs_v2() function.

5) Open temporary btrfs

6) Insert all data chunks to cover all ext* data

7) Create ext2_save subvolume and image
   Unlike old implement, which did this later, we do this first, as this
   method can reduce the extent fragments, reducing extent tree size.

   And this also calculate all the csum if needed, making later inode
   copy free from calculating csum.

8) Handle reserved ranges
   Copy ext* data in reserved ranges into other places.
   Now the hole ext2_save subvolume and image is created.

9) Copy inodes
   Inode copy will use the ext2_save image as new logical <-> disk
   mapping, to handle reserved ranges.

And yes, these patchset is already huge enough, but considering the
cleanup patches are not here yet, the net line of changes should be
under zero.

Qu Wenruo (22):
  btrfs-progs: extent-cache: Add comments for search/lookup functions
  btrfs-progs: extent-tree: Add add_merge_cache_extent function
  btrfs-progs: Add new init/free function and member for mkfs_config
  btrfs-progs: convert: Read and build up used space tree
  btrfs-progs: utils: Introduce new function to remove reserved ranges
  btrfs-progs: utils: Introduce function to calculate the available
    space
  btrfs-progs: Reserve space for system/meta chunks and superblock
  btrfs-progs: Introduce function to setup temporary superblock
  btrfs-progs: Introduce function to setup temporary tree root
  btrfs-progs: Introduce function to setup temporary chunk root
  btrfs-progs: Introduce function to initialize device tree
  btrfs-progs: Introduce function to initialize fs tree
  btrfs-progs: Introduce function to initialize csum tree
  btrfs-progs: Introduce function to setup temporary extent tree
  btrfs-progs: Introduce function to create convert data chunks
  btrfs-progs: extent-tree: Introduce function to find the first overlap
    extent.
  btrfs-progs: extent-tree: Enhance btrfs_record_file_extent
  btrfs-progs: convert: Introduce new function to create ext2 image
  btrfs-progs: convert: Introduce function to migrate reserved ranges
  btrfs-progs: Enhance record_file_blocks to handle reserved ranges
  btrfs-progs: convert: Introduce init_btrfs_v2 function.
  btrfs-progs: Introduce do_convert_v2 function

 btrfs-convert.c |  787 +++++++++++++++++++++++++++++++++++++++++-
 ctree.c         |   24 ++
 ctree.h         |    3 +
 extent-cache.c  |   57 ++++
 extent-cache.h  |   39 +++
 extent-tree.c   |  217 +++++++++---
 mkfs.c          |    4 +-
 utils.c         | 1013 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 utils.h         |   45 +++
 volumes.c       |   46 ++-
 volumes.h       |    2 +-
 11 files changed, 2165 insertions(+), 72 deletions(-)

-- 
2.6.2

[RFC PATCH 01/22] btrfs-progs: extent-cache: Add comments for search/lookup functions

[Qu Wenruo]

There are quite a lot search/lookup functions with different behavior,
add comments for them, as it will take extra time to view source to
understand the behavior difference.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 extent-cache.h | 31 +++++++++++++++++++++++++++++++
 1 file changed, 31 insertions(+)

diff --git a/extent-cache.h b/extent-cache.h
index cb1f77c..1ce68ef 100644
--- a/extent-cache.h
+++ b/extent-cache.h
@@ -45,11 +45,31 @@ struct cache_extent *last_cache_extent(struct cache_tree *tree);
 struct cache_extent *prev_cache_extent(struct cache_extent *pe);
 struct cache_extent *next_cache_extent(struct cache_extent *pe);
 
+/*
+ * Find a cache_extent which covers start.
+ *
+ * If not found, return next cache_extent if possible.
+ */
 struct cache_extent *search_cache_extent(struct cache_tree *tree, u64 start);
+
+/*
+ * Find a cahce_extent which restrictly covers start.
+ *
+ * If not found, return NULL.
+ */
 struct cache_extent *lookup_cache_extent(struct cache_tree *tree,
 					 u64 start, u64 size);
 
+/*
+ * Add an non-overlap extent into cache tree
+ *
+ * If [start, start+size) overlap with existing one, it will return -EEXIST.
+ */
 int add_cache_extent(struct cache_tree *tree, u64 start, u64 size);
+
+/*
+ * Same with add_cache_extent, but with cache_extent strcut.
+ */
 int insert_cache_extent(struct cache_tree *tree, struct cache_extent *pe);
 void remove_cache_extent(struct cache_tree *tree, struct cache_extent *pe);
 
@@ -71,8 +91,19 @@ static void free_##name##_tree(struct cache_tree *tree)		\
 
 void free_extent_cache_tree(struct cache_tree *tree);
 
+/*
+ * Search a cache_extent with same objectid, and covers start.
+ *
+ * If not found, return next if possible.
+ */
 struct cache_extent *search_cache_extent2(struct cache_tree *tree,
 					  u64 objectid, u64 start);
+/*
+ * Search a cache_extent with same objectid, and covers the range
+ * [start, start + size)
+ *
+ * If not found, return next cache_extent if possible.
+ */
 struct cache_extent *lookup_cache_extent2(struct cache_tree *tree,
 					  u64 objectid, u64 start, u64 size);
 int add_cache_extent2(struct cache_tree *tree,
-- 
2.6.2

[RFC PATCH 02/22] btrfs-progs: extent-tree: Add add_merge_cache_extent function

[Qu Wenruo]

This add_merge_cache_extent() function will try to merge adjusted
cache_extent.

This is used for later btrfs-convert ext2 free space cache.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 extent-cache.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 extent-cache.h |  8 ++++++++
 2 files changed, 65 insertions(+)

diff --git a/extent-cache.c b/extent-cache.c
index d80aead..38bed8b 100644
--- a/extent-cache.c
+++ b/extent-cache.c
@@ -282,3 +282,60 @@ void free_extent_cache_tree(struct cache_tree *tree)
 {
 	cache_tree_free_extents(tree, free_extent_cache);
 }
+
+int add_merge_cache_extent(struct cache_tree *tree, u64 start, u64 size)
+{
+	struct cache_extent *cache;
+	struct cache_extent *next = NULL;
+	struct cache_extent *prev = NULL;
+	int next_merged = 0;
+	int prev_merged = 0;
+	int ret = 0;
+
+	if (cache_tree_empty(tree))
+		goto insert;
+
+	cache = search_cache_extent(tree, start);
+	if (!cache) {
+		/*
+		 * Either the tree is completely empty, or the no range after
+		 * start.
+		 * Either way, the last cache_extent should be prev.
+		 */
+		prev = last_cache_extent(tree);
+	} else if (start <= cache->start) {
+		next = cache;
+		prev = prev_cache_extent(cache);
+	} else {
+		prev = cache;
+		next = next_cache_extent(cache);
+	}
+
+	/*
+	 * Ensure the range to be inserted won't cover with existings
+	 * Or we will need extra loop to do merge
+	 */
+	BUG_ON(next && start + size > next->start);
+	BUG_ON(prev && prev->start + prev->size > start);
+
+	if (next && start + size == next->start) {
+		next_merged = 1;
+		next->size = next->start + next->size - start;
+		next->start = start;
+	}
+	if (prev && prev->start + prev->size == start) {
+		prev_merged = 1;
+		if (next_merged) {
+			next->size = next->start + next->size - prev->start;
+			next->start = prev->start;
+			remove_cache_extent(tree, prev);
+			free(prev);
+		} else {
+			prev->size = start + size - prev->start;
+		}
+	}
+insert:
+	if (!prev_merged && !next_merged)
+		ret = add_cache_extent(tree, start, size);
+	return ret;
+}
diff --git a/extent-cache.h b/extent-cache.h
index 1ce68ef..f031fbf 100644
--- a/extent-cache.h
+++ b/extent-cache.h
@@ -110,4 +110,12 @@ int add_cache_extent2(struct cache_tree *tree,
 		      u64 objectid, u64 start, u64 size);
 int insert_cache_extent2(struct cache_tree *tree, struct cache_extent *pe);
 
+/*
+ * Insert a cache_extent range [start, start + size).
+ *
+ * This function may merge with existing cache_extent.
+ * NOTE: caller must ensure the inserted range won't cover with any existing
+ * range.
+ */
+int add_merge_cache_extent(struct cache_tree *tree, u64 start, u64 size);
 #endif
-- 
2.6.2

[RFC PATCH 03/22] btrfs-progs: Add new init/free function and member for mkfs_config

[Qu Wenruo]

Add new members for mkfs_config:
1. super_bytenr
   For convert case to restore where super block is allocated.
   Has no use for normal mkfs case.

2. convert_used
   A cache tree to record which ranges are used in original filesystem.
   This will gives the guide for later convert implement to provide better
   system/meta chunk allocation, other than just allocating them into
   range covered by DATA chunk.

3. chunk_uuid
   Chunk tree uuid, used for later per tree root initialization.

Since convert_used is a cache_tree, it needs to be initialized and freed
properly, add new init/free function for it too.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 btrfs-convert.c |  5 +++++
 mkfs.c          |  2 ++
 utils.h         | 29 +++++++++++++++++++++++++++++
 3 files changed, 36 insertions(+)

diff --git a/btrfs-convert.c b/btrfs-convert.c
index 02e5cdb..f66affd 100644
--- a/btrfs-convert.c
+++ b/btrfs-convert.c
@@ -2322,6 +2322,9 @@ static int do_convert(const char *devname, int datacsum, int packing, int noxatt
 	}
 	if (btrfs_check_nodesize(nodesize, blocksize, features))
 		goto fail;
+
+	init_mkfs_config(&mkfs_cfg);
+
 	blocks_per_node = nodesize / blocksize;
 	ret = -blocks_per_node;
 	for (i = 0; i < 7; i++) {
@@ -2479,6 +2482,8 @@ static int do_convert(const char *devname, int datacsum, int packing, int noxatt
 	printf("conversion complete.\n");
 	return 0;
 fail:
+	free_mkfs_config(&mkfs_cfg);
+
 	if (fd != -1)
 		close(fd);
 	if (is_btrfs)
diff --git a/mkfs.c b/mkfs.c
index 5f1411f..306be51 100644
--- a/mkfs.c
+++ b/mkfs.c
@@ -1669,6 +1669,7 @@ int main(int ac, char **av)
 			"WARNING: metatdata has lower redundancy than data!\n\n");
 	}
 
+	init_mkfs_config(&mkfs_cfg);
 	mkfs_cfg.label = label;
 	mkfs_cfg.fs_uuid = fs_uuid;
 	memcpy(mkfs_cfg.blocks, blocks, sizeof(blocks));
@@ -1839,6 +1840,7 @@ raid_groups:
 	}
 
 out:
+	free_mkfs_config(&mkfs_cfg);
 	ret = close_ctree(root);
 	BUG_ON(ret);
 	btrfs_close_all_devices();
diff --git a/utils.h b/utils.h
index b625330..dff2633 100644
--- a/utils.h
+++ b/utils.h
@@ -109,14 +109,43 @@ void btrfs_parse_features_to_string(char *buf, u64 flags);
 struct btrfs_mkfs_config {
 	char *label;
 	char *fs_uuid;
+	char *chunk_uuid;
+
 	u64 blocks[8];
 	u64 num_bytes;
 	u32 nodesize;
 	u32 sectorsize;
 	u32 stripesize;
 	u64 features;
+
+	/*
+	 * Already used space in original filesystem before convert.
+	 * For normal mkfs case, it should be empty.
+	 */
+	struct cache_tree convert_used;
+
+	/*
+	 * Super block bytenr.
+	 * For normal mkfs case, it shouldn't be used as mkfs doesn't support
+	 * change super block bytenr anymore.
+	 *
+	 * For convert use, it restore the superblock bytenr from the temporary
+	 * btrfs fs.
+	 */
+	u64 super_bytenr;
 };
 
+static inline void init_mkfs_config(struct btrfs_mkfs_config *cfg)
+{
+	memset(cfg, 0, sizeof(*cfg));
+	cache_tree_init(&cfg->convert_used);
+}
+
+static inline void free_mkfs_config(struct btrfs_mkfs_config *cfg)
+{
+	free_extent_cache_tree(&cfg->convert_used);
+}
+
 int make_btrfs(int fd, struct btrfs_mkfs_config *cfg);
 int btrfs_make_root_dir(struct btrfs_trans_handle *trans,
 			struct btrfs_root *root, u64 objectid);
-- 
2.6.2

[RFC PATCH 04/22] btrfs-progs: convert: Read and build up used space tree

[Qu Wenruo]

Before we do real convert, we'd better read and build up used space
cache tree for later data/meta chunk layout calculation.

This patch will iterate all used blocks in ext2 filesystem and record it
into mkfs_cfg.used cache tree for later used.

This provides the basis for later btrfs-convert rework.

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

diff --git a/btrfs-convert.c b/btrfs-convert.c
index f66affd..3bee049 100644
--- a/btrfs-convert.c
+++ b/btrfs-convert.c
@@ -2286,6 +2286,77 @@ err:
 	return ret;
 }
 
+static int add_one_used_block(ext2_filsys fs, char *bitmap,
+			      unsigned long group_nr, struct cache_tree *used)
+{
+	unsigned long offset;
+	unsigned i;
+	int ret = 0;
+
+	offset = fs->super->s_first_data_block;
+	offset /= EXT2FS_CLUSTER_RATIO(fs);
+	offset += group_nr * fs->super->s_clusters_per_group;
+	for (i = 0; i < fs->super->s_clusters_per_group; i++) {
+		if (ext2fs_test_bit(i, bitmap)) {
+			u64 start;
+
+			start = (i + offset) * EXT2FS_CLUSTER_RATIO(fs);
+			start *= fs->blocksize;
+			ret = add_merge_cache_extent(used, start,
+						     fs->blocksize);
+			if (ret < 0)
+				break;
+		}
+	}
+	return ret;
+}
+
+/*
+ * This function will iterate through all the ext2 block groups to fill used
+ * space tree.
+ * Which will later be used to build data chunk layout to ensure all ext2 used
+ * data will be covered by data chunk.
+ */
+static int read_ext2_used_space(ext2_filsys fs, struct cache_tree *used_tree)
+{
+	blk64_t blk_itr = EXT2FS_B2C(fs, fs->super->s_first_data_block);
+	char *block_bitmap = NULL;
+	unsigned long i;
+	int block_nbytes;
+	int ret = 0;
+
+	block_nbytes = EXT2_CLUSTERS_PER_GROUP(fs->super) / 8;
+	ret = ext2fs_read_bitmaps(fs);
+	if (ret < 0)
+		return ret;
+	/* Shouldn't happen */
+	BUG_ON(!fs->block_map);
+
+	block_bitmap = malloc(block_nbytes);
+	if (!block_bitmap)
+		return -ENOMEM;
+
+	for (i = 0; i < fs->group_desc_count; i++) {
+		ret = ext2fs_get_block_bitmap_range2(fs->block_map, blk_itr,
+						block_nbytes * 8, block_bitmap);
+		if (ret) {
+			error("fail to get bitmap from ext2, %s",
+			      strerror(-ret));
+			break;
+		}
+		ret = add_one_used_block(fs, block_bitmap, i, used_tree);
+		if (ret < 0) {
+			error("fail to build used space tree, %s",
+			      strerror(-ret));
+			break;
+		}
+		blk_itr += fs->super->s_clusters_per_group;
+	}
+
+	free(block_bitmap);
+	return ret;
+}
+
 static int do_convert(const char *devname, int datacsum, int packing, int noxattr,
 		u32 nodesize, int copylabel, const char *fslabel, int progress,
 		u64 features)
@@ -2323,7 +2394,13 @@ static int do_convert(const char *devname, int datacsum, int packing, int noxatt
 	if (btrfs_check_nodesize(nodesize, blocksize, features))
 		goto fail;
 
+	/* Build the used space tree first */
 	init_mkfs_config(&mkfs_cfg);
+	ret = read_ext2_used_space(ext2_fs, &mkfs_cfg.convert_used);
+	if (ret < 0) {
+		error("fail to read ext2 block bitmap\n");
+		goto fail;
+	}
 
 	blocks_per_node = nodesize / blocksize;
 	ret = -blocks_per_node;
-- 
2.6.2

[RFC PATCH 05/22] btrfs-progs: utils: Introduce new function to remove reserved ranges

[Qu Wenruo]

Introduce functions to remove reserved ranges for later btrfs-convert
rework.

The reserved ranges includes:
1. [0,1M)
2. [btrfs_sb_offset(1), +BTRFS_STRIP_LEN)
3. [btrfs_sb_offset(2), +BTRFS_STRIP_LEN)

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

diff --git a/utils.c b/utils.c
index 60235d8..5ab5ede 100644
--- a/utils.c
+++ b/utils.c
@@ -177,6 +177,121 @@ int test_uuid_unique(char *fs_uuid)
 }
 
 /*
+ * Remove one reserve range from given cache tree
+ * if min_stripe_size is non-zero, it will ensure for split case,
+ * all its split cache extent is no smaller than @min_strip_size / 2.
+ *
+ */
+static int wipe_one_reserved_range(struct cache_tree *tree,
+				   u64 start, u64 len, u64 min_stripe_size,
+				   int ensure_size)
+{
+	struct cache_extent *cache;
+	int ret;
+
+	/* The logical here is simplified to handle special cases only */
+	BUG_ON(min_stripe_size < len * 2 ||
+	       min_stripe_size / 2 < BTRFS_STRIPE_LEN);
+
+	/* Also, wipe range should already be aligned */
+	BUG_ON(start != round_down(start, BTRFS_STRIPE_LEN) ||
+	       start + len != round_up(start + len, BTRFS_STRIPE_LEN));
+
+	min_stripe_size /= 2;
+
+	cache = lookup_cache_extent(tree, start, len);
+	if (!cache)
+		return 0;
+
+	if (start <= cache->start) {
+		/*
+		 *	|--------cache---------|
+		 * |-wipe-|
+		 */
+		BUG_ON(start + len <= cache->start);
+
+		/*
+		 * The wipe size is smaller than min_stripe_size / 2,
+		 * so the result length should still meet min_stripe_size
+		 * And no need to do alignment
+		 */
+		cache->size -= (start + len - cache->start);
+		if (cache->size == 0) {
+			remove_cache_extent(tree, cache);
+			free(cache);
+			return 0;
+		}
+
+		BUG_ON(ensure_size && cache->size < min_stripe_size);
+
+		cache->start = start + len;
+		return 0;
+	} else if (start > cache->start && start + len < cache->start +
+		   cache->size) {
+		/*
+		 * |-------cache-----|
+		 * 	|-wipe-|
+		 */
+		u64 old_len = cache->size;
+		u64 insert_start = start + len;
+		u64 insert_len;
+
+		cache->size = start - cache->start;
+		if (ensure_size)
+			cache->size = max(cache->size, min_stripe_size);
+		cache->start = start - cache->size;
+
+		/* And insert the new one */
+		insert_len = old_len - start - len;
+		if (ensure_size)
+			insert_len = max(insert_len, min_stripe_size);
+
+		ret = add_merge_cache_extent(tree, insert_start, insert_len);
+		return ret;
+	} else {
+		/*
+		 * |----cache-----|
+		 * 		|--wipe-|
+		 * Wipe len should be small enough and no need to expand the
+		 * remaining extent
+		 */
+		cache->size = start - cache->start;
+		BUG_ON(ensure_size && cache->size < min_stripe_size);
+		return 0;
+	}
+}
+
+/*
+ * Remove reserved ranges from given cache_tree
+ *
+ * It will remove the following ranges
+ * 1) 0~1M
+ * 2) 2nd superblock, +64K(make sure chunks are 64K aligned)
+ * 3) 3rd superblock, +64K
+ *
+ * @min_stripe must be given for safety check
+ * and if @ensure_size is given, it will ensure affected cache_extent will be
+ * larger than min_stripe_size
+ */
+static int wipe_reserved_ranges(struct cache_tree *tree, u64 min_stripe_size,
+				int ensure_size)
+{
+	int ret;
+
+	ret = wipe_one_reserved_range(tree, 0, 1024 * 1024, min_stripe_size, 
+				      ensure_size);
+	if (ret < 0)
+		return ret;
+	ret = wipe_one_reserved_range(tree, btrfs_sb_offset(1), BTRFS_STRIPE_LEN,
+				      min_stripe_size, ensure_size);
+	if (ret < 0)
+		return ret;
+	ret = wipe_one_reserved_range(tree, btrfs_sb_offset(2), BTRFS_STRIPE_LEN,
+				      min_stripe_size, ensure_size);
+	return ret;
+}
+
+/*
  * @fs_uuid - if NULL, generates a UUID, returns back the new filesystem UUID
  */
 int make_btrfs(int fd, struct btrfs_mkfs_config *cfg)
-- 
2.6.2

[RFC PATCH 06/22] btrfs-progs: utils: Introduce function to calculate the available space

[Qu Wenruo]

Introduce a new function, calculate_available_space() to get available
space for convert.

Unlike old implement, this function will do the new work:
1) batch used ext* data space.
   To ensure data chunks will recovery them all.
   And restore the result into mkfs_cfg->convert_data_chunks for later
   user.

2) avoid SB and reserved space
   Both batched data space or free space will not cover reserved space,
   like sb or the first 1M.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 utils.c | 75 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 utils.h | 12 +++++++++++
 2 files changed, 87 insertions(+)

diff --git a/utils.c b/utils.c
index 5ab5ede..42e333b 100644
--- a/utils.c
+++ b/utils.c
@@ -291,6 +291,81 @@ static int wipe_reserved_ranges(struct cache_tree *tree, u64 min_stripe_size,
 	return ret;
 }
 
+static int calculate_available_space(struct cache_tree *used,
+				     struct cache_tree *free,
+				     struct btrfs_mkfs_config *cfg)
+{
+	struct cache_extent *cache;
+	u64 cur_off = 0;
+	/* Twice minimal chunk size */
+	u64 min_stripe_size = 2 * 16 * 1024 * 1024;
+	int ret;
+
+	for (cache = first_cache_extent(used); cache;
+	     cache = next_cache_extent(cache)) {
+		u64 cur_len;
+
+		if (cache->start + cache->size < cur_off)
+			continue;
+		if (cache->start > cur_off + min_stripe_size)
+			cur_off = cache->start;
+		cur_len = max(cache->start + cache->size - cur_off,
+			      min_stripe_size);
+		ret = add_merge_cache_extent(&cfg->convert_data_chunks,
+					     cur_off, cur_len);
+		if (ret < 0)
+			goto out;
+		cur_off += cur_len;
+	}
+
+	/* remove reserved ranges and keep the size of chunks */
+	ret = wipe_reserved_ranges(&cfg->convert_data_chunks, min_stripe_size,
+				   1);
+	if (ret < 0)
+		goto out;
+
+	/*
+	 * Now calculate the free space cache tree
+	 * Always round up the start for insert, to avoid metadta extent cross
+	 * stripe boundary
+	 */
+	cur_off = 0;
+	for (cache = first_cache_extent(&cfg->convert_data_chunks); cache;
+	     cache = next_cache_extent(cache)) {
+		if (cache->start < cur_off)
+			continue;
+		if (cache->start > cur_off) {
+			u64 insert_start;
+			u64 len;
+
+			len = cache->start - round_up(cur_off,
+						      BTRFS_STRIPE_LEN);
+			insert_start = round_up(cur_off, BTRFS_STRIPE_LEN);
+
+			ret = add_merge_cache_extent(free, insert_start, len);
+			if (ret < 0)
+				goto out;
+		}
+		cur_off = cache->start + cache->size;
+	}
+	/* Don't forget the last range */
+	if (cfg->num_bytes > cur_off) {
+		u64 len = cfg->num_bytes - cur_off;
+		u64 insert_start;
+
+		insert_start = round_up(cur_off, BTRFS_STRIPE_LEN);
+
+		ret = add_merge_cache_extent(free, insert_start, len);
+		if (ret < 0)
+			goto out;
+	}
+
+	/* Remove reserved bytes */
+	ret = wipe_reserved_ranges(free, min_stripe_size, 0);
+out:
+	return ret;
+}
+
 /*
  * @fs_uuid - if NULL, generates a UUID, returns back the new filesystem UUID
  */
diff --git a/utils.h b/utils.h
index dff2633..6ac1ba8 100644
--- a/utils.h
+++ b/utils.h
@@ -31,6 +31,8 @@
 		(BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF		\
 		| BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA)
 
+#define BTRFS_CONVERT_META_GROUP_SIZE (32 * 1024 * 1024)
+
 /*
  * Avoid multi-device features (RAID56) and mixed block groups
  */
@@ -125,6 +127,14 @@ struct btrfs_mkfs_config {
 	struct cache_tree convert_used;
 
 	/*
+	 * Ranges that should be covered by data chunk
+	 * For convert use only.
+	 *
+	 * Optimized version of convert_used, without tiny chunks.
+	 */
+	struct cache_tree convert_data_chunks;
+
+	/*
 	 * Super block bytenr.
 	 * For normal mkfs case, it shouldn't be used as mkfs doesn't support
 	 * change super block bytenr anymore.
@@ -139,11 +149,13 @@ static inline void init_mkfs_config(struct btrfs_mkfs_config *cfg)
 {
 	memset(cfg, 0, sizeof(*cfg));
 	cache_tree_init(&cfg->convert_used);
+	cache_tree_init(&cfg->convert_data_chunks);
 }
 
 static inline void free_mkfs_config(struct btrfs_mkfs_config *cfg)
 {
 	free_extent_cache_tree(&cfg->convert_used);
+	free_extent_cache_tree(&cfg->convert_data_chunks);
 }
 
 int make_btrfs(int fd, struct btrfs_mkfs_config *cfg);
-- 
2.6.2

[RFC PATCH 07/22] btrfs-progs: Reserve space for system/meta chunks and superblock

[Qu Wenruo]

Now we have a free space cache tree, we can reserve space for system and
metadata chunks and super blocks.

With this patch, even for the temporary fs, metadata tree blocks will be
prevent from being allocated into possible data chunks.

This provides the basis for later btrfs-convert enhancement.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 utils.c | 85 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 utils.h |  2 ++
 2 files changed, 87 insertions(+)

diff --git a/utils.c b/utils.c
index 42e333b..5619b85 100644
--- a/utils.c
+++ b/utils.c
@@ -367,6 +367,91 @@ out:
 }
 
 /*
+ * Reserve space from free_tree.
+ * The algorithm is very simple, find the first cache_extent with enough space
+ * and allocate from its beginning.
+ */
+static int reserve_free_space(struct cache_tree *free_tree, u64 len,
+			      u64 *ret_start)
+{
+	struct cache_extent *cache;
+	int found = 0;
+
+	BUG_ON(!ret_start);
+	cache = first_cache_extent(free_tree);
+	while (cache) {
+		if (cache->size > len) {
+			found = 1;
+			*ret_start = cache->start;
+
+			cache->size -= len;
+			if (cache->size == 0) {
+				remove_cache_extent(free_tree, cache);
+				free(cache);
+			} else {
+				cache->start += len;
+			}
+			break;
+		}
+		cache = next_cache_extent(cache);
+	}
+	if (!found)
+		return -ENOSPC;
+	return 0;
+}
+
+/*
+ * Improved version of make_btrfs().
+ *
+ * This one will not use bad behaved cfg->blocks[] array to arrange tree
+ * roots.
+ * Instead, it will use cfg->convert_used to calculate a free space tree,
+ * and then allocate system and metadata chunk, then put tree roots into
+ * corresponding chunks.
+ */
+static int make_btrfs_v2(int fd, struct btrfs_mkfs_config *cfg)
+{
+	struct cache_tree *free_tree;
+	struct cache_tree *used_tree = &cfg->convert_used;
+	u64 sys_chunk_start;
+	u64 meta_chunk_start;
+	int ret;
+
+	/* Shouldn't happen */
+	BUG_ON(cache_tree_empty(used_tree));
+
+	free_tree = malloc(sizeof(*free_tree));
+	if (!free_tree)
+		return -ENOMEM;
+	cache_tree_init(free_tree);
+
+	/* generate free space cache tree for later chunk allocation */
+	ret = calculate_available_space(used_tree, free_tree, cfg);
+	if (ret < 0)
+		goto out;
+
+	/* reserve space for temporary superblock first */
+	ret = reserve_free_space(free_tree, BTRFS_SUPER_INFO_SIZE,
+				 &cfg->super_bytenr);
+	if (ret < 0)
+		goto out;
+
+	/* Then reserve system and metadata chunk space*/
+	ret = reserve_free_space(free_tree, BTRFS_MKFS_SYSTEM_GROUP_SIZE,
+				 &sys_chunk_start);
+	if (ret < 0)
+		goto out;
+	ret = reserve_free_space(free_tree, BTRFS_CONVERT_META_GROUP_SIZE,
+				 &meta_chunk_start);
+	if (ret < 0)
+		goto out;
+
+out:
+	free(free_tree);
+	return ret;
+}
+
+/*
  * @fs_uuid - if NULL, generates a UUID, returns back the new filesystem UUID
  */
 int make_btrfs(int fd, struct btrfs_mkfs_config *cfg)
diff --git a/utils.h b/utils.h
index 6ac1ba8..cec30dc 100644
--- a/utils.h
+++ b/utils.h
@@ -123,6 +123,8 @@ struct btrfs_mkfs_config {
 	/*
 	 * Already used space in original filesystem before convert.
 	 * For normal mkfs case, it should be empty.
+	 *
+	 * Raw ext* used bytes.
 	 */
 	struct cache_tree convert_used;
 
-- 
2.6.2

[RFC PATCH 08/22] btrfs-progs: Introduce function to setup temporary superblock

[Qu Wenruo]

Introduce a new function, setup_temp_super(), to setup temporary super
for make_btrfs_v2().

Unlike the old codes in make_btrfs(), it will also initialize
system_chunk_array before chunk tree allocation.

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

diff --git a/utils.c b/utils.c
index 5619b85..6c4da04 100644
--- a/utils.c
+++ b/utils.c
@@ -400,6 +400,98 @@ static int reserve_free_space(struct cache_tree *free_tree, u64 len,
 	return 0;
 }
 
+static inline int write_temp_super(int fd, struct btrfs_super_block *sb,
+				   u64 sb_bytenr)
+{
+	u32 crc = ~(u32)0;
+	int ret;
+
+	crc = btrfs_csum_data(NULL, (char *)sb + BTRFS_CSUM_SIZE, crc,
+			      BTRFS_SUPER_INFO_SIZE - BTRFS_CSUM_SIZE);
+	btrfs_csum_final(crc, (char *)&sb->csum[0]);
+	ret = pwrite(fd, sb, BTRFS_SUPER_INFO_SIZE, sb_bytenr);
+	if (ret < BTRFS_SUPER_INFO_SIZE)
+		ret = (ret < 0 ? -errno : - EIO);
+	else
+		ret = 0;
+	return ret;
+}
+
+/*
+ * Setup temporary superblock at cfg->super_bynter
+ * Needed info are extracted from cfg, and root_bytenr, chunk_bytenr
+ *
+ * For now sys chunk array will be empty and dev_item is empty
+ * too.
+ * They will be re-initialized at temp chunk tree setup.
+ */
+static int setup_temp_super(int fd, struct btrfs_mkfs_config *cfg,
+			    u64 root_bytenr, u64 chunk_bytenr)
+{
+	unsigned char chunk_uuid[BTRFS_UUID_SIZE];
+	char super_buf[BTRFS_SUPER_INFO_SIZE];
+	struct btrfs_super_block *super = (struct btrfs_super_block*)super_buf;
+	int ret;
+
+	/*
+	 * We rely on cfg->chunk_uuid and cfg->fs_uuid to pass uuid
+	 * for other functions.
+	 * Caller must allocation space for them
+	 */
+	BUG_ON(!cfg->chunk_uuid || !cfg->fs_uuid);
+	memset(super_buf, 0, BTRFS_SUPER_INFO_SIZE);
+	cfg->num_bytes = round_down(cfg->num_bytes, cfg->sectorsize);
+
+	if (cfg->fs_uuid && *cfg->fs_uuid) {
+		if (uuid_parse(cfg->fs_uuid, super->fsid) != 0) {
+			error("cound not parse UUID: %s", cfg->fs_uuid);
+			ret = -EINVAL;
+			goto out;
+		}
+		if (!test_uuid_unique(cfg->fs_uuid)) {
+			error("non-unique UUID: %s", cfg->fs_uuid);
+			ret = -EINVAL;
+			goto out;
+		}
+	} else {
+		uuid_generate(super->fsid);
+		uuid_unparse(super->fsid, cfg->fs_uuid);
+	}
+	uuid_generate(chunk_uuid);
+	uuid_unparse(chunk_uuid, cfg->chunk_uuid);
+
+	btrfs_set_super_bytenr(super, cfg->super_bytenr);
+	btrfs_set_super_num_devices(super, 1);
+	btrfs_set_super_magic(super, BTRFS_MAGIC);
+	btrfs_set_super_generation(super, 1);
+	btrfs_set_super_root(super, root_bytenr);
+	btrfs_set_super_chunk_root(super, chunk_bytenr);
+	btrfs_set_super_total_bytes(super, cfg->num_bytes);
+	/*
+	 * Temporary btrfs will only has 6 tree roots:
+	 * chunk tree, root tree, extent_tree, device tree, fs tree
+	 * and csum tree.
+	 */
+	btrfs_set_super_bytes_used(super, 6 * cfg->nodesize);
+	btrfs_set_super_sectorsize(super, cfg->sectorsize);
+	btrfs_set_super_leafsize(super, cfg->nodesize);
+	btrfs_set_super_nodesize(super, cfg->nodesize);
+	btrfs_set_super_stripesize(super, cfg->stripesize);
+	btrfs_set_super_csum_type(super, BTRFS_CSUM_TYPE_CRC32);
+	btrfs_set_super_chunk_root(super, chunk_bytenr);
+	btrfs_set_super_cache_generation(super, -1);
+	btrfs_set_super_incompat_flags(super, cfg->features);
+	if (cfg->label)
+		strncpy(super->label, cfg->label, BTRFS_LABEL_SIZE - 1);
+
+	/* Sys chunk array will be re-initialized at chunk tree init time */
+	super->sys_chunk_array_size = 0;
+
+	ret = write_temp_super(fd, super, cfg->super_bytenr);
+out:
+	return ret;
+}
+
 /*
  * Improved version of make_btrfs().
  *
@@ -415,6 +507,10 @@ static int make_btrfs_v2(int fd, struct btrfs_mkfs_config *cfg)
 	struct cache_tree *used_tree = &cfg->convert_used;
 	u64 sys_chunk_start;
 	u64 meta_chunk_start;
+	/* chunk tree bytenr, in system chunk */
+	u64 chunk_bytenr;
+	/* metadata trees bytenr, in metadata chunk */
+	u64 root_bytenr;
 	int ret;
 
 	/* Shouldn't happen */
@@ -446,6 +542,27 @@ static int make_btrfs_v2(int fd, struct btrfs_mkfs_config *cfg)
 	if (ret < 0)
 		goto out;
 
+	/*
+	 * Inside the allocate metadata chunk, its layout will be:
+	 *  | offset		| contents	|
+	 *  -------------------------------------
+	 *  | +0		| tree root	|
+	 *  | +nodesize		| extent root	|
+	 *  | +nodesize * 2	| device root	|
+	 *  | +nodesize * 3	| fs tree	|
+	 *  | +nodesize * 4	| csum tree	|
+	 *  -------------------------------------
+	 * Inside the allocated system chunk, its layout will be:
+	 *  | offset		| contents	|
+	 *  -------------------------------------
+	 *  | +0		| chunk root	|
+	 *  -------------------------------------
+	 */
+	chunk_bytenr = sys_chunk_start;
+	root_bytenr = meta_chunk_start;
+	ret = setup_temp_super(fd, cfg, root_bytenr, chunk_bytenr);
+	if (ret < 0)
+		goto out;
 out:
 	free(free_tree);
 	return ret;
-- 
2.6.2

[RFC PATCH 09/22] btrfs-progs: Introduce function to setup temporary tree root

[Qu Wenruo]

Introduce new function, setup_temp_tree_root(), to initialize temporary
tree root for make_btrfs_v2().

The new function will setup tree root at metadata chunk and ensure data
won't be written into metadata chunk.

Also, new make_btrfs_v2() will have a much better code structure than
old make_btrfs().

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

diff --git a/utils.c b/utils.c
index 6c4da04..ce4d93c 100644
--- a/utils.c
+++ b/utils.c
@@ -493,6 +493,136 @@ out:
 }
 
 /*
+ * Setup an extent buffer for tree block.
+ */
+static int setup_temp_extent_buffer(struct extent_buffer *buf,
+				    struct btrfs_mkfs_config *cfg,
+				    u64 bytenr, u64 owner)
+{
+	unsigned char fsid[BTRFS_FSID_SIZE];
+	unsigned char chunk_uuid[BTRFS_UUID_SIZE];
+	int ret;
+
+	/* We rely on cfg->fs_uuid and chunk_uuid to fsid and chunk uuid */
+	BUG_ON(!cfg->fs_uuid || !cfg->chunk_uuid);
+	ret = uuid_parse(cfg->fs_uuid, fsid);
+	if (ret)
+		return -EINVAL;
+	ret = uuid_parse(cfg->chunk_uuid, chunk_uuid);
+	if (ret)
+		return -EINVAL;
+
+	memset(buf->data, 0, cfg->nodesize);
+	buf->len = cfg->nodesize;
+	btrfs_set_header_bytenr(buf, bytenr);
+	btrfs_set_header_generation(buf, 1);
+	btrfs_set_header_backref_rev(buf, BTRFS_MIXED_BACKREF_REV);
+	btrfs_set_header_owner(buf, owner);
+	btrfs_set_header_flags(buf, BTRFS_HEADER_FLAG_WRITTEN);
+	write_extent_buffer(buf, chunk_uuid, btrfs_header_chunk_tree_uuid(buf),
+			    BTRFS_UUID_SIZE);
+	write_extent_buffer(buf, fsid, btrfs_header_fsid(), BTRFS_FSID_SIZE);
+	return 0;
+}
+
+static inline int write_temp_extent_buffer(int fd, struct extent_buffer *buf,
+					   u64 bytenr)
+{
+	int ret;
+
+	csum_tree_block_size(buf, BTRFS_CRC32_SIZE, 0);
+
+	/* Temporary extent buffer is always mapped 1:1 on disk */
+	ret = pwrite(fd, buf->data, buf->len, bytenr);
+	if (ret < buf->len)
+		ret = (ret < 0 ? ret : -EIO);
+	else
+		ret = 0;
+	return ret;
+}
+
+/*
+ * Insert a root item for temporary tree root
+ *
+ * Only used in make_btrfs_v2().
+ */
+static void insert_temp_root_item(struct extent_buffer *buf,
+				  struct btrfs_mkfs_config *cfg,
+				  int *slot, u32 *itemoff, u64 objectid,
+				  u64 bytenr)
+{
+	struct btrfs_root_item root_item;
+	struct btrfs_inode_item *inode_item;
+	struct btrfs_disk_key disk_key;
+
+	btrfs_set_header_nritems(buf, *slot + 1);
+	(*itemoff) -= sizeof(root_item);
+	memset(&root_item, 0, sizeof(root_item));
+	inode_item = &root_item.inode;
+	btrfs_set_stack_inode_generation(inode_item, 1);
+	btrfs_set_stack_inode_size(inode_item, 3);
+	btrfs_set_stack_inode_nlink(inode_item, 1);
+	btrfs_set_stack_inode_nbytes(inode_item, cfg->nodesize);
+	btrfs_set_stack_inode_mode(inode_item, S_IFDIR | 0755);
+	btrfs_set_root_refs(&root_item, 1);
+	btrfs_set_root_used(&root_item, cfg->nodesize);
+	btrfs_set_root_generation(&root_item, 1);
+	btrfs_set_root_bytenr(&root_item, bytenr);
+
+	memset(&disk_key, 0, sizeof(disk_key));
+	btrfs_set_disk_key_type(&disk_key, BTRFS_ROOT_ITEM_KEY);
+	btrfs_set_disk_key_objectid(&disk_key, objectid);
+	btrfs_set_disk_key_offset(&disk_key, 0);
+
+	btrfs_set_item_key(buf, &disk_key, *slot);
+	btrfs_set_item_offset(buf, btrfs_item_nr(*slot), *itemoff);
+	btrfs_set_item_size(buf, btrfs_item_nr(*slot), sizeof(root_item));
+	write_extent_buffer(buf, &root_item,
+			    btrfs_item_ptr_offset(buf, *slot),
+			    sizeof(root_item));
+	(*slot)++;
+}
+
+static int setup_temp_root_tree(int fd, struct btrfs_mkfs_config *cfg,
+				u64 root_bytenr, u64 extent_bytenr,
+				u64 dev_bytenr, u64 fs_bytenr, u64 csum_bytenr)
+{
+	struct extent_buffer *buf = NULL;
+	u32 itemoff = __BTRFS_LEAF_DATA_SIZE(cfg->nodesize);
+	int slot = 0;
+	int ret;
+
+	/*
+	 * Provided bytenr must in ascending order, or tree root will have a
+	 * bad key order.
+	 */
+	BUG_ON(!(root_bytenr < extent_bytenr && extent_bytenr < dev_bytenr &&
+		 dev_bytenr < fs_bytenr && fs_bytenr < csum_bytenr));
+	buf = malloc(sizeof(*buf) + cfg->nodesize);
+	if (!buf)
+		return -ENOMEM;
+
+	ret = setup_temp_extent_buffer(buf, cfg, root_bytenr,
+				       BTRFS_ROOT_TREE_OBJECTID);
+	if (ret < 0)
+		goto out;
+
+	insert_temp_root_item(buf, cfg, &slot, &itemoff,
+			      BTRFS_EXTENT_TREE_OBJECTID, extent_bytenr);
+	insert_temp_root_item(buf, cfg, &slot, &itemoff,
+			      BTRFS_DEV_TREE_OBJECTID, dev_bytenr);
+	insert_temp_root_item(buf, cfg, &slot, &itemoff,
+			      BTRFS_FS_TREE_OBJECTID, fs_bytenr);
+	insert_temp_root_item(buf, cfg, &slot, &itemoff,
+			      BTRFS_CSUM_TREE_OBJECTID, csum_bytenr);
+
+	ret = write_temp_extent_buffer(fd, buf, root_bytenr);
+out:
+	free(buf);
+	return ret;
+}
+
+/*
  * Improved version of make_btrfs().
  *
  * This one will not use bad behaved cfg->blocks[] array to arrange tree
@@ -511,6 +641,11 @@ static int make_btrfs_v2(int fd, struct btrfs_mkfs_config *cfg)
 	u64 chunk_bytenr;
 	/* metadata trees bytenr, in metadata chunk */
 	u64 root_bytenr;
+	u64 extent_bytenr;
+	u64 dev_bytenr;
+	u64 fs_bytenr;
+	u64 csum_bytenr;
+	/* Above bytenrs are just for better readablity */
 	int ret;
 
 	/* Shouldn't happen */
@@ -543,6 +678,8 @@ static int make_btrfs_v2(int fd, struct btrfs_mkfs_config *cfg)
 		goto out;
 
 	/*
+	 * Allocated meta/sys chunks will be mapped 1:1 with device offset.
+	 *
 	 * Inside the allocate metadata chunk, its layout will be:
 	 *  | offset		| contents	|
 	 *  -------------------------------------
@@ -560,9 +697,20 @@ static int make_btrfs_v2(int fd, struct btrfs_mkfs_config *cfg)
 	 */
 	chunk_bytenr = sys_chunk_start;
 	root_bytenr = meta_chunk_start;
+	extent_bytenr = meta_chunk_start + cfg->nodesize;
+	dev_bytenr = meta_chunk_start + cfg->nodesize * 2;
+	fs_bytenr = meta_chunk_start + cfg->nodesize * 3;
+	csum_bytenr = meta_chunk_start + cfg->nodesize * 4;
+
 	ret = setup_temp_super(fd, cfg, root_bytenr, chunk_bytenr);
 	if (ret < 0)
 		goto out;
+
+	ret = setup_temp_root_tree(fd, cfg, root_bytenr, extent_bytenr,
+				   dev_bytenr, fs_bytenr, csum_bytenr);
+	if (ret < 0)
+		goto out;
+
 out:
 	free(free_tree);
 	return ret;
-- 
2.6.2

[RFC PATCH 10/22] btrfs-progs: Introduce function to setup temporary chunk root

[Qu Wenruo]

Introduce new function, setup_temp_chunk_root(), to initialize temporary
chunk root for make_btrfs_v2().

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

diff --git a/utils.c b/utils.c
index ce4d93c..a91b70c 100644
--- a/utils.c
+++ b/utils.c
@@ -622,6 +622,171 @@ out:
 	return ret;
 }
 
+static int insert_temp_dev_item(int fd, struct extent_buffer *buf,
+				struct btrfs_mkfs_config *cfg,
+				int *slot, u32 *itemoff)
+{
+	struct btrfs_disk_key disk_key;
+	struct btrfs_dev_item *dev_item;
+	char super_buf[BTRFS_SUPER_INFO_SIZE];
+	unsigned char dev_uuid[BTRFS_UUID_SIZE];
+	unsigned char fsid[BTRFS_FSID_SIZE];
+	struct btrfs_super_block *super = (struct btrfs_super_block*)super_buf;
+	int ret;
+
+	ret = pread(fd, super_buf, BTRFS_SUPER_INFO_SIZE, cfg->super_bytenr);
+	if (ret < BTRFS_SUPER_INFO_SIZE) {
+		ret = (ret < 0 ? -errno : -EIO);
+		goto out;
+	}
+
+	btrfs_set_header_nritems(buf, *slot + 1);
+	(*itemoff) -= sizeof(*dev_item);
+	/* setup device item 1, 0 is for replace case */
+	btrfs_set_disk_key_type(&disk_key, BTRFS_DEV_ITEM_KEY);
+	btrfs_set_disk_key_objectid(&disk_key, BTRFS_DEV_ITEMS_OBJECTID);
+	btrfs_set_disk_key_offset(&disk_key, 1);
+	btrfs_set_item_key(buf, &disk_key, *slot);
+	btrfs_set_item_offset(buf, btrfs_item_nr(*slot), *itemoff);
+	btrfs_set_item_size(buf, btrfs_item_nr(*slot), sizeof(*dev_item));
+
+	dev_item = btrfs_item_ptr(buf, *slot, struct btrfs_dev_item);
+	/* Generate device uuid */
+	uuid_generate(dev_uuid);
+	write_extent_buffer(buf, dev_uuid, (unsigned long)btrfs_device_uuid(dev_item),
+			    BTRFS_UUID_SIZE);
+	uuid_parse(cfg->fs_uuid, fsid);
+	write_extent_buffer(buf, fsid, (unsigned long)btrfs_device_fsid(dev_item),
+			    BTRFS_FSID_SIZE);
+	btrfs_set_device_id(buf, dev_item, 1);
+	btrfs_set_device_generation(buf, dev_item, 0);
+	btrfs_set_device_total_bytes(buf, dev_item, cfg->num_bytes);
+	/*
+	 * The number must match the initial SYSTEM and META chunk size
+	 */
+	btrfs_set_device_bytes_used(buf, dev_item,
+			BTRFS_MKFS_SYSTEM_GROUP_SIZE +
+			BTRFS_CONVERT_META_GROUP_SIZE);
+	btrfs_set_device_io_align(buf, dev_item, cfg->sectorsize);
+	btrfs_set_device_io_width(buf, dev_item, cfg->sectorsize);
+	btrfs_set_device_sector_size(buf, dev_item, cfg->sectorsize);
+	btrfs_set_device_type(buf, dev_item, 0);
+
+	/* Super dev_item is not complete, copy the complete one to sb */
+	read_extent_buffer(buf, &super->dev_item, (unsigned long)dev_item,
+			   sizeof(*dev_item));
+	ret = write_temp_super(fd, super, cfg->super_bytenr);
+	(*slot)++;
+out:
+	return ret;
+}
+
+static int insert_temp_chunk_item(int fd, struct extent_buffer *buf,
+				  struct btrfs_mkfs_config *cfg,
+				  int *slot, u32 *itemoff, u64 start, u64 len,
+				  u64 type)
+{
+	struct btrfs_chunk *chunk;
+	struct btrfs_disk_key disk_key;
+	char super_buf[BTRFS_SUPER_INFO_SIZE];
+	struct btrfs_super_block *sb = (struct btrfs_super_block *)super_buf;
+	int ret = 0;
+
+	ret = pread(fd, super_buf, BTRFS_SUPER_INFO_SIZE,
+		    cfg->super_bytenr);
+	if (ret < BTRFS_SUPER_INFO_SIZE) {
+		ret = (ret < 0 ? ret : -EIO);
+		return ret;
+	}
+
+	btrfs_set_header_nritems(buf, *slot + 1);
+	(*itemoff) -= btrfs_chunk_item_size(1);
+	btrfs_set_disk_key_type(&disk_key, BTRFS_CHUNK_ITEM_KEY);
+	btrfs_set_disk_key_objectid(&disk_key, BTRFS_FIRST_CHUNK_TREE_OBJECTID);
+	btrfs_set_disk_key_offset(&disk_key, start);
+	btrfs_set_item_key(buf, &disk_key, *slot);
+	btrfs_set_item_offset(buf, btrfs_item_nr(*slot), *itemoff);
+	btrfs_set_item_size(buf, btrfs_item_nr(*slot),
+			    btrfs_chunk_item_size(1));
+
+	chunk = btrfs_item_ptr(buf, *slot, struct btrfs_chunk);
+	btrfs_set_chunk_length(buf, chunk, len);
+	btrfs_set_chunk_owner(buf, chunk, BTRFS_EXTENT_TREE_OBJECTID);
+	btrfs_set_chunk_stripe_len(buf, chunk, 64 * 1024);
+	btrfs_set_chunk_type(buf, chunk, type);
+	btrfs_set_chunk_io_align(buf, chunk, cfg->sectorsize);
+	btrfs_set_chunk_io_width(buf, chunk, cfg->sectorsize);
+	btrfs_set_chunk_sector_size(buf, chunk, cfg->sectorsize);
+	btrfs_set_chunk_num_stripes(buf, chunk, 1);
+	/* TODO: Support DUP profile for system chunk */
+	btrfs_set_stripe_devid_nr(buf, chunk, 0, 1);
+	/* We are doing 1:1 mapping, so start is its dev offset */
+	btrfs_set_stripe_offset_nr(buf, chunk, 0, start);
+	write_extent_buffer(buf, &sb->dev_item.uuid,
+			    (unsigned long)btrfs_stripe_dev_uuid_nr(chunk, 0),
+			    BTRFS_UUID_SIZE);
+	(*slot)++;
+
+	/*
+	 * If it's system chunk, also copy it to super block.
+	 */
+	if (type & BTRFS_BLOCK_GROUP_SYSTEM) {
+		char *cur;
+
+		cur = (char *)sb->sys_chunk_array + sb->sys_chunk_array_size;
+		memcpy(cur, &disk_key, sizeof(disk_key));
+		cur += sizeof(disk_key);
+		read_extent_buffer(buf, cur, (unsigned long int)chunk,
+				   btrfs_chunk_item_size(1));
+		sb->sys_chunk_array_size += btrfs_chunk_item_size(1) +
+					    sizeof(disk_key);
+
+		ret = write_temp_super(fd, sb, cfg->super_bytenr);
+	}
+	return ret;
+}
+
+static int setup_temp_chunk_tree(int fd, struct btrfs_mkfs_config *cfg,
+				 u64 sys_chunk_start, u64 meta_chunk_start,
+				 u64 chunk_bytenr)
+{
+	struct extent_buffer *buf = NULL;
+	u32 itemoff = __BTRFS_LEAF_DATA_SIZE(cfg->nodesize);
+	int slot = 0;
+	int ret;
+
+	/* Must ensure SYS chunk starts before META chunk */
+	BUG_ON(meta_chunk_start < sys_chunk_start);
+	buf = malloc(sizeof(*buf) + cfg->nodesize);
+	if (!buf)
+		return -ENOMEM;
+	ret = setup_temp_extent_buffer(buf, cfg, chunk_bytenr,
+				       BTRFS_CHUNK_TREE_OBJECTID);
+	if (ret < 0)
+		goto out;
+
+	ret = insert_temp_dev_item(fd, buf, cfg, &slot, &itemoff);
+	if (ret < 0)
+		goto out;
+	ret = insert_temp_chunk_item(fd, buf, cfg, &slot, &itemoff,
+				     sys_chunk_start,
+				     BTRFS_MKFS_SYSTEM_GROUP_SIZE,
+				     BTRFS_BLOCK_GROUP_SYSTEM);
+	if (ret < 0)
+		goto out;
+	ret = insert_temp_chunk_item(fd, buf, cfg, &slot, &itemoff,
+				     meta_chunk_start,
+				     BTRFS_CONVERT_META_GROUP_SIZE,
+				     BTRFS_BLOCK_GROUP_METADATA);
+	if (ret < 0)
+		goto out;
+	ret = write_temp_extent_buffer(fd, buf, chunk_bytenr);
+
+out:
+	free(buf);
+	return ret;
+}
+
 /*
  * Improved version of make_btrfs().
  *
@@ -710,6 +875,10 @@ static int make_btrfs_v2(int fd, struct btrfs_mkfs_config *cfg)
 				   dev_bytenr, fs_bytenr, csum_bytenr);
 	if (ret < 0)
 		goto out;
+	ret = setup_temp_chunk_tree(fd, cfg, sys_chunk_start, meta_chunk_start,
+				    chunk_bytenr);
+	if (ret < 0)
+		goto out;
 
 out:
 	free(free_tree);
-- 
2.6.2

[RFC PATCH 11/22] btrfs-progs: Introduce function to initialize device tree

[Qu Wenruo]

Introduce new function, setup_temp_device_tree(), to setup temporary
device tree for make_btrfs_v2().

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 utils.c | 56 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 55 insertions(+), 1 deletion(-)

diff --git a/utils.c b/utils.c
index a91b70c..3be484a 100644
--- a/utils.c
+++ b/utils.c
@@ -787,6 +787,59 @@ out:
 	return ret;
 }
 
+static void insert_temp_dev_extent(struct extent_buffer *buf,
+				   int *slot, u32 *itemoff, u64 start, u64 len)
+{
+	struct btrfs_dev_extent *dev_extent;
+	struct btrfs_disk_key disk_key;
+
+	btrfs_set_header_nritems(buf, *slot + 1);
+	(*itemoff) -= sizeof(*dev_extent);
+	btrfs_set_disk_key_type(&disk_key, BTRFS_DEV_EXTENT_KEY);
+	btrfs_set_disk_key_objectid(&disk_key, 1);
+	btrfs_set_disk_key_offset(&disk_key, start);
+	btrfs_set_item_key(buf, &disk_key, *slot);
+	btrfs_set_item_offset(buf, btrfs_item_nr(*slot), *itemoff);
+	btrfs_set_item_size(buf, btrfs_item_nr(*slot), sizeof(*dev_extent));
+
+	dev_extent = btrfs_item_ptr(buf, *slot, struct btrfs_dev_extent);
+	btrfs_set_dev_extent_chunk_objectid(buf, dev_extent,
+					    BTRFS_FIRST_CHUNK_TREE_OBJECTID);
+	btrfs_set_dev_extent_length(buf, dev_extent, len);
+	btrfs_set_dev_extent_chunk_offset(buf, dev_extent, start);
+	btrfs_set_dev_extent_chunk_tree(buf, dev_extent,
+					BTRFS_CHUNK_TREE_OBJECTID);
+	(*slot)++;
+}
+
+static int setup_temp_dev_tree(int fd, struct btrfs_mkfs_config *cfg,
+			       u64 sys_chunk_start, u64 meta_chunk_start,
+			       u64 dev_bytenr)
+{
+	struct extent_buffer *buf = NULL;
+	u32 itemoff = __BTRFS_LEAF_DATA_SIZE(cfg->nodesize);
+	int slot = 0;
+	int ret;
+
+	/* Must ensure SYS chunk starts before META chunk */
+	BUG_ON(meta_chunk_start < sys_chunk_start);
+	buf = malloc(sizeof(*buf) + cfg->nodesize);
+	if (!buf)
+		return -ENOMEM;
+	ret = setup_temp_extent_buffer(buf, cfg, dev_bytenr,
+				       BTRFS_DEV_TREE_OBJECTID);
+	if (ret < 0)
+		goto out;
+	insert_temp_dev_extent(buf, &slot, &itemoff, sys_chunk_start,
+			       BTRFS_MKFS_SYSTEM_GROUP_SIZE);
+	insert_temp_dev_extent(buf, &slot, &itemoff, meta_chunk_start,
+			       BTRFS_CONVERT_META_GROUP_SIZE);
+	ret = write_temp_extent_buffer(fd, buf, dev_bytenr);
+out:
+	free(buf);
+	return ret;
+}
+
 /*
  * Improved version of make_btrfs().
  *
@@ -879,7 +932,8 @@ static int make_btrfs_v2(int fd, struct btrfs_mkfs_config *cfg)
 				    chunk_bytenr);
 	if (ret < 0)
 		goto out;
-
+	ret = setup_temp_dev_tree(fd, cfg, sys_chunk_start, meta_chunk_start,
+				  dev_bytenr);
 out:
 	free(free_tree);
 	return ret;
-- 
2.6.2

[RFC PATCH 12/22] btrfs-progs: Introduce function to initialize fs tree

[Qu Wenruo]

Introudce new function, setup_temp_fs_tree(), to setup temporary fs tree
for make_btrfs_v2().

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

diff --git a/utils.c b/utils.c
index 3be484a..edd8ac1 100644
--- a/utils.c
+++ b/utils.c
@@ -840,6 +840,28 @@ out:
 	return ret;
 }
 
+static int setup_temp_fs_tree(int fd, struct btrfs_mkfs_config *cfg,
+			      u64 fs_bytenr)
+{
+	struct extent_buffer *buf = NULL;
+	int ret;
+
+	buf = malloc(sizeof(*buf) + cfg->nodesize);
+	if (!buf)
+		return -ENOMEM;
+	ret = setup_temp_extent_buffer(buf, cfg, fs_bytenr,
+				       BTRFS_FS_TREE_OBJECTID);
+	if (ret < 0)
+		goto out;
+	/*
+	 * Temporary fs tree is completely empty.
+	 */
+	ret = write_temp_extent_buffer(fd, buf, fs_bytenr);
+out:
+	free(buf);
+	return ret;
+}
+
 /*
  * Improved version of make_btrfs().
  *
@@ -934,6 +956,10 @@ static int make_btrfs_v2(int fd, struct btrfs_mkfs_config *cfg)
 		goto out;
 	ret = setup_temp_dev_tree(fd, cfg, sys_chunk_start, meta_chunk_start,
 				  dev_bytenr);
+	if (ret < 0)
+		goto out;
+	ret = setup_temp_fs_tree(fd, cfg, fs_bytenr);
+
 out:
 	free(free_tree);
 	return ret;
-- 
2.6.2

[RFC PATCH 13/22] btrfs-progs: Introduce function to initialize csum tree

[Qu Wenruo]

Introduce new function, setup_temp_csum_tree(), to setup temporary
csum tree for make_btrfs_v2().

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

diff --git a/utils.c b/utils.c
index edd8ac1..ee2a538 100644
--- a/utils.c
+++ b/utils.c
@@ -862,6 +862,28 @@ out:
 	return ret;
 }
 
+static int setup_temp_csum_tree(int fd, struct btrfs_mkfs_config *cfg,
+				u64 csum_bytenr)
+{
+	struct extent_buffer *buf = NULL;
+	int ret;
+
+	buf = malloc(sizeof(*buf) + cfg->nodesize);
+	if (!buf)
+		return -ENOMEM;
+	ret = setup_temp_extent_buffer(buf, cfg, csum_bytenr,
+				       BTRFS_CSUM_TREE_OBJECTID);
+	if (ret < 0)
+		goto out;
+	/*
+	 * Temporary csum tree is completely empty.
+	 */
+	ret = write_temp_extent_buffer(fd, buf, csum_bytenr);
+out:
+	free(buf);
+	return ret;
+}
+
 /*
  * Improved version of make_btrfs().
  *
@@ -959,6 +981,9 @@ static int make_btrfs_v2(int fd, struct btrfs_mkfs_config *cfg)
 	if (ret < 0)
 		goto out;
 	ret = setup_temp_fs_tree(fd, cfg, fs_bytenr);
+	if (ret < 0)
+		goto out;
+	ret = setup_temp_csum_tree(fd, cfg, csum_bytenr);
 
 out:
 	free(free_tree);
-- 
2.6.2

[RFC PATCH 14/22] btrfs-progs: Introduce function to setup temporary extent tree

[Qu Wenruo]

Introduce new function, setup_temporary_extent_tree() to build a
temporary extent tree for make_btrfs_v2().

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 utils.c | 198 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 197 insertions(+), 1 deletion(-)

diff --git a/utils.c b/utils.c
index ee2a538..f5fadb1 100644
--- a/utils.c
+++ b/utils.c
@@ -885,6 +885,194 @@ out:
 }
 
 /*
+ * Insert one temporary extent item.
+ *
+ * NOTE: if skinny_metadata is not enabled, this function must be called
+ * after all other trees are initialized.
+ * Or fs without skinny-metadata will be screwed up.
+ */
+static int insert_temp_extent_item(int fd, struct extent_buffer *buf,
+				   struct btrfs_mkfs_config *cfg,
+				   int *slot, u32 *itemoff, u64 bytenr,
+				   u64 ref_root)
+{
+	struct extent_buffer *tmp;
+	struct btrfs_extent_item *ei;
+	struct btrfs_extent_inline_ref *iref;
+	struct btrfs_disk_key disk_key;
+	struct btrfs_disk_key tree_info_key;
+	struct btrfs_tree_block_info *info;
+	int itemsize;
+	int skinny_metadata = cfg->features &
+			      BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA;
+	int ret;
+
+	if (skinny_metadata)
+		itemsize = sizeof(*ei) + sizeof(*iref);
+	else
+		itemsize = sizeof(*ei) + sizeof(*iref) +
+			   sizeof(struct btrfs_tree_block_info);
+ 
+	btrfs_set_header_nritems(buf, *slot + 1);
+	*(itemoff) -= itemsize;
+
+	if (skinny_metadata) {
+		btrfs_set_disk_key_type(&disk_key, BTRFS_METADATA_ITEM_KEY);
+		btrfs_set_disk_key_offset(&disk_key, 0);
+	} else {
+		btrfs_set_disk_key_type(&disk_key, BTRFS_EXTENT_ITEM_KEY);
+		btrfs_set_disk_key_offset(&disk_key, cfg->nodesize);
+	}
+	btrfs_set_disk_key_objectid(&disk_key, bytenr);
+
+	btrfs_set_item_key(buf, &disk_key, *slot);
+	btrfs_set_item_offset(buf, btrfs_item_nr(*slot), *itemoff);
+	btrfs_set_item_size(buf, btrfs_item_nr(*slot), itemsize);
+
+	ei = btrfs_item_ptr(buf, *slot, struct btrfs_extent_item);
+	btrfs_set_extent_refs(buf, ei, 1);
+	btrfs_set_extent_generation(buf, ei, 1);
+	btrfs_set_extent_flags(buf, ei, BTRFS_EXTENT_FLAG_TREE_BLOCK);
+
+	if (skinny_metadata) {
+		iref = (struct btrfs_extent_inline_ref *)(ei + 1);
+	} else {
+		info = (struct btrfs_tree_block_info *)(ei + 1);
+		iref = (struct btrfs_extent_inline_ref *)(info + 1);
+	}
+	btrfs_set_extent_inline_ref_type(buf, iref,
+					 BTRFS_TREE_BLOCK_REF_KEY);
+	btrfs_set_extent_inline_ref_offset(buf, iref, ref_root);
+
+	(*slot)++;
+	if (skinny_metadata)
+		return 0;
+
+	/*
+	 * Lastly, check the tree block key by read the tree block
+	 * Since we do 1:1 mapping for convert case, we can directly
+	 * read the bytenr from disk
+	 */
+	tmp = malloc(sizeof(*tmp) + cfg->nodesize);
+	if (!tmp)
+		return -ENOMEM;
+	ret = setup_temp_extent_buffer(tmp, cfg, bytenr, ref_root);
+	if (ret < 0)
+		goto out;
+	ret = pread(fd, tmp->data, cfg->nodesize, bytenr);
+	if (ret < cfg->nodesize) {
+		ret = (ret < 0 ? -errno : -EIO);
+		goto out;
+	}
+	if (btrfs_header_nritems(tmp) == 0) {
+		btrfs_set_disk_key_type(&tree_info_key, 0);
+		btrfs_set_disk_key_objectid(&tree_info_key, 0);
+		btrfs_set_disk_key_offset(&tree_info_key, 0);
+	} else {
+		btrfs_item_key(tmp, &tree_info_key, 0);
+	}
+	btrfs_set_tree_block_key(buf, info, &tree_info_key);
+
+out:
+	free(tmp);
+	return ret;
+}
+
+static void insert_temp_block_group(struct extent_buffer *buf,
+				   struct btrfs_mkfs_config *cfg,
+				   int *slot, u32 *itemoff,
+				   u64 bytenr, u64 len, u64 used, u64 flag)
+{
+	struct btrfs_block_group_item bgi;
+	struct btrfs_disk_key disk_key;
+
+	btrfs_set_header_nritems(buf, *slot + 1);
+	(*itemoff) -= sizeof(bgi);
+	btrfs_set_disk_key_type(&disk_key, BTRFS_BLOCK_GROUP_ITEM_KEY);
+	btrfs_set_disk_key_objectid(&disk_key, bytenr);
+	btrfs_set_disk_key_offset(&disk_key, len);
+	btrfs_set_item_key(buf, &disk_key, *slot);
+	btrfs_set_item_offset(buf, btrfs_item_nr(*slot), *itemoff);
+	btrfs_set_item_size(buf, btrfs_item_nr(*slot), sizeof(bgi));
+
+	btrfs_set_block_group_flags(&bgi, flag);
+	btrfs_set_block_group_used(&bgi, used);
+	btrfs_set_block_group_chunk_objectid(&bgi,
+			BTRFS_FIRST_CHUNK_TREE_OBJECTID);
+	write_extent_buffer(buf, &bgi, btrfs_item_ptr_offset(buf, *slot),
+			    sizeof(bgi));
+	(*slot)++;
+}
+
+static int setup_temp_extent_tree(int fd, struct btrfs_mkfs_config *cfg,
+				  u64 chunk_bytenr, u64 root_bytenr,
+				  u64 extent_bytenr, u64 dev_bytenr,
+				  u64 fs_bytenr, u64 csum_bytenr)
+{
+	struct extent_buffer *buf = NULL;
+	u32 itemoff = __BTRFS_LEAF_DATA_SIZE(cfg->nodesize);
+	int slot = 0;
+	int ret;
+
+	/*
+	 * We must ensure provided bytenr are in ascending order,
+	 * or extent tree key order will be broken.
+	 */
+	BUG_ON(!(chunk_bytenr < root_bytenr && root_bytenr < extent_bytenr &&
+		 extent_bytenr < dev_bytenr && dev_bytenr < fs_bytenr &&
+		 fs_bytenr < csum_bytenr));
+	buf = malloc(sizeof(*buf) + cfg->nodesize);
+	if (!buf)
+		return -ENOMEM;
+
+	ret = setup_temp_extent_buffer(buf, cfg, extent_bytenr,
+				       BTRFS_EXTENT_TREE_OBJECTID);
+	if (ret < 0)
+		goto out;
+
+	ret = insert_temp_extent_item(fd, buf, cfg, &slot, &itemoff,
+			chunk_bytenr, BTRFS_CHUNK_TREE_OBJECTID);
+	if (ret < 0)
+		goto out;
+
+	insert_temp_block_group(buf, cfg, &slot, &itemoff, chunk_bytenr,
+			BTRFS_MKFS_SYSTEM_GROUP_SIZE, cfg->nodesize,
+			BTRFS_BLOCK_GROUP_SYSTEM);
+
+	ret = insert_temp_extent_item(fd, buf, cfg, &slot, &itemoff,
+			root_bytenr, BTRFS_ROOT_TREE_OBJECTID);
+	if (ret < 0)
+		goto out;
+
+	/* 5 tree block used, root, extent, dev, fs and csum*/
+	insert_temp_block_group(buf, cfg, &slot, &itemoff, root_bytenr,
+			BTRFS_CONVERT_META_GROUP_SIZE, cfg->nodesize * 5,
+			BTRFS_BLOCK_GROUP_METADATA);
+
+	ret = insert_temp_extent_item(fd, buf, cfg, &slot, &itemoff,
+			extent_bytenr, BTRFS_EXTENT_TREE_OBJECTID);
+	if (ret < 0)
+		goto out;
+	ret = insert_temp_extent_item(fd, buf, cfg, &slot, &itemoff,
+			dev_bytenr, BTRFS_DEV_TREE_OBJECTID);
+	if (ret < 0)
+		goto out;
+	ret = insert_temp_extent_item(fd, buf, cfg, &slot, &itemoff,
+			fs_bytenr, BTRFS_FS_TREE_OBJECTID);
+	if (ret < 0)
+		goto out;
+	ret = insert_temp_extent_item(fd, buf, cfg, &slot, &itemoff,
+			csum_bytenr, BTRFS_CSUM_TREE_OBJECTID);
+	if (ret < 0)
+		goto out;
+
+	ret = write_temp_extent_buffer(fd, buf, extent_bytenr);
+out:
+	free(buf);
+	return ret;
+}
+
+/*
  * Improved version of make_btrfs().
  *
  * This one will not use bad behaved cfg->blocks[] array to arrange tree
@@ -984,7 +1172,15 @@ static int make_btrfs_v2(int fd, struct btrfs_mkfs_config *cfg)
 	if (ret < 0)
 		goto out;
 	ret = setup_temp_csum_tree(fd, cfg, csum_bytenr);
-
+	if (ret < 0)
+		goto out;
+	/*
+	 * Setup extent tree lastly, since it may need to read tree block key
+	 * for non-skinny metadata case.
+	 */
+	ret = setup_temp_extent_tree(fd, cfg, chunk_bytenr, root_bytenr,
+				     extent_bytenr, dev_bytenr, fs_bytenr,
+				     csum_bytenr);
 out:
 	free(free_tree);
 	return ret;
-- 
2.6.2

[RFC PATCH 15/22] btrfs-progs: Introduce function to create convert data chunks

[Qu Wenruo]

Introduce new function, make_convert_data_chunks(), to build up data
chunks for convert.

It will call a modified verion of btrfs_alloc_data_chunk() to force
data chunks to cover all known ext* data.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 btrfs-convert.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 mkfs.c          |  2 +-
 volumes.c       | 46 ++++++++++++++++++++++++++++++++++------------
 volumes.h       |  2 +-
 4 files changed, 85 insertions(+), 14 deletions(-)

diff --git a/btrfs-convert.c b/btrfs-convert.c
index 3bee049..4626bbd 100644
--- a/btrfs-convert.c
+++ b/btrfs-convert.c
@@ -1688,6 +1688,55 @@ static int create_subvol(struct btrfs_trans_handle *trans,
 	return 0;
 }
 
+/*
+ * New make_btrfs_v2() has handle system and meta chunks quite well.
+ * So only need to add remaining data chunks.
+ */
+static int make_convert_data_block_groups(struct btrfs_trans_handle *trans,
+					  struct btrfs_fs_info *fs_info,
+					  struct btrfs_mkfs_config *cfg)
+{
+	struct btrfs_root *extent_root = fs_info->extent_root;
+	struct cache_tree *data_chunks = &cfg->convert_data_chunks;
+	struct cache_extent *cache;
+	u64 max_chunk_size;
+	int ret = 0;
+
+	/*
+	 * Don't create data chunk over 10% of the convert device
+	 * And for single chunk, don't create chunk larger than 1G.
+	 */
+	max_chunk_size = cfg->num_bytes / 10;
+	max_chunk_size = min((u64)(1024 * 1024 * 1024), max_chunk_size);
+	max_chunk_size = round_down(max_chunk_size, extent_root->sectorsize);
+
+	for (cache = first_cache_extent(data_chunks); cache;
+	     cache = next_cache_extent(cache)) {
+		u64 cur = cache->start;
+
+		while (cur < cache->start + cache->size) {
+			u64 len;
+			u64 cur_backup = cur;
+
+			len = min(max_chunk_size,
+				  cache->start + cache->size - cur);
+			ret = btrfs_alloc_data_chunk(trans, extent_root,
+					&cur_backup, len,
+					BTRFS_BLOCK_GROUP_DATA, 1);
+			if (ret < 0)
+				break;
+			ret = btrfs_make_block_group(trans, extent_root, 0,
+					BTRFS_BLOCK_GROUP_DATA,
+					BTRFS_FIRST_CHUNK_TREE_OBJECTID,
+					cur, len);
+			if (ret < 0)
+				break;
+			cur += len;
+		}
+	}
+	return ret;
+}
+
 static int init_btrfs(struct btrfs_root *root)
 {
 	int ret;
diff --git a/mkfs.c b/mkfs.c
index 306be51..3d62732 100644
--- a/mkfs.c
+++ b/mkfs.c
@@ -974,7 +974,7 @@ static int create_chunks(struct btrfs_trans_handle *trans,
 		size_of_data = minimum_data_chunk_size;
 
 	ret = btrfs_alloc_data_chunk(trans, root->fs_info->extent_root,
-				     &chunk_start, size_of_data, data_type);
+				     &chunk_start, size_of_data, data_type, 0);
 	BUG_ON(ret);
 	ret = btrfs_make_block_group(trans, root->fs_info->extent_root, 0,
 				     data_type, BTRFS_FIRST_CHUNK_TREE_OBJECTID,
diff --git a/volumes.c b/volumes.c
index 4e683bb..edc381e 100644
--- a/volumes.c
+++ b/volumes.c
@@ -399,7 +399,7 @@ static int btrfs_alloc_dev_extent(struct btrfs_trans_handle *trans,
 				  struct btrfs_device *device,
 				  u64 chunk_tree, u64 chunk_objectid,
 				  u64 chunk_offset,
-				  u64 num_bytes, u64 *start)
+				  u64 num_bytes, u64 *start, int convert)
 {
 	int ret;
 	struct btrfs_path *path;
@@ -412,9 +412,15 @@ static int btrfs_alloc_dev_extent(struct btrfs_trans_handle *trans,
 	if (!path)
 		return -ENOMEM;
 
-	ret = find_free_dev_extent(trans, device, path, num_bytes, start);
-	if (ret) {
-		goto err;
+	/*
+	 * For convert case, just skip search free dev_extent, as caller
+	 * is responsible to ensure it's free.
+	 */
+	if (!convert) {
+		ret = find_free_dev_extent(trans, device, path, num_bytes,
+					   start);
+		if (ret)
+			goto err;
 	}
 
 	key.objectid = device->devid;
@@ -973,7 +979,7 @@ again:
 		ret = btrfs_alloc_dev_extent(trans, device,
 			     info->chunk_root->root_key.objectid,
 			     BTRFS_FIRST_CHUNK_TREE_OBJECTID, key.offset,
-			     calc_size, &dev_offset);
+			     calc_size, &dev_offset, 0);
 		BUG_ON(ret);
 
 		device->bytes_used += calc_size;
@@ -1029,9 +1035,17 @@ again:
 	return ret;
 }
 
+/*
+ * Alloc a DATA chunk with SINGLE profile.
+ *
+ * If 'convert' is set, it will alloc a chunk with 1:1 mapping
+ * (btrfs logical bytenr == on-disk bytenr)
+ * For that case, caller must ensure the chunk and dev_extent is not
+ * occupied.
+ */
 int btrfs_alloc_data_chunk(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *extent_root, u64 *start,
-			   u64 num_bytes, u64 type)
+			   u64 num_bytes, u64 type, int convert)
 {
 	u64 dev_offset;
 	struct btrfs_fs_info *info = extent_root->fs_info;
@@ -1052,10 +1066,17 @@ int btrfs_alloc_data_chunk(struct btrfs_trans_handle *trans,
 
 	key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
 	key.type = BTRFS_CHUNK_ITEM_KEY;
-	ret = find_next_chunk(chunk_root, BTRFS_FIRST_CHUNK_TREE_OBJECTID,
-			      &key.offset);
-	if (ret)
-		return ret;
+	if (convert) {
+		BUG_ON(*start != round_down(*start, extent_root->sectorsize));
+		key.offset = *start;
+		dev_offset = *start;
+	} else {
+		ret = find_next_chunk(chunk_root,
+				      BTRFS_FIRST_CHUNK_TREE_OBJECTID,
+				      &key.offset);
+		if (ret)
+			return ret;
+	}
 
 	chunk = kmalloc(btrfs_chunk_item_size(num_stripes), GFP_NOFS);
 	if (!chunk)
@@ -1080,7 +1101,7 @@ int btrfs_alloc_data_chunk(struct btrfs_trans_handle *trans,
 		ret = btrfs_alloc_dev_extent(trans, device,
 			     info->chunk_root->root_key.objectid,
 			     BTRFS_FIRST_CHUNK_TREE_OBJECTID, key.offset,
-			     calc_size, &dev_offset);
+			     calc_size, &dev_offset, convert);
 		BUG_ON(ret);
 
 		device->bytes_used += calc_size;
@@ -1117,7 +1138,8 @@ int btrfs_alloc_data_chunk(struct btrfs_trans_handle *trans,
 	ret = btrfs_insert_item(trans, chunk_root, &key, chunk,
 				btrfs_chunk_item_size(num_stripes));
 	BUG_ON(ret);
-	*start = key.offset;
+	if (!convert)
+		*start = key.offset;
 
 	map->ce.start = key.offset;
 	map->ce.size = num_bytes;
diff --git a/volumes.h b/volumes.h
index eb434f1..fccd964 100644
--- a/volumes.h
+++ b/volumes.h
@@ -191,7 +191,7 @@ int btrfs_alloc_chunk(struct btrfs_trans_handle *trans,
 		      u64 *num_bytes, u64 type);
 int btrfs_alloc_data_chunk(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *extent_root, u64 *start,
-			   u64 num_bytes, u64 type);
+			   u64 num_bytes, u64 type, int convert);
 int btrfs_read_super_device(struct btrfs_root *root, struct extent_buffer *buf);
 int btrfs_add_device(struct btrfs_trans_handle *trans,
 		     struct btrfs_root *root,
-- 
2.6.2

[RFC PATCH 16/22] btrfs-progs: extent-tree: Introduce function to find the first overlap extent.

[Qu Wenruo]

Introduce a new function, btrfs_search_overlap_extent() to find the first
overlap extent.

It's useful for later btrfs-convert rework.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 ctree.c       | 24 +++++++++++++++++++++++
 ctree.h       |  2 ++
 extent-tree.c | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 89 insertions(+)

diff --git a/ctree.c b/ctree.c
index 46153e3..dcf824a 100644
--- a/ctree.c
+++ b/ctree.c
@@ -2937,3 +2937,27 @@ int btrfs_previous_extent_item(struct btrfs_root *root,
 	}
 	return 1;
 }
+
+/*
+ * Search in extent tree to found next meta/data extent
+ * Caller need to check no-hole or skinny metadata
+ */
+int btrfs_next_extent_item(struct btrfs_root *root,
+			struct btrfs_path *path, u64 max_objectid)
+{
+	struct btrfs_key found_key;
+	int ret;
+
+	while (1) {
+		ret = btrfs_next_item(root, path);
+		if (ret)
+			return ret;
+		btrfs_item_key_to_cpu(path->nodes[0], &found_key,
+				      path->slots[0]);
+		if (found_key.objectid > max_objectid)
+			return 1;
+		if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
+		    found_key.type == BTRFS_METADATA_ITEM_KEY)
+		return 0;
+	}
+}
diff --git a/ctree.h b/ctree.h
index c57f9ca..f97af7e 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2301,6 +2301,8 @@ int btrfs_previous_item(struct btrfs_root *root,
 			int type);
 int btrfs_previous_extent_item(struct btrfs_root *root,
 			struct btrfs_path *path, u64 min_objectid);
+int btrfs_next_extent_item(struct btrfs_root *root,
+			struct btrfs_path *path, u64 max_objectid);
 int btrfs_cow_block(struct btrfs_trans_handle *trans,
 		    struct btrfs_root *root, struct extent_buffer *buf,
 		    struct extent_buffer *parent, int parent_slot,
diff --git a/extent-tree.c b/extent-tree.c
index e04d962..9fa9377 100644
--- a/extent-tree.c
+++ b/extent-tree.c
@@ -3908,6 +3908,69 @@ int btrfs_fix_block_accounting(struct btrfs_trans_handle *trans,
 	return 0;
 }
 
+static void __get_extent_size(struct btrfs_root *root, struct btrfs_path *path,
+			      u64 *start, u64 *len)
+{
+	struct btrfs_key key;
+
+	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+	BUG_ON(!(key.type == BTRFS_EXTENT_ITEM_KEY ||
+		 key.type == BTRFS_METADATA_ITEM_KEY));
+	*start = key.objectid;
+	if (key.type == BTRFS_EXTENT_DATA_KEY)
+		*len = key.offset;
+	else
+		*len = root->nodesize;
+}
+
+/*
+ * Find first overlap extent for range [bytenr, bytenr + len)
+ * Return 0 for found and point path to it.
+ * Return >0 for not found.
+ * Return <0 for err
+ */
+int btrfs_search_overlap_extent(struct btrfs_root *root,
+				struct btrfs_path *path, u64 bytenr, u64 len)
+{
+	struct btrfs_key key;
+	u64 cur_start;
+	u64 cur_len;
+	int ret;
+
+	key.objectid = bytenr;
+	key.type = BTRFS_EXTENT_DATA_KEY;
+	key.offset = (u64)-1;
+
+	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
+	if (ret < 0)
+		return ret;
+	BUG_ON(ret == 0);
+
+	ret = btrfs_previous_extent_item(root, path, 0);
+	if (ret < 0)
+		return ret;
+	/* no previous, check next extent */
+	if (ret > 0)
+		goto next;
+	__get_extent_size(root, path, &cur_start, &cur_len);
+	/* Tail overlap */
+	if (cur_start + cur_len > bytenr)
+		return 1;
+
+next:
+	ret = btrfs_next_extent_item(root, path, bytenr + len);
+	if (ret < 0)
+		return ret;
+	/* No next, prev already checked, no overlap */
+	if (ret > 0)
+		return 0;
+	__get_extent_size(root, path, &cur_start, &cur_len);
+	/* head overlap*/
+	if (cur_start < bytenr + len)
+		return 1;
+	return 0;
+}
+
 /*
  * Record a file extent. Do all the required works, such as inserting
  * file extent item, inserting extent item and backref item into extent
-- 
2.6.2

[RFC PATCH 17/22] btrfs-progs: extent-tree: Enhance btrfs_record_file_extent

[Qu Wenruo]

Btrfs_record_file_extent() has some small problems like:
1) Can't handle overlap extent
2) May create extent larger than BTRFS_MAX_EXTENT_SIZE

So enhance it using previous added facilites.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 extent-tree.c | 160 ++++++++++++++++++++++++++++++++++++++++------------------
 utils.h       |   2 +
 2 files changed, 114 insertions(+), 48 deletions(-)

diff --git a/extent-tree.c b/extent-tree.c
index 9fa9377..a2f8fee 100644
--- a/extent-tree.c
+++ b/extent-tree.c
@@ -3917,7 +3917,7 @@ static void __get_extent_size(struct btrfs_root *root, struct btrfs_path *path,
 	BUG_ON(!(key.type == BTRFS_EXTENT_ITEM_KEY ||
 		 key.type == BTRFS_METADATA_ITEM_KEY));
 	*start = key.objectid;
-	if (key.type == BTRFS_EXTENT_DATA_KEY)
+	if (key.type == BTRFS_EXTENT_ITEM_KEY)
 		*len = key.offset;
 	else
 		*len = root->nodesize;
@@ -3971,16 +3971,11 @@ next:
 	return 0;
 }
 
-/*
- * Record a file extent. Do all the required works, such as inserting
- * file extent item, inserting extent item and backref item into extent
- * tree and updating block accounting.
- */
-int btrfs_record_file_extent(struct btrfs_trans_handle *trans,
+static int __btrfs_record_file_extent(struct btrfs_trans_handle *trans,
 			      struct btrfs_root *root, u64 objectid,
 			      struct btrfs_inode_item *inode,
 			      u64 file_pos, u64 disk_bytenr,
-			      u64 num_bytes)
+			      u64 *ret_num_bytes)
 {
 	int ret;
 	struct btrfs_fs_info *info = root->fs_info;
@@ -3988,36 +3983,100 @@ int btrfs_record_file_extent(struct btrfs_trans_handle *trans,
 	struct extent_buffer *leaf;
 	struct btrfs_file_extent_item *fi;
 	struct btrfs_key ins_key;
-	struct btrfs_path path;
+	struct btrfs_path *path;
 	struct btrfs_extent_item *ei;
 	u64 nbytes;
+	u64 extent_num_bytes;
+	u64 extent_bytenr;
+	u64 extent_offset;
+	u64 num_bytes = *ret_num_bytes;
 
+	num_bytes = min_t(u64, num_bytes, BTRFS_MAX_EXTENT_SIZE);
 	if (disk_bytenr == 0) {
 		ret = btrfs_insert_file_extent(trans, root, objectid,
 						file_pos, disk_bytenr,
 						num_bytes, num_bytes);
+		*ret_num_bytes = num_bytes;
 		return ret;
 	}
 
-	btrfs_init_path(&path);
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	/* First to check extent overlap */
+	ret = btrfs_search_overlap_extent(extent_root, path, disk_bytenr,
+					  num_bytes);
+	if (ret < 0)
+		goto fail;
+	if (ret > 0) {
+		/* Found overlap */
+		u64 cur_start;
+		u64 cur_len;
+
+		__get_extent_size(extent_root, path, &cur_start, &cur_len);
+		/*
+		 * Now we only support subset of exist extent
+		 * No complicated split, as in btrfs-convert caller, it
+		 * won't happen
+		 */
+		BUG_ON(disk_bytenr < cur_start);
+
+		extent_bytenr = cur_start;
+		extent_num_bytes = cur_len;
+		extent_offset = disk_bytenr - extent_bytenr;
+	} else {
+		/* No overlap at all, create new extent */
+		btrfs_release_path(path);
+		ins_key.objectid = disk_bytenr;
+		ins_key.offset = num_bytes;
+		ins_key.type = BTRFS_EXTENT_ITEM_KEY;
+
+		ret = btrfs_insert_empty_item(trans, extent_root, path,
+					      &ins_key, sizeof(*ei));
+		if (ret == 0) {
+			leaf = path->nodes[0];
+			ei = btrfs_item_ptr(leaf, path->slots[0],
+					    struct btrfs_extent_item);
+
+			btrfs_set_extent_refs(leaf, ei, 0);
+			btrfs_set_extent_generation(leaf, ei, 0);
+			btrfs_set_extent_flags(leaf, ei,
+					       BTRFS_EXTENT_FLAG_DATA);
+
+			btrfs_mark_buffer_dirty(leaf);
+
+			ret = btrfs_update_block_group(trans, root, disk_bytenr,
+						       num_bytes, 1, 0);
+			if (ret)
+				goto fail;
+		} else if (ret != -EEXIST) {
+			goto fail;
+		}
+		btrfs_extent_post_op(trans, extent_root);
+		extent_bytenr = disk_bytenr;
+		extent_num_bytes = num_bytes;
+		extent_offset = 0;
+	}
 
+	btrfs_release_path(path);
 	ins_key.objectid = objectid;
 	ins_key.offset = file_pos;
 	btrfs_set_key_type(&ins_key, BTRFS_EXTENT_DATA_KEY);
-	ret = btrfs_insert_empty_item(trans, root, &path, &ins_key,
+	ret = btrfs_insert_empty_item(trans, root, path, &ins_key,
 				      sizeof(*fi));
 	if (ret)
 		goto fail;
-	leaf = path.nodes[0];
-	fi = btrfs_item_ptr(leaf, path.slots[0],
+	leaf = path->nodes[0];
+	fi = btrfs_item_ptr(leaf, path->slots[0],
 			    struct btrfs_file_extent_item);
 	btrfs_set_file_extent_generation(leaf, fi, trans->transid);
 	btrfs_set_file_extent_type(leaf, fi, BTRFS_FILE_EXTENT_REG);
-	btrfs_set_file_extent_disk_bytenr(leaf, fi, disk_bytenr);
-	btrfs_set_file_extent_disk_num_bytes(leaf, fi, num_bytes);
-	btrfs_set_file_extent_offset(leaf, fi, 0);
+	btrfs_set_file_extent_disk_bytenr(leaf, fi, extent_bytenr);
+	btrfs_set_file_extent_disk_num_bytes(leaf, fi, extent_num_bytes);
+	btrfs_set_file_extent_offset(leaf, fi, extent_offset);
 	btrfs_set_file_extent_num_bytes(leaf, fi, num_bytes);
-	btrfs_set_file_extent_ram_bytes(leaf, fi, num_bytes);
+	btrfs_set_file_extent_ram_bytes(leaf, fi, extent_num_bytes);
 	btrfs_set_file_extent_compression(leaf, fi, 0);
 	btrfs_set_file_extent_encryption(leaf, fi, 0);
 	btrfs_set_file_extent_other_encoding(leaf, fi, 0);
@@ -4026,41 +4085,46 @@ int btrfs_record_file_extent(struct btrfs_trans_handle *trans,
 	nbytes = btrfs_stack_inode_nbytes(inode) + num_bytes;
 	btrfs_set_stack_inode_nbytes(inode, nbytes);
 
-	btrfs_release_path(&path);
-
-	ins_key.objectid = disk_bytenr;
-	ins_key.offset = num_bytes;
-	ins_key.type = BTRFS_EXTENT_ITEM_KEY;
-
-	ret = btrfs_insert_empty_item(trans, extent_root, &path,
-				      &ins_key, sizeof(*ei));
-	if (ret == 0) {
-		leaf = path.nodes[0];
-		ei = btrfs_item_ptr(leaf, path.slots[0],
-				    struct btrfs_extent_item);
-
-		btrfs_set_extent_refs(leaf, ei, 0);
-		btrfs_set_extent_generation(leaf, ei, 0);
-		btrfs_set_extent_flags(leaf, ei, BTRFS_EXTENT_FLAG_DATA);
-
-		btrfs_mark_buffer_dirty(leaf);
-
-		ret = btrfs_update_block_group(trans, root, disk_bytenr,
-					       num_bytes, 1, 0);
-		if (ret)
-			goto fail;
-	} else if (ret != -EEXIST) {
-		goto fail;
-	}
-	btrfs_extent_post_op(trans, extent_root);
+	btrfs_release_path(path);
 
-	ret = btrfs_inc_extent_ref(trans, root, disk_bytenr, num_bytes, 0,
-				   root->root_key.objectid,
-				   objectid, file_pos);
+	ret = btrfs_inc_extent_ref(trans, root, extent_bytenr, extent_num_bytes,
+				   0, root->root_key.objectid, objectid,
+				   file_pos - extent_offset);
 	if (ret)
 		goto fail;
 	ret = 0;
+	*ret_num_bytes = min(extent_num_bytes, num_bytes);
 fail:
-	btrfs_release_path(&path);
+	btrfs_free_path(path);
+	return ret;
+}
+
+/*
+ * Record a file extent. Do all the required works, such as inserting
+ * file extent item, inserting extent item and backref item into extent
+ * tree and updating block accounting.
+ */
+int btrfs_record_file_extent(struct btrfs_trans_handle *trans,
+			     struct btrfs_root *root, u64 objectid,
+			     struct btrfs_inode_item *inode,
+			     u64 file_pos, u64 disk_bytenr,
+			     u64 num_bytes)
+{
+	u64 cur_disk_bytenr = disk_bytenr;
+	u64 cur_file_pos = file_pos;
+	u64 cur_num_bytes = num_bytes;
+	int ret = 0;
+
+	while (num_bytes > 0) {
+		ret = __btrfs_record_file_extent(trans, root, objectid,
+						 inode, cur_file_pos,
+						 cur_disk_bytenr,
+						 &cur_num_bytes);
+		if (ret < 0)
+			break;
+		cur_disk_bytenr += cur_num_bytes;
+		cur_file_pos += cur_num_bytes;
+		num_bytes -= cur_num_bytes;
+	}
 	return ret;
 }
diff --git a/utils.h b/utils.h
index cec30dc..1fcc72e 100644
--- a/utils.h
+++ b/utils.h
@@ -31,6 +31,8 @@
 		(BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF		\
 		| BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA)
 
+#define BTRFS_MAX_EXTENT_SIZE	(128 * 1024 * 1024)
+
 #define BTRFS_CONVERT_META_GROUP_SIZE (32 * 1024 * 1024)
 
 /*
-- 
2.6.2

[RFC PATCH 18/22] btrfs-progs: convert: Introduce new function to create ext2 image

[Qu Wenruo]

Use new function, create_ext2_image_v2() to create ext2 image.

Unlike old function which is called after copying all inodes, this
function need to be called before copying inodes.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 btrfs-convert.c | 153 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ctree.h         |   1 +
 2 files changed, 154 insertions(+)

diff --git a/btrfs-convert.c b/btrfs-convert.c
index 4626bbd..18701b1 100644
--- a/btrfs-convert.c
+++ b/btrfs-convert.c
@@ -1237,6 +1237,7 @@ static int create_image_file_range(struct btrfs_trans_handle *trans,
 fail:
 	return ret;
 }
+
 /*
  * Create the ext2fs image file.
  */
@@ -1430,6 +1431,158 @@ fail:
 	return ret;
 }
 
+static int create_image_file_range_v2(struct btrfs_trans_handle *trans,
+				      struct btrfs_root *root,
+				      struct cache_tree *used,
+				      struct btrfs_inode_item *inode,
+				      u64 ino, u64 bytenr, u64 *ret_len,
+				      int datacsum)
+{
+	struct cache_extent *cache;
+	struct btrfs_block_group_cache *bg_cache;
+	u64 len = *ret_len;
+	u64 disk_bytenr;
+	int ret;
+
+	BUG_ON(bytenr != round_down(bytenr, root->sectorsize));
+	BUG_ON(len != round_down(len, root->sectorsize));
+	len = min_t(u64, len, BTRFS_MAX_EXTENT_SIZE);
+
+	cache = search_cache_extent(used, bytenr);
+	if (cache) {
+		if (cache->start <= bytenr) {
+			/*
+			 * |///////Used///////|
+			 *	|<--insert--->|
+			 *	bytenr
+			 */
+			len = min_t(u64, len, cache->start + cache->size -
+				    bytenr);
+			disk_bytenr = bytenr;
+		} else {
+			/*
+			 *		|//Used//|
+			 *  |<-insert-->|
+			 *  bytenr
+			 */
+			len = min(len, cache->start - bytenr);
+			disk_bytenr = 0;
+			datacsum = 0;
+		}
+	} else {
+		/*
+		 * |//Used//|		|EOF
+		 * 	    |<-insert-->|
+		 * 	    bytenr
+		 */
+		disk_bytenr = 0;
+		datacsum = 0;
+	}
+
+	if (disk_bytenr) {
+		/* Check if the range is in a data block group */
+		bg_cache = btrfs_lookup_block_group(root->fs_info, bytenr);
+		if (!bg_cache)
+			return -ENOENT;
+		if (!(bg_cache->flags & BTRFS_BLOCK_GROUP_DATA))
+			return -EINVAL;
+	
+		/* The extent should never cross block group boundary */
+		len = min_t(u64, len, bg_cache->key.objectid +
+			    bg_cache->key.offset - bytenr);
+	}
+
+	BUG_ON(len != round_down(len, root->sectorsize));
+	ret = btrfs_record_file_extent(trans, root, ino, inode, bytenr,
+				       disk_bytenr, len);
+	if (ret < 0)
+		return ret;
+
+	if (datacsum)
+		ret = csum_disk_extent(trans, root, bytenr, len);
+	*ret_len = len;
+	return ret;
+}
+
+static int create_ext2_image_v2(struct btrfs_root *root,
+				struct btrfs_mkfs_config *cfg, u64 size,
+				char *name, int datacsum)
+{
+	struct btrfs_inode_item buf;
+	struct btrfs_trans_handle *trans;
+	struct btrfs_path *path = NULL;
+	struct btrfs_key key;
+	u64 cur;
+	u64 ino;
+	int ret;
+
+	trans = btrfs_start_transaction(root, 1);
+	if (!trans)
+		return -ENOMEM;
+	ret = btrfs_find_free_objectid(trans, root, BTRFS_FIRST_FREE_OBJECTID,
+				       &ino);
+	if (ret < 0)
+		goto out;
+	ret = btrfs_new_inode(trans, root, ino, 0600 | S_IFREG);
+	if (ret < 0)
+		goto out;
+	ret = btrfs_add_link(trans, root, ino, BTRFS_FIRST_FREE_OBJECTID, name,
+			     strlen(name), BTRFS_FT_REG_FILE, NULL, 1);
+	if (ret < 0)
+		goto out;
+
+	path = btrfs_alloc_path();
+	if (!path) {
+		ret = -ENOMEM;
+		goto out;
+	}
+	key.objectid = ino;
+	key.type = BTRFS_INODE_ITEM_KEY;
+	key.offset = 0;
+
+	ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
+	if (ret) {
+		ret = (ret > 0 ? -ENOENT : ret);
+		goto out;
+	}
+	read_extent_buffer(path->nodes[0], &buf,
+			btrfs_item_ptr_offset(path->nodes[0], path->slots[0]),
+			sizeof(buf));
+	btrfs_release_path(path);
+
+	/*
+	 * Skip the first 1M, it should be reserved and will be handled later
+	 */
+	cur = 1024 * 1024;
+	while (cur < size) {
+		u64 len = size - cur;
+
+		ret = create_image_file_range_v2(trans, root,
+				&cfg->convert_used, &buf, ino, cur, &len,
+				datacsum);
+		if (ret < 0)
+			goto out;
+		cur += len;
+	}
+
+	key.objectid = ino;
+	key.type = BTRFS_INODE_ITEM_KEY;
+	key.offset = 0;
+	ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
+	if (ret) {
+		ret = (ret > 0 ? -ENOENT : ret);
+		goto out;
+	}
+	btrfs_set_stack_inode_size(&buf, cfg->num_bytes);
+	write_extent_buffer(path->nodes[0], &buf,
+			btrfs_item_ptr_offset(path->nodes[0], path->slots[0]),
+			sizeof(buf));
+out:
+	btrfs_free_path(path);
+	btrfs_commit_transaction(trans, root);
+	return ret;
+}
+
 static struct btrfs_root * link_subvol(struct btrfs_root *root,
 		const char *base, u64 root_objectid)
 {
diff --git a/ctree.h b/ctree.h
index f97af7e..6e3e919 100644
--- a/ctree.h
+++ b/ctree.h
@@ -570,6 +570,7 @@ struct btrfs_extent_item_v0 {
 
 #define BTRFS_MAX_EXTENT_ITEM_SIZE(r) ((BTRFS_LEAF_DATA_SIZE(r) >> 4) - \
 					sizeof(struct btrfs_item))
+#define BTRFS_MAX_EXTENT_SIZE		(128 * 1024 * 1024)
 
 #define BTRFS_EXTENT_FLAG_DATA		(1ULL << 0)
 #define BTRFS_EXTENT_FLAG_TREE_BLOCK	(1ULL << 1)
-- 
2.6.2

[RFC PATCH 19/22] btrfs-progs: convert: Introduce function to migrate reserved ranges

[Qu Wenruo]

Introduce new function, migrate_reserved_ranges() to migrate used ext2
data in btrfs reserved space.

Unlike old implement, which will need to relocate all the complicated
csum and reference relocation, above patches already ensure such
reserved ranges won't be allocated.
So here we only need copy these data out and create new
extent/csum/reference.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 btrfs-convert.c | 123 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 122 insertions(+), 1 deletion(-)

diff --git a/btrfs-convert.c b/btrfs-convert.c
index 18701b1..657fc1d 100644
--- a/btrfs-convert.c
+++ b/btrfs-convert.c
@@ -1504,8 +1504,123 @@ static int create_image_file_range_v2(struct btrfs_trans_handle *trans,
 	return ret;
 }
 
+/*
+ * Relocate used ext2 data in one reserved ranges
+ *
+ * Since all ext2 data in reserved range is not covered by any chunk nor
+ * data extent, we don't need to handle any reference but add new
+ * extent/reference
+ */
+static int migrate_one_reserved_range(struct btrfs_trans_handle *trans,
+				      struct btrfs_root *root,
+				      struct cache_tree *used,
+				      struct btrfs_inode_item *inode, int fd,
+				      u64 ino, u64 start, u64 len, int datacsum)
+{
+	u64 cur_off = start;
+	u64 cur_len = len;
+	struct cache_extent *cache;
+	struct btrfs_key key;
+	struct extent_buffer *eb;
+	int ret = 0;
+
+	while (cur_off < start + len) {
+		cache = lookup_cache_extent(used, cur_off, cur_len);
+		if (!cache)
+			break;
+		cur_off = max(cache->start, cur_off);
+		cur_len = min(cache->start + cache->size, start + len) -
+			  cur_off;
+		BUG_ON(cur_len < root->sectorsize);
+
+		/* reserve extent for the data */
+		ret = btrfs_reserve_extent(trans, root, cur_len, 0, 0, (u64)-1, &key, 1);
+		if (ret < 0)
+			break;
+
+		eb = malloc(sizeof(*eb) + cur_len);
+		if (!eb) {
+			ret = -ENOMEM;
+			break;
+		}
+
+		ret = pread(fd, eb->data, cur_len, cur_off);
+		if (ret < cur_len) {
+			ret = (ret < 0 ? ret : -EIO);
+			free(eb);
+			break;
+		}
+		eb->start = key.objectid;
+		eb->len = key.offset;
+
+		/* Write the data */
+		ret = write_and_map_eb(trans, root, eb);
+		free(eb);
+		if (ret < 0)
+			break;
+
+		/* Now handle extent item and file extent things */
+		ret = btrfs_record_file_extent(trans, root, ino, inode, cur_off,
+					       key.objectid, key.offset);
+		if (ret < 0)
+			break;
+		/* Finally, insert csum items */
+		if (datacsum)
+			ret = csum_disk_extent(trans, root, key.objectid,
+					       key.offset);
+
+		cur_off += key.offset;
+		cur_len = start + len - cur_off;
+	}
+	return ret;
+}
+
+/*
+ * Relocate the used ext2 data in reserved ranges
+ * [0,1M)
+ * [btrfs_sb_offset(1), +BTRFS_STRIPE_LEN)
+ * [btrfs_sb_offset(2), +BTRFS_STRIPE_LEN)
+ */
+static int migrate_reserved_ranges(struct btrfs_trans_handle *trans,
+				   struct btrfs_root *root,
+				   struct cache_tree *used,
+				   struct btrfs_inode_item *inode, int fd,
+				   u64 ino, u64 total_bytes, int datacsum)
+{
+	u64 cur_off;
+	u64 cur_len;
+	int ret = 0;
+
+	/* 0 ~ 1M */
+	cur_off = 0;
+	cur_len = 1024 * 1024;
+	ret = migrate_one_reserved_range(trans, root, used, inode, fd, ino,
+					 cur_off, cur_len, datacsum);
+	if (ret < 0)
+		return ret;
+
+	/* second sb(fisrt sb is included in 0~1M) */
+	cur_off = btrfs_sb_offset(1);
+	cur_len = min(total_bytes, cur_off + BTRFS_STRIPE_LEN) - cur_off;
+	if (cur_off < total_bytes)
+		return ret;
+	ret = migrate_one_reserved_range(trans, root, used, inode, fd, ino,
+					 cur_off, cur_len, datacsum);
+	if (ret < 0)
+		return ret;
+
+	/* Last sb */
+	cur_off = btrfs_sb_offset(2);
+	cur_len = min(total_bytes, cur_off + BTRFS_STRIPE_LEN) - cur_off;
+	if (cur_off < total_bytes)
+		return ret;
+	ret = migrate_one_reserved_range(trans, root, used, inode, fd, ino,
+					 cur_off, cur_len, datacsum);
+	return ret;
+}
+
 static int create_ext2_image_v2(struct btrfs_root *root,
-				struct btrfs_mkfs_config *cfg, u64 size,
+				struct btrfs_mkfs_config *cfg, int fd, u64 size,
 				char *name, int datacsum)
 {
 	struct btrfs_inode_item buf;
@@ -1565,6 +1680,12 @@ static int create_ext2_image_v2(struct btrfs_root *root,
 		cur += len;
 	}
 
+	/* handle the reserved ranges */
+	ret = migrate_reserved_ranges(trans, root, &cfg->convert_used, &buf, fd,
+				      ino, cfg->num_bytes, datacsum);
+	if (ret < 0)
+		goto out;
+
 	key.objectid = ino;
 	key.type = BTRFS_INODE_ITEM_KEY;
 	key.offset = 0;
-- 
2.6.2

[RFC PATCH 20/22] btrfs-progs: Enhance record_file_blocks to handle reserved ranges

[Qu Wenruo]

Enhance record_file_blocks() function to handle reserved ranges.

Unlike most of file extents, ext* data in reserved ranges are not mapped
on disk with 1:1 bytenr.
So we can't use bytenr directly.

But thanks for calling create_ext2_image_v2() before copying inodes, we
have a image in convert subvolume as a logical <-> disk bytenr mapping.

So use it to handle reserved ranges for record_file_blocks().

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 btrfs-convert.c | 99 +++++++++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 90 insertions(+), 9 deletions(-)

diff --git a/btrfs-convert.c b/btrfs-convert.c
index 657fc1d..993ee80 100644
--- a/btrfs-convert.c
+++ b/btrfs-convert.c
@@ -464,7 +464,9 @@ static int csum_disk_extent(struct btrfs_trans_handle *trans,
 struct blk_iterate_data {
 	struct btrfs_trans_handle *trans;
 	struct btrfs_root *root;
+	struct btrfs_root *convert_root;
 	struct btrfs_inode_item *inode;
+	u64 convert_ino;
 	u64 objectid;
 	u64 first_block;
 	u64 disk_block;
@@ -480,6 +482,8 @@ static void init_blk_iterate_data(struct blk_iterate_data *data,
 				  struct btrfs_inode_item *inode,
 				  u64 objectid, int checksum)
 {
+	struct btrfs_key key;
+
 	data->trans		= trans;
 	data->root		= root;
 	data->inode		= inode;
@@ -490,25 +494,100 @@ static void init_blk_iterate_data(struct blk_iterate_data *data,
 	data->boundary		= (u64)-1;
 	data->checksum		= checksum;
 	data->errcode		= 0;
+
+	key.objectid = CONV_IMAGE_SUBVOL_OBJECTID;
+	key.type = BTRFS_ROOT_ITEM_KEY;
+	key.offset = (u64)-1;
+	data->convert_root = btrfs_read_fs_root(root->fs_info, &key);
+	/* Impossible since previously we just opened that subvolume */
+	BUG_ON(!data->convert_root || IS_ERR(data->convert_root));
+	data->convert_ino = BTRFS_FIRST_FREE_OBJECTID + 1;
 }
 
 static int record_file_blocks(struct blk_iterate_data *data,
 			      u64 file_block, u64 disk_block, u64 num_blocks)
 {
-	int ret;
+	int ret = 0;
 	struct btrfs_root *root = data->root;
+	struct btrfs_root *convert_root = data->convert_root;
+	struct btrfs_path *path;
 	u64 file_pos = file_block * root->sectorsize;
-	u64 disk_bytenr = disk_block * root->sectorsize;
+	u64 old_disk_bytenr = disk_block * root->sectorsize;
 	u64 num_bytes = num_blocks * root->sectorsize;
-	ret = btrfs_record_file_extent(data->trans, data->root,
-				       data->objectid, data->inode, file_pos,
-				       disk_bytenr, num_bytes);
-
-	if (ret || !data->checksum || disk_bytenr == 0)
-		return ret;
+	u64 cur_off = old_disk_bytenr;
 
-	return csum_disk_extent(data->trans, data->root, disk_bytenr,
+	if (old_disk_bytenr == 0)
+		return btrfs_record_file_extent(data->trans, root,
+				data->objectid, data->inode, file_pos, 0,
 				num_bytes);
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+	/*
+	 * Since the logical mapping of converted image is not all 1:1,
+	 * especially for the reserved ranges, so we shouldn't use disk_bytenr
+	 * directly, but search in convert_subvolume.
+	 * Which acts like another logical <-> disk mapping layer.
+	 */
+	while (cur_off < old_disk_bytenr + num_bytes) {
+		struct btrfs_key key;
+		struct btrfs_file_extent_item *fi;
+		struct extent_buffer *node;
+		int slot;
+		u64 extent_disk_bytenr;
+		u64 extent_num_bytes;
+		u64 real_disk_bytenr;
+		u64 cur_len;
+
+		key.objectid = data->convert_ino;
+		key.type = BTRFS_EXTENT_DATA_KEY;
+		key.offset = cur_off;
+
+		ret = btrfs_search_slot(NULL, convert_root, &key, path, 0, 0);
+		if (ret < 0)
+			break;
+		if (ret > 0) {
+			ret = btrfs_previous_item(convert_root, path,
+						  data->convert_ino,
+						  BTRFS_EXTENT_DATA_KEY);
+			if (ret < 0)
+				break;
+			if (ret > 0) {
+				ret = -ENOENT;
+				break;
+			}
+		}
+		node = path->nodes[0];
+		slot = path->slots[0];
+		btrfs_item_key_to_cpu(node, &key, slot);
+		BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY ||
+		       key.objectid != data->convert_ino ||
+		       key.offset > cur_off);
+		fi = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item);
+		extent_disk_bytenr = btrfs_file_extent_disk_bytenr(node, fi);
+		extent_num_bytes = btrfs_file_extent_disk_num_bytes(node, fi);
+		BUG_ON(cur_off - key.offset >= extent_num_bytes);
+		btrfs_release_path(path);
+
+		real_disk_bytenr = cur_off - key.offset + extent_disk_bytenr;
+		cur_len = min(key.offset + extent_num_bytes,
+			      old_disk_bytenr + num_bytes) - cur_off;
+		ret = btrfs_record_file_extent(data->trans, data->root,
+				data->objectid, data->inode, file_pos,
+				real_disk_bytenr, cur_len);
+		if (ret < 0)
+			break;
+		cur_off += cur_len;
+		file_pos += cur_len;
+		/*
+		 * Here we don't need to care about data checksum
+		 * As all the ext* data is already calculated for csum, so no
+		 * need to calculate it again
+		 */
+	}
+
+	btrfs_free_path(path);
+	return ret;
 }
 
 static int block_iterate_proc(u64 disk_block, u64 file_block,
@@ -1638,6 +1717,8 @@ static int create_ext2_image_v2(struct btrfs_root *root,
 				       &ino);
 	if (ret < 0)
 		goto out;
+	/* Shouldn't happen, and we need this const ino for later use */
+	BUG_ON(ino != BTRFS_FIRST_FREE_OBJECTID + 1);
 	ret = btrfs_new_inode(trans, root, ino, 0600 | S_IFREG);
 	if (ret < 0)
 		goto out;
-- 
2.6.2

[RFC PATCH 21/22] btrfs-progs: convert: Introduce init_btrfs_v2 function.

[Qu Wenruo]

Introduce new init_btrfs_v2() function for later newer do_convert().

Since we have good enough chunk allocation, a lot of wired chunk hack
won't ever be used.
We only need to insert data chunks and create needed subvolume/inode.

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

diff --git a/btrfs-convert.c b/btrfs-convert.c
index 993ee80..9e8158d 100644
--- a/btrfs-convert.c
+++ b/btrfs-convert.c
@@ -2092,6 +2092,102 @@ static int make_convert_data_block_groups(struct btrfs_trans_handle *trans,
 	return ret;
 }
 
+/*
+ * Init the temp btrfs to a operational status.
+ *
+ * It will fix the extent usage accounting and insert needed data chunks, to
+ * ensure all ext* data extents are covered by DATA chunks, preventing wrong
+ * chunks are allocated.
+ * And also create convert image subvolume and relocation tree.
+ */
+static int init_btrfs_v2(struct btrfs_mkfs_config *cfg, ext2_filsys ext2_fs,
+			 struct btrfs_root *root, int datacsum, int packing,
+			 int noxattr)
+{
+	struct btrfs_key location;
+	struct btrfs_trans_handle *trans;
+	struct btrfs_fs_info *fs_info = root->fs_info;
+	struct ext2_inode ext2_inode;
+	ext2_inode_scan ext2_scan;
+	ext2_ino_t ext2_ino;
+	int found_root = 0;
+	int ret;
+
+	trans = btrfs_start_transaction(root, 1);
+	BUG_ON(!trans);
+	ret = btrfs_fix_block_accounting(trans, root);
+	if (ret)
+		goto err;
+	ret = make_convert_data_block_groups(trans, fs_info, cfg);
+	if (ret)
+		goto err;
+	ret = btrfs_make_root_dir(trans, fs_info->tree_root,
+				  BTRFS_ROOT_TREE_DIR_OBJECTID);
+	if (ret)
+		goto err;
+	memcpy(&location, &root->root_key, sizeof(location));
+	location.offset = (u64)-1;
+	ret = btrfs_insert_dir_item(trans, fs_info->tree_root, "default", 7,
+				btrfs_super_root_dir(fs_info->super_copy),
+				&location, BTRFS_FT_DIR, 0);
+	if (ret)
+		goto err;
+	ret = btrfs_insert_inode_ref(trans, fs_info->tree_root, "default", 7,
+				location.objectid,
+				btrfs_super_root_dir(fs_info->super_copy), 0);
+	if (ret)
+		goto err;
+	btrfs_set_root_dirid(&fs_info->fs_root->root_item,
+			     BTRFS_FIRST_FREE_OBJECTID);
+
+	/* subvol for ext2 image file */
+	ret = create_subvol(trans, root, CONV_IMAGE_SUBVOL_OBJECTID);
+	BUG_ON(ret);
+	/* subvol for data relocation */
+	ret = create_subvol(trans, root, BTRFS_DATA_RELOC_TREE_OBJECTID);
+	BUG_ON(ret);
+
+	/*
+	 * Copy root inode for fs_root. Or we will be unable to do
+	 * link_subvol().
+	 * And it can't be done before create_subvol(), as it will copy
+	 * tree root, including all its contents.
+	 */
+	ret = ext2fs_open_inode_scan(ext2_fs, 0, &ext2_scan);
+	if (ret) {
+		fprintf(stderr, "ext2fs_open_inode_scan: %s\n",
+			error_message(ret));
+		return -EIO;
+	}
+
+	while (!(ret = ext2fs_get_next_inode(ext2_scan, &ext2_ino,
+					     &ext2_inode))) {
+		if (ext2_ino == 0 || ext2_ino >= EXT2_GOOD_OLD_FIRST_INO)
+			break;
+		if (ext2_ino == EXT2_ROOT_INO) {
+			found_root = 1;
+			break;
+		}
+	}
+	ext2fs_close_inode_scan(ext2_scan);
+
+	if (found_root) {
+		ret = copy_single_inode(trans, root, BTRFS_FIRST_FREE_OBJECTID,
+					ext2_fs, ext2_ino, &ext2_inode,
+					datacsum, packing, noxattr);
+		if (ret < 0)
+			goto err;
+	} else {
+		ret = -ENOENT;
+		goto err;
+	}
+
+	ret = btrfs_commit_transaction(trans, root);
+	BUG_ON(ret);
+err:
+	return ret;
+}
+
 static int init_btrfs(struct btrfs_root *root)
 {
 	int ret;
-- 
2.6.2

[RFC PATCH 22/22] btrfs-progs: Introduce do_convert_v2 function

[Qu Wenruo]

Introduce new function do_convert_v2() to do new convert.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 btrfs-convert.c | 187 ++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 utils.c         |   3 +
 2 files changed, 186 insertions(+), 4 deletions(-)

diff --git a/btrfs-convert.c b/btrfs-convert.c
index 9e8158d..8079aea 100644
--- a/btrfs-convert.c
+++ b/btrfs-convert.c
@@ -1217,7 +1217,8 @@ fail:
  * scan ext2's inode bitmap and copy all used inodes.
  */
 static int copy_inodes(struct btrfs_root *root, ext2_filsys ext2_fs,
-		       int datacsum, int packing, int noxattr, struct task_ctx *p)
+		       int datacsum, int packing, int noxattr, int skip_root,
+		       struct task_ctx *p)
 {
 	int ret;
 	errcode_t err;
@@ -1242,7 +1243,7 @@ static int copy_inodes(struct btrfs_root *root, ext2_filsys ext2_fs,
 			break;
 		/* skip special inode in ext2fs */
 		if (ext2_ino < EXT2_GOOD_OLD_FIRST_INO &&
-		    ext2_ino != EXT2_ROOT_INO)
+		    (ext2_ino != EXT2_ROOT_INO || skip_root))
 			continue;
 		objectid = ext2_ino + INO_OFFSET;
 		ret = copy_single_inode(trans, root,
@@ -2857,6 +2858,183 @@ static int read_ext2_used_space(ext2_filsys fs, struct cache_tree *used_tree)
 	return ret;
 }
 
+static int do_convert_v2(const char *devname, int datacsum, int packing,
+		int noxattr, u64 nodesize, int copylabel, const char *fslabel,
+		int progress, u64 features)
+{
+	int ret;
+	int fd = -1;
+	int is_btrfs = 0;
+	u32 blocksize;
+	u64 blocks[7];
+	u64 total_bytes;
+	ext2_filsys ext2_fs;
+	struct btrfs_root *root;
+	struct btrfs_root *image_root;
+	struct task_ctx ctx;
+	char features_buf[64];
+	struct btrfs_mkfs_config mkfs_cfg;
+
+	ret = open_ext2fs(devname, &ext2_fs);
+	if (ret) {
+		fprintf(stderr, "unable to open the Ext2fs\n");
+		goto fail;
+	}
+	blocksize = ext2_fs->blocksize;
+	total_bytes = (u64)ext2_fs->super->s_blocks_count * blocksize;
+	if (blocksize < 4096) {
+		fprintf(stderr, "block size is too small\n");
+		goto fail;
+	}
+	if (!(ext2_fs->super->s_feature_incompat &
+	      EXT2_FEATURE_INCOMPAT_FILETYPE)) {
+		fprintf(stderr, "filetype feature is missing\n");
+		goto fail;
+	}
+	if (btrfs_check_nodesize(nodesize, blocksize, features))
+		goto fail;
+
+	/* Build the used space tree first */
+	init_mkfs_config(&mkfs_cfg);
+	ret = read_ext2_used_space(ext2_fs, &mkfs_cfg.convert_used);
+	if (ret < 0) {
+		error("fail to read ext2 block bitmap\n");
+		goto fail;
+	}
+
+	fd = open(devname, O_RDWR);
+	if (fd < 0) {
+		fprintf(stderr, "unable to open %s\n", devname);
+		goto fail;
+	}
+	btrfs_parse_features_to_string(features_buf, features);
+	if (features == BTRFS_MKFS_DEFAULT_FEATURES)
+		strcat(features_buf, " (default)");
+
+	printf("create btrfs filesystem:\n");
+	printf("\tblocksize: %u\n", blocksize);
+	printf("\tnodesize:  %llu\n", nodesize);
+	printf("\tfeatures:  %s\n", features_buf);
+
+	mkfs_cfg.label = ext2_fs->super->s_volume_name;
+	mkfs_cfg.fs_uuid = malloc(BTRFS_UUID_UNPARSED_SIZE);
+	if (!mkfs_cfg.fs_uuid) {
+		ret = -ENOMEM;
+		goto fail;
+	}
+	*(mkfs_cfg.fs_uuid) = '\0';
+	mkfs_cfg.chunk_uuid = malloc(BTRFS_UUID_UNPARSED_SIZE);
+	if (!mkfs_cfg.chunk_uuid) {
+		ret = -ENOMEM;
+		goto fail;
+	}
+	*(mkfs_cfg.chunk_uuid) = '\0';
+	memcpy(mkfs_cfg.blocks, blocks, sizeof(blocks));
+	mkfs_cfg.num_bytes = total_bytes;
+	mkfs_cfg.nodesize = nodesize;
+	mkfs_cfg.sectorsize = blocksize;
+	mkfs_cfg.stripesize = blocksize;
+	mkfs_cfg.features = features;
+
+	ret = make_btrfs(fd, &mkfs_cfg);
+	if (ret) {
+		fprintf(stderr, "unable to create initial ctree: %s\n",
+			strerror(-ret));
+		goto fail;
+	}
+	root = open_ctree_fd(fd, devname, mkfs_cfg.super_bytenr,
+			     OPEN_CTREE_WRITES);
+	if (!root) {
+		fprintf(stderr, "unable to open ctree\n");
+		goto fail;
+	}
+	ret = init_btrfs_v2(&mkfs_cfg, ext2_fs, root, datacsum, packing, 
+			    noxattr);
+	if (ret) {
+		fprintf(stderr, "unable to setup the root tree\n");
+		goto fail;
+	}
+	printf("creating ext2fs image file.\n");
+	image_root = link_subvol(root, "ext2_saved", CONV_IMAGE_SUBVOL_OBJECTID);
+	if (!image_root) {
+		fprintf(stderr, "unable to create subvol\n");
+		goto fail;
+	}
+	ret = create_ext2_image_v2(image_root, &mkfs_cfg, fd, total_bytes,
+				   "image", datacsum);
+	if (ret) {
+		fprintf(stderr, "error during create_ext2_image %d\n", ret);
+		goto fail;
+	}
+	printf("creating btrfs metadata.\n");
+	ctx.max_copy_inodes = (ext2_fs->super->s_inodes_count
+			- ext2_fs->super->s_free_inodes_count);
+	ctx.cur_copy_inodes = 0;
+
+	if (progress) {
+		ctx.info = task_init(print_copied_inodes, after_copied_inodes, &ctx);
+		task_start(ctx.info);
+	}
+	ret = copy_inodes(root, ext2_fs, datacsum, packing, noxattr, 1, &ctx);
+	if (ret) {
+		fprintf(stderr, "error during copy_inodes %d\n", ret);
+		goto fail;
+	}
+	if (progress) {
+		task_stop(ctx.info);
+		task_deinit(ctx.info);
+	}
+	memset(root->fs_info->super_copy->label, 0, BTRFS_LABEL_SIZE);
+	if (copylabel == 1) {
+		strncpy(root->fs_info->super_copy->label,
+				ext2_fs->super->s_volume_name, 16);
+		fprintf(stderr, "copy label '%s'\n",
+				root->fs_info->super_copy->label);
+	} else if (copylabel == -1) {
+		strcpy(root->fs_info->super_copy->label, fslabel);
+		fprintf(stderr, "set label to '%s'\n", fslabel);
+	}
+
+	ret = close_ctree(root);
+	if (ret) {
+		fprintf(stderr, "error during close_ctree %d\n", ret);
+		goto fail;
+	}
+	close_ext2fs(ext2_fs);
+
+	/*
+	 * If this step succeed, we get a mountable btrfs. Otherwise
+	 * the ext2fs is left unchanged.
+	 */
+	ret = migrate_super_block(fd, mkfs_cfg.super_bytenr, blocksize);
+	if (ret) {
+		fprintf(stderr, "unable to migrate super block\n");
+		goto fail;
+	}
+	is_btrfs = 1;
+
+	root = open_ctree_fd(fd, devname, 0, OPEN_CTREE_WRITES);
+	if (!root) {
+		fprintf(stderr, "unable to open ctree\n");
+		goto fail;
+	}
+	close(fd);
+
+	printf("conversion complete.\n");
+	return 0;
+fail:
+	free_mkfs_config(&mkfs_cfg);
+
+	if (fd != -1)
+		close(fd);
+	if (is_btrfs)
+		fprintf(stderr,
+			"WARNING: an error occured during chunk mapping fixup, filesystem mountable but not finalized\n");
+	else
+		fprintf(stderr, "conversion aborted\n");
+	return -1;
+}
+
 static int do_convert(const char *devname, int datacsum, int packing, int noxattr,
 		u32 nodesize, int copylabel, const char *fslabel, int progress,
 		u64 features)
@@ -2933,6 +3111,7 @@ static int do_convert(const char *devname, int datacsum, int packing, int noxatt
 	printf("\tfeatures:  %s\n", features_buf);
 
 	mkfs_cfg.label = ext2_fs->super->s_volume_name;
+	mkfs_cfg.chunk_uuid = NULL;
 	mkfs_cfg.fs_uuid = NULL;
 	memcpy(mkfs_cfg.blocks, blocks, sizeof(blocks));
 	mkfs_cfg.num_bytes = total_bytes;
@@ -2987,7 +3166,7 @@ static int do_convert(const char *devname, int datacsum, int packing, int noxatt
 		ctx.info = task_init(print_copied_inodes, after_copied_inodes, &ctx);
 		task_start(ctx.info);
 	}
-	ret = copy_inodes(root, ext2_fs, datacsum, packing, noxattr, &ctx);
+	ret = copy_inodes(root, ext2_fs, datacsum, packing, noxattr, 0, &ctx);
 	if (ret) {
 		fprintf(stderr, "error during copy_inodes %d\n", ret);
 		goto fail;
@@ -3606,7 +3785,7 @@ int main(int argc, char *argv[])
 	if (rollback) {
 		ret = do_rollback(file);
 	} else {
-		ret = do_convert(file, datacsum, packing, noxattr, nodesize,
+		ret = do_convert_v2(file, datacsum, packing, noxattr, nodesize,
 				copylabel, fslabel, progress, features);
 	}
 	if (ret)
diff --git a/utils.c b/utils.c
index f5fadb1..6c5b17a 100644
--- a/utils.c
+++ b/utils.c
@@ -1214,6 +1214,9 @@ int make_btrfs(int fd, struct btrfs_mkfs_config *cfg)
 				 BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA);
 	u64 num_bytes;
 
+	if (!cache_tree_empty(&cfg->convert_used))
+		return make_btrfs_v2(fd, cfg);
+
 	buf = malloc(sizeof(*buf) + max(cfg->sectorsize, cfg->nodesize));
 	if (!buf)
 		return -ENOMEM;
-- 
2.6.2