[PATCH 0/7] btrfs-progs: mkfs: Reword --rootdir

[PATCH 0/7] btrfs-progs: mkfs: Reword --rootdir

[Qu Wenruo]

Can be fetched from github:
https://github.com/adam900710/btrfs-progs/tree/mkfs_rootdir_rework

And fetching from github is preferred method to test, as this patchset
has 2 prerequisite:

1) Minimal device size patchset
   The image size estimate algorithm heavily relies on the minimal
   device size calculation

2) Rootdir refactor
   To make life a little easier.

Both the prerequisite has no further modification in this patchset, just the
version submitted to mail list, and rebased to v4.13.3 without any
conflict.

Rework 'mkfs.btrfs --rootdir' by:

1) Not using custom chunk allocator
   Use btrfs_alloc_chunk() only.
   Although currently chunk allocator in btrfs-progs is not small device
   friendly, which will try to allocate large chunk.
   This can be addressed by image size estimate algorithm, so it won't
   cause too much problem.
   (But still, it follow the minimal device size from normal mkfs, which
    is over 100M for default profile)

2) New image size estimate algorithm
   Use over-reserve-for-metadata method, which should ensure we can write
   all content into the image.
   And rely later shrink the shrink the fs size to minimal.

   Although the method itself is based on over-reserve, but in fact it's
   quite space efficient in most case.
   For empty file case, we will use the allocated data/meta space
   allocated in normal mkfs, so no shrink really needed.

   For large file and small metadata case, the size difference between
   shrunk and unshrunk image is less than 1%.

   Although due to the nature we over-reserve for metadata, for
   extremely unbalanced data/meta case, like tons of empty files, we
   really need to rely shrink functionality.

   And the algorithm itself only needs minimal amount of data.
   It only uses number of inodes and file size of each regular inode.

3) Shrinking the fs by device extent
   As implemented in almost all version of rework which includes
   shrinking, tried and true, and easier to implement.
   And shrinking is completely independent now, can be easily modified
   to shrink multi-device btrfs.

4) Separate shrink functionality to '--shrink' option
   This causes less confusion.
   And due to my poor English, I only added basic explanation to the
   mkfs doc. Although I think this is enough since each functionality
   is easier to understand.

5) Not wasting IO to wipe the whole image
   Only to wipe the first 1M and create sparse file.

Qu Wenruo (7):
  btrfs-progs: mkfs: Don't use custom chunk allocator for rootdir
  btrfs-progs: mkfs/rootdir: Use over-reserve method to make size
    estimate easier
  btrfs-progs: mkfs: Only zero out the first 1M for rootdir
  btrfs-progs: mkfs/rootdir: Introduce function to get end position of
    last device extent
  btrfs-progs: mkfs/rootdir: Shrink fs for rootdir option
  btrfs-progs: mkfs: Update allocation info before verbose output
  btrfs-progs: mkfs: Separate shrink from rootdir

 Documentation/mkfs.btrfs.asciidoc |  11 ++
 mkfs/main.c                       | 260 ++++++++++++++++-----------------
 mkfs/rootdir.c                    | 292 +++++++++++++++++++++++++++++++++-----
 mkfs/rootdir.h                    |   6 +-
 4 files changed, 400 insertions(+), 169 deletions(-)

-- 
2.14.2

[PATCH 1/7] btrfs-progs: mkfs: Don't use custom chunk allocator for rootdir

[Qu Wenruo]

Remove these custom chunk allocator for mkfs.
Use generic btrfs chunk allocator instead.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 mkfs/main.c | 75 ++++++-------------------------------------------------------
 1 file changed, 7 insertions(+), 68 deletions(-)

diff --git a/mkfs/main.c b/mkfs/main.c
index 423b35579722..5b8de6f690bb 100644
--- a/mkfs/main.c
+++ b/mkfs/main.c
@@ -400,53 +400,6 @@ static char *parse_label(const char *input)
 	return strdup(input);
 }
 
-static int create_chunks(struct btrfs_trans_handle *trans,
-			 struct btrfs_root *root, u64 num_of_meta_chunks,
-			 u64 size_of_data,
-			 struct mkfs_allocation *allocation)
-{
-	struct btrfs_fs_info *fs_info = root->fs_info;
-	u64 chunk_start;
-	u64 chunk_size;
-	u64 meta_type = BTRFS_BLOCK_GROUP_METADATA;
-	u64 data_type = BTRFS_BLOCK_GROUP_DATA;
-	u64 minimum_data_chunk_size = SZ_8M;
-	u64 i;
-	int ret;
-
-	for (i = 0; i < num_of_meta_chunks; i++) {
-		ret = btrfs_alloc_chunk(trans, fs_info,
-					&chunk_start, &chunk_size, meta_type);
-		if (ret)
-			return ret;
-		ret = btrfs_make_block_group(trans, fs_info, 0,
-					     meta_type, BTRFS_FIRST_CHUNK_TREE_OBJECTID,
-					     chunk_start, chunk_size);
-		allocation->metadata += chunk_size;
-		if (ret)
-			return ret;
-		set_extent_dirty(&root->fs_info->free_space_cache,
-				 chunk_start, chunk_start + chunk_size - 1);
-	}
-
-	if (size_of_data < minimum_data_chunk_size)
-		size_of_data = minimum_data_chunk_size;
-
-	ret = btrfs_alloc_data_chunk(trans, fs_info,
-				     &chunk_start, size_of_data, data_type, 0);
-	if (ret)
-		return ret;
-	ret = btrfs_make_block_group(trans, fs_info, 0,
-				     data_type, BTRFS_FIRST_CHUNK_TREE_OBJECTID,
-				     chunk_start, size_of_data);
-	allocation->data += size_of_data;
-	if (ret)
-		return ret;
-	set_extent_dirty(&root->fs_info->free_space_cache,
-			 chunk_start, chunk_start + size_of_data - 1);
-	return ret;
-}
-
 static int zero_output_file(int out_fd, u64 size)
 {
 	int loop_num;
@@ -1180,34 +1133,20 @@ raid_groups:
 		goto out;
 	}
 
-	if (source_dir_set) {
-		trans = btrfs_start_transaction(root, 1);
-		BUG_ON(IS_ERR(trans));
-		ret = create_chunks(trans, root,
-				    num_of_meta_chunks, size_of_data,
-				    &allocation);
-		if (ret) {
-			error("unable to create chunks: %d", ret);
-			goto out;
-		}
-		ret = btrfs_commit_transaction(trans, root);
-		if (ret) {
-			error("transaction commit failed: %d", ret);
-			goto out;
-		}
+	ret = cleanup_temp_chunks(fs_info, &allocation, data_profile,
+				  metadata_profile, metadata_profile);
+	if (ret < 0) {
+		error("failed to cleanup temporary chunks: %d", ret);
+		goto out;
+	}
 
+	if (source_dir_set) {
 		ret = btrfs_mkfs_fill_dir(source_dir, root, verbose);
 		if (ret) {
 			error("error wihle filling filesystem: %d", ret);
 			goto out;
 		}
 	}
-	ret = cleanup_temp_chunks(fs_info, &allocation, data_profile,
-				  metadata_profile, metadata_profile);
-	if (ret < 0) {
-		error("failed to cleanup temporary chunks: %d", ret);
-		goto out;
-	}
 
 	if (verbose) {
 		char features_buf[64];
-- 
2.14.2

[PATCH 2/7] btrfs-progs: mkfs/rootdir: Use over-reserve method to make size estimate easier

[Qu Wenruo]

Use an easier method to calculate the estimate device for mkfs.btrfs
--rootdir.

The new method will over-estimate, but should ensure we won't encounter
ENOSPC.

It relies on the following data to estimate:
1) number of inodes
   for metadata chunk size
2) rounded up data size of each regular inode
   for data chunk size.

Total meta chunk size = round_up(nr_inode * (PATH_MAX * 3 + sectorsize),
min_chunk_size) * profile_multiplier

PATH_MAX is the maximum size possible for INODE_REF/DIR_INDEX/DIR_ITEM.
Sectorsize is the maximum size possible for inline extent.
min_chunk_size is 8M for SINGLE, and 32M for DUP, get from
btrfs_alloc_chunk().
profile_multiplier is 1 for Single, 2 for DUP.

Total data chunk size is much easier.
Total data chunk size = round_up(total_data_usage, min_chunk_size) *
profile_multiplier

Total_data_usage is the sum of *rounded up* size of each regular inode
use.
min_chunk_size is 8M for SINGLE, 64M for DUP, get from
btrfS_alloc_chunk().
Same profile_multiplier for meta.

This over-estimate calculate is, of course, over-estimate.
But since we will later shrink the fs to its real usage, it doesn't
matter much now.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 mkfs/main.c    | 109 ++++++++++++++++++++++++++--------------------------
 mkfs/rootdir.c | 119 +++++++++++++++++++++++++++++++++++++++------------------
 mkfs/rootdir.h |   4 +-
 3 files changed, 139 insertions(+), 93 deletions(-)

diff --git a/mkfs/main.c b/mkfs/main.c
index 5b8de6f690bb..1355089505ca 100644
--- a/mkfs/main.c
+++ b/mkfs/main.c
@@ -693,8 +693,6 @@ int main(int argc, char **argv)
 	int force_overwrite = 0;
 	char *source_dir = NULL;
 	int source_dir_set = 0;
-	u64 num_of_meta_chunks = 0;
-	u64 size_of_data = 0;
 	u64 source_dir_size = 0;
 	u64 min_dev_size;
 	int dev_cnt = 0;
@@ -909,6 +907,34 @@ int main(int argc, char **argv)
 
 	min_dev_size = btrfs_min_dev_size(nodesize, mixed, metadata_profile,
 					  data_profile);
+	/*
+	 * Enlarge the destination file or create new one, using the
+	 * size calculated from source dir.
+	 *
+	 * This must be done before minimal device size check.
+	 */
+	if (source_dir_set) {
+		fd = open(file, O_CREAT | O_RDWR, S_IRUSR | S_IWUSR | S_IRGRP |
+			  S_IWGRP | S_IROTH);
+		if (fd < 0) {
+			error("unable to open %s: %s", file, strerror(errno));
+			goto error;
+		}
+
+		source_dir_size = btrfs_mkfs_size_dir(source_dir, sectorsize,
+				min_dev_size, metadata_profile, data_profile);
+		if (block_count < source_dir_size)
+			block_count = source_dir_size;
+		ret = zero_output_file(fd, block_count);
+		if (ret) {
+			error("unable to zero the output file");
+			close(fd);
+			goto error;
+		}
+		/* our "device" is the new image file */
+		dev_block_count = block_count;
+		close(fd);
+	}
 	/* Check device/block_count after the nodesize is determined */
 	if (block_count && block_count < min_dev_size) {
 		error("size %llu is too small to make a usable filesystem",
@@ -942,51 +968,28 @@ int main(int argc, char **argv)
 
 	dev_cnt--;
 
-	if (!source_dir_set) {
-		/*
-		 * open without O_EXCL so that the problem should not
-		 * occur by the following processing.
-		 * (btrfs_register_one_device() fails if O_EXCL is on)
-		 */
-		fd = open(file, O_RDWR);
-		if (fd < 0) {
-			error("unable to open %s: %s", file, strerror(errno));
-			goto error;
-		}
-		ret = btrfs_prepare_device(fd, file, &dev_block_count,
-				block_count,
-				(zero_end ? PREP_DEVICE_ZERO_END : 0) |
-				(discard ? PREP_DEVICE_DISCARD : 0) |
-				(verbose ? PREP_DEVICE_VERBOSE : 0));
-		if (ret) {
-			goto error;
-		}
-		if (block_count && block_count > dev_block_count) {
-			error("%s is smaller than requested size, expected %llu, found %llu",
-					file,
-					(unsigned long long)block_count,
-					(unsigned long long)dev_block_count);
-			goto error;
-		}
-	} else {
-		fd = open(file, O_CREAT | O_RDWR,
-				S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP | S_IROTH);
-		if (fd < 0) {
-			error("unable to open %s: %s", file, strerror(errno));
-			goto error;
-		}
-
-		source_dir_size = btrfs_mkfs_size_dir(source_dir, sectorsize,
-					&num_of_meta_chunks, &size_of_data);
-		if(block_count < source_dir_size)
-			block_count = source_dir_size;
-		ret = zero_output_file(fd, block_count);
-		if (ret) {
-			error("unable to zero the output file");
-			goto error;
-		}
-		/* our "device" is the new image file */
-		dev_block_count = block_count;
+	/*
+	 * open without O_EXCL so that the problem should not
+	 * occur by the following processing.
+	 * (btrfs_register_one_device() fails if O_EXCL is on)
+	 */
+	fd = open(file, O_RDWR);
+	if (fd < 0) {
+		error("unable to open %s: %s", file, strerror(errno));
+		goto error;
+	}
+	ret = btrfs_prepare_device(fd, file, &dev_block_count,
+			block_count,
+			(zero_end ? PREP_DEVICE_ZERO_END : 0) |
+			(discard ? PREP_DEVICE_DISCARD : 0) |
+			(verbose ? PREP_DEVICE_VERBOSE : 0));
+	if (ret)
+		goto error;
+	if (block_count && block_count > dev_block_count) {
+		error("%s is smaller than requested size, expected %llu, found %llu",
+		      file, (unsigned long long)block_count,
+		      (unsigned long long)dev_block_count);
+		goto error;
 	}
 
 	/* To create the first block group and chunk 0 in make_btrfs */
@@ -1112,13 +1115,11 @@ int main(int argc, char **argv)
 	}
 
 raid_groups:
-	if (!source_dir_set) {
-		ret = create_raid_groups(trans, root, data_profile,
-				 metadata_profile, mixed, &allocation);
-		if (ret) {
-			error("unable to create raid groups: %d", ret);
-			goto out;
-		}
+	ret = create_raid_groups(trans, root, data_profile,
+			 metadata_profile, mixed, &allocation);
+	if (ret) {
+		error("unable to create raid groups: %d", ret);
+		goto out;
 	}
 
 	ret = create_tree(trans, root, BTRFS_DATA_RELOC_TREE_OBJECTID);
diff --git a/mkfs/rootdir.c b/mkfs/rootdir.c
index 83a3191d2bd7..99022afaa030 100644
--- a/mkfs/rootdir.c
+++ b/mkfs/rootdir.c
@@ -32,19 +32,29 @@
 #include "transaction.h"
 #include "utils.h"
 #include "mkfs/rootdir.h"
+#include "mkfs/common.h"
 #include "send-utils.h"
 
-/*
- * This ignores symlinks with unreadable targets and subdirs that can't
- * be read.  It's a best-effort to give a rough estimate of the size of
- * a subdir.  It doesn't guarantee that prepopulating btrfs from this
- * tree won't still run out of space.
- */
-static u64 global_total_size;
-static u64 fs_block_size;
+static u32 fs_block_size;
 
 static u64 index_cnt = 2;
 
+/*
+ * Size estimate will be done using the following data:
+ * 1) Number of inodes
+ *    Since we will later shrink the fs, over-estimate is completely fine here
+ *    as long as our estimate ensure we can populate the image without ENOSPC.
+ *    So we only records how many inodes there is, and use the maximum space
+ *    usage for every inode.
+ *
+ * 2) Data space each (regular) inode uses
+ *    To estimate data chunk size.
+ *    Don't care if it can fit as inline extent.
+ *    Always round them up to sectorsize.
+ */
+static u64 ftw_meta_nr_inode;
+static u64 ftw_data_size;
+
 static int add_directory_items(struct btrfs_trans_handle *trans,
 			       struct btrfs_root *root, u64 objectid,
 			       ino_t parent_inum, const char *name,
@@ -684,52 +694,87 @@ out:
 static int ftw_add_entry_size(const char *fpath, const struct stat *st,
 			      int type)
 {
-	if (type == FTW_F || type == FTW_D)
-		global_total_size += round_up(st->st_size, fs_block_size);
+	/*
+	 * Failed to read dir, mostly due to EPERM.
+	 * Abort ASAP, so we don't need to populate the fs
+	 */
+	if (type == FTW_DNR || type == FTW_NS)
+		return -EPERM;
+
+	if (S_ISREG(st->st_mode))
+		ftw_data_size += round_up(st->st_size, fs_block_size);
+	ftw_meta_nr_inode++;
 
 	return 0;
 }
 
-u64 btrfs_mkfs_size_dir(const char *dir_name, u64 sectorsize,
-			u64 *num_of_meta_chunks_ret, u64 *size_of_data_ret)
+u64 btrfs_mkfs_size_dir(const char *dir_name, u32 sectorsize, u64 min_dev_size,
+			u64 meta_profile, u64 data_profile)
 {
-	u64 dir_size = 0;
 	u64 total_size = 0;
 	int ret;
-	u64 default_chunk_size = SZ_8M;
-	u64 allocated_meta_size = SZ_8M;
-	u64 allocated_total_size = 20 * SZ_1M;	/* 20MB */
-	u64 num_of_meta_chunks = 0;
-	u64 num_of_data_chunks = 0;
-	u64 num_of_allocated_meta_chunks =
-			allocated_meta_size / default_chunk_size;
-
-	global_total_size = 0;
+
+	u64 meta_size = 0;	/* Based on @ftw_meta_nr_inode */
+	u64 meta_chunk_size = 0;/* Based on @meta_size */
+	u64 data_chunk_size = 0;/* Based on @ftw_data_size */
+
+	u64 meta_threshold = SZ_8M;
+	u64 data_threshold = SZ_8M;
+
+	float data_multipler = 1;
+	float meta_multipler = 1;
+
 	fs_block_size = sectorsize;
+	ftw_data_size = 0;
+	ftw_meta_nr_inode = 0;
 	ret = ftw(dir_name, ftw_add_entry_size, 10);
-	dir_size = global_total_size;
 	if (ret < 0) {
 		error("ftw subdir walk of %s failed: %s", dir_name,
 			strerror(errno));
 		exit(1);
 	}
 
-	num_of_data_chunks = (dir_size + default_chunk_size - 1) /
-		default_chunk_size;
 
-	num_of_meta_chunks = (dir_size / 2) / default_chunk_size;
-	if (((dir_size / 2) % default_chunk_size) != 0)
-		num_of_meta_chunks++;
-	if (num_of_meta_chunks <= num_of_allocated_meta_chunks)
-		num_of_meta_chunks = 0;
-	else
-		num_of_meta_chunks -= num_of_allocated_meta_chunks;
+	/*
+	 * Maximum metadata useage for every inode, which will be PATH_MAX
+	 * for the following items:
+	 * 1) DIR_ITEM
+	 * 2) DIR_INDEX
+	 * 3) INODE_REF
+	 *
+	 * Plus possible inline extent size, which is sectorsize.
+	 *
+	 * And finally, allow metadata usage to increase with data size.
+	 * Follow the old kernel 8:1 data:meta ratio.
+	 * This is especially important for --rootdir, as the file extent size
+	 * up limit is 1M, instead of 128M in kernel.
+	 * This can bump meta usage easily.
+	 */
+	meta_size = ftw_meta_nr_inode * (PATH_MAX * 3 + sectorsize) +
+		    ftw_data_size / 8;
 
-	total_size = allocated_total_size +
-		     (num_of_data_chunks * default_chunk_size) +
-		     (num_of_meta_chunks * default_chunk_size);
+	/* Minimal chunk size from btrfs_alloc_chunk(). */
+	if (meta_profile & BTRFS_BLOCK_GROUP_DUP) {
+		meta_threshold = SZ_32M;
+		meta_multipler = 2;
+	}
+	if (data_profile & BTRFS_BLOCK_GROUP_DUP) {
+		data_threshold = SZ_64M;
+		data_multipler = 2;
+	}
 
-	*num_of_meta_chunks_ret = num_of_meta_chunks;
-	*size_of_data_ret = num_of_data_chunks * default_chunk_size;
+	/*
+	 * Only when the usage is larger than the minimal chunk size (threshold)
+	 * we need to allocate new chunk, or the initial chunk in the image is
+	 * large enough.
+	 */
+	if (meta_size > meta_threshold)
+		meta_chunk_size = (round_up(meta_size, meta_threshold) -
+				   meta_threshold) * meta_multipler;
+	if (ftw_data_size > data_threshold)
+		data_chunk_size = (round_up(ftw_data_size, data_threshold) -
+				   data_threshold) * data_multipler;
+
+	total_size = data_chunk_size + meta_chunk_size + min_dev_size;
 	return total_size;
 }
diff --git a/mkfs/rootdir.h b/mkfs/rootdir.h
index a557bd183f7b..75169f37e026 100644
--- a/mkfs/rootdir.h
+++ b/mkfs/rootdir.h
@@ -27,6 +27,6 @@ struct directory_name_entry {
 
 int btrfs_mkfs_fill_dir(const char *source_dir, struct btrfs_root *root,
 			bool verbose);
-u64 btrfs_mkfs_size_dir(const char *dir_name, u64 sectorsize,
-			u64 *num_of_meta_chunks_ret, u64 *size_of_data_ret);
+u64 btrfs_mkfs_size_dir(const char *dir_name, u32 sectorsize, u64 min_dev_size,
+			u64 meta_profile, u64 data_profile);
 #endif
-- 
2.14.2

[PATCH 3/7] btrfs-progs: mkfs: Only zero out the first 1M for rootdir

[Qu Wenruo]

It's a waste of IO to fill the whole image before creating btrfs on it,
just wiping the first 1M, and then write 1 byte to the last position to
create a sparse file.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 mkfs/main.c | 19 +++++++++++++------
 1 file changed, 13 insertions(+), 6 deletions(-)

diff --git a/mkfs/main.c b/mkfs/main.c
index 1355089505ca..7b78cfe3550e 100644
--- a/mkfs/main.c
+++ b/mkfs/main.c
@@ -404,18 +404,25 @@ static int zero_output_file(int out_fd, u64 size)
 {
 	int loop_num;
 	u64 location = 0;
-	char buf[4096];
+	char buf[SZ_4K];
 	int ret = 0, i;
 	ssize_t written;
 
-	memset(buf, 0, 4096);
-	loop_num = size / 4096;
+	memset(buf, 0, SZ_4K);
+
+	/* Only zero out the first 1M */
+	loop_num = SZ_1M / SZ_4K;
 	for (i = 0; i < loop_num; i++) {
-		written = pwrite64(out_fd, buf, 4096, location);
-		if (written != 4096)
+		written = pwrite64(out_fd, buf, SZ_4K, location);
+		if (written != SZ_4K)
 			ret = -EIO;
-		location += 4096;
+		location += SZ_4K;
 	}
+
+	/* Then enlarge the file to size */
+	written = pwrite64(out_fd, buf, 1, size - 1);
+	if (written < 1)
+		ret = -EIO;
 	return ret;
 }
 
-- 
2.14.2

[PATCH 4/7] btrfs-progs: mkfs/rootdir: Introduce function to get end position of last device extent

[Qu Wenruo]

Useful for later 'mkfs.btrfs --rootdir' shrink support.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 mkfs/rootdir.c | 43 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 43 insertions(+)

diff --git a/mkfs/rootdir.c b/mkfs/rootdir.c
index 99022afaa030..1ca37996a3b3 100644
--- a/mkfs/rootdir.c
+++ b/mkfs/rootdir.c
@@ -26,6 +26,7 @@
 #include <fcntl.h>
 #include <ftw.h>
 #include "ctree.h"
+#include "volumes.h"
 #include "internal.h"
 #include "disk-io.h"
 #include "messages.h"
@@ -778,3 +779,45 @@ u64 btrfs_mkfs_size_dir(const char *dir_name, u32 sectorsize, u64 min_dev_size,
 	total_size = data_chunk_size + meta_chunk_size + min_dev_size;
 	return total_size;
 }
+
+/*
+ * Get the end position of the last device extent for given @devid;
+ * @size_ret is exclsuive (means it should be aligned to sectorsize)
+ */
+static int get_device_extent_end(struct btrfs_fs_info *fs_info,
+				 u64 devid, u64 *size_ret)
+{
+	struct btrfs_root *dev_root = fs_info->dev_root;
+	struct btrfs_key key;
+	struct btrfs_path path;
+	struct btrfs_dev_extent *de;
+	int ret;
+
+	key.objectid = devid;
+	key.type = BTRFS_DEV_EXTENT_KEY;
+	key.offset = (u64)-1;
+
+	btrfs_init_path(&path);
+	ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0);
+	/* Not really possible */
+	BUG_ON(ret == 0);
+
+	ret = btrfs_previous_item(dev_root, &path, devid, BTRFS_DEV_EXTENT_KEY);
+	if (ret < 0)
+		goto out;
+
+	/* No dev_extent at all, not really possible for rootdir case*/
+	if (ret > 0) {
+		*size_ret = 0;
+		ret = -EUCLEAN;
+		goto out;
+	}
+
+	btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
+	de = btrfs_item_ptr(path.nodes[0], path.slots[0],
+			    struct btrfs_dev_extent);
+	*size_ret = key.offset + btrfs_dev_extent_length(path.nodes[0], de);
+out:
+	btrfs_release_path(&path);
+	return ret;
+}
-- 
2.14.2

[PATCH 5/7] btrfs-progs: mkfs/rootdir: Shrink fs for rootdir option

[Qu Wenruo]

Use the new dev extent based shrink method for rootdir option.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 mkfs/main.c    |   5 +++
 mkfs/rootdir.c | 111 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 mkfs/rootdir.h |   1 +
 3 files changed, 117 insertions(+)

diff --git a/mkfs/main.c b/mkfs/main.c
index 7b78cfe3550e..0866e40d155f 100644
--- a/mkfs/main.c
+++ b/mkfs/main.c
@@ -1154,6 +1154,11 @@ raid_groups:
 			error("error wihle filling filesystem: %d", ret);
 			goto out;
 		}
+		ret = btrfs_mkfs_shrink_fs(fs_info, NULL);
+		if (ret < 0) {
+			error("error while shrinking filesystem: %d", ret);
+			goto out;
+		}
 	}
 
 	if (verbose) {
diff --git a/mkfs/rootdir.c b/mkfs/rootdir.c
index 1ca37996a3b3..9593bbc25b39 100644
--- a/mkfs/rootdir.c
+++ b/mkfs/rootdir.c
@@ -821,3 +821,114 @@ out:
 	btrfs_release_path(&path);
 	return ret;
 }
+
+/*
+ * Set device size to @new_size.
+ *
+ * Only used for --rootdir option.
+ * We will need to reset the following values:
+ * 1) dev item in chunk tree
+ * 2) super->dev_item
+ * 3) super->total_bytes
+ */
+static int set_device_size(struct btrfs_fs_info *fs_info,
+			   struct btrfs_device *device, u64 new_size)
+{
+	struct btrfs_root *chunk_root = fs_info->chunk_root;
+	struct btrfs_trans_handle *trans;
+	struct btrfs_dev_item *di;
+	struct btrfs_path path;
+	struct btrfs_key key;
+	int ret;
+
+	/*
+	 * Update in-meory device->total_bytes, so that at trans commit time,
+	 * it super->dev_item will also get updated
+	 */
+	device->total_bytes = new_size;
+	btrfs_init_path(&path);
+
+	/* Update device item in chunk tree */
+	trans = btrfs_start_transaction(chunk_root, 1);
+	if (IS_ERR(trans)) {
+		ret = PTR_ERR(trans);
+		error("failed to start transaction: %d (%s)", ret,
+			strerror(-ret));
+		return ret;
+	}
+	key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
+	key.type = BTRFS_DEV_ITEM_KEY;
+	key.offset = device->devid;
+
+	ret = btrfs_search_slot(trans, chunk_root, &key, &path, 0, 1);
+	if (ret < 0)
+		goto err;
+	if (ret > 0)
+		ret = -ENOENT;
+	di = btrfs_item_ptr(path.nodes[0], path.slots[0],
+			    struct btrfs_dev_item);
+	btrfs_set_device_total_bytes(path.nodes[0], di, new_size);
+	btrfs_mark_buffer_dirty(path.nodes[0]);
+
+	/*
+	 * Update super->total_bytes, since it's only used for --rootdir,
+	 * there is only one device, just use the @new_size.
+	 */
+	btrfs_set_super_total_bytes(fs_info->super_copy, new_size);
+
+	/*
+	 * Commit transaction to reflect the updated super->total_bytes and
+	 * super->dev_item
+	 */
+	ret = btrfs_commit_transaction(trans, chunk_root);
+	if (ret < 0)
+		error("failed to commit current transaction: %d (%s)",
+			ret, strerror(-ret));
+	btrfs_release_path(&path);
+	return ret;
+
+err:
+	btrfs_release_path(&path);
+	/*
+	 * Commit trans here won't cause problem since the fs still has
+	 * bad magic, and something wrong already happened, we don't
+	 * care the return value anyway.
+	 */
+	btrfs_commit_transaction(trans, chunk_root);
+	return ret;
+}
+
+int btrfs_mkfs_shrink_fs(struct btrfs_fs_info *fs_info, u64 *new_size_ret)
+{
+	u64 new_size;
+	struct btrfs_device *device;
+	struct list_head *cur;
+	int nr_devs = 0;
+	int ret;
+
+	list_for_each(cur, &fs_info->fs_devices->devices)
+		nr_devs++;
+
+	if (nr_devs > 1) {
+		error("cannot shrink fs with more than 1 device");
+		return -ENOTTY;
+	}
+
+	ret = get_device_extent_end(fs_info, 1, &new_size);
+	if (ret < 0) {
+		error("failed to get minimal device size: %d (%s)",
+			ret, strerror(-ret));
+		return ret;
+	}
+
+	BUG_ON(!IS_ALIGNED(new_size, fs_info->sectorsize));
+
+	device = list_entry(fs_info->fs_devices->devices.next,
+			   struct btrfs_device, dev_list);
+	ret = set_device_size(fs_info, device, new_size);
+	if (ret < 0)
+		return ret;
+	if (new_size_ret)
+		*new_size_ret = new_size;
+	return ret;
+}
diff --git a/mkfs/rootdir.h b/mkfs/rootdir.h
index 75169f37e026..e5b739ede48a 100644
--- a/mkfs/rootdir.h
+++ b/mkfs/rootdir.h
@@ -29,4 +29,5 @@ int btrfs_mkfs_fill_dir(const char *source_dir, struct btrfs_root *root,
 			bool verbose);
 u64 btrfs_mkfs_size_dir(const char *dir_name, u32 sectorsize, u64 min_dev_size,
 			u64 meta_profile, u64 data_profile);
+int btrfs_mkfs_shrink_fs(struct btrfs_fs_info *fs_info, u64 *new_size_ret);
 #endif
-- 
2.14.2

[PATCH 6/7] btrfs-progs: mkfs: Update allocation info before verbose output

[Qu Wenruo]

Since new --rootdir can allocate chunk, it will modify the chunk
allocation result.

This patch will update allocation info before verbose output to reflect
such info.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 mkfs/main.c | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)

diff --git a/mkfs/main.c b/mkfs/main.c
index 0866e40d155f..6aefb50a8033 100644
--- a/mkfs/main.c
+++ b/mkfs/main.c
@@ -670,6 +670,38 @@ out:
 	return ret;
 }
 
+/*
+ * Just update chunk allocation info, since --rootdir may allocate new
+ * chunks which is not updated in @allocation structure.
+ */
+static void update_chunk_allocation(struct btrfs_fs_info *fs_info,
+				    struct mkfs_allocation *allocation)
+{
+	struct btrfs_block_group_cache *bg_cache;
+	u64 mixed_flag = BTRFS_BLOCK_GROUP_DATA | BTRFS_BLOCK_GROUP_METADATA;
+	u64 search_start = 0;
+
+	allocation->mixed = 0;
+	allocation->data = 0;
+	allocation->metadata = 0;
+	allocation->system = 0;
+	while (1) {
+		bg_cache = btrfs_lookup_first_block_group(fs_info,
+							  search_start);
+		if (!bg_cache)
+			break;
+		if ((bg_cache->flags & mixed_flag) == mixed_flag)
+			allocation->mixed += bg_cache->key.offset;
+		else if (bg_cache->flags & BTRFS_BLOCK_GROUP_DATA)
+			allocation->data += bg_cache->key.offset;
+		else if (bg_cache->flags & BTRFS_BLOCK_GROUP_METADATA)
+			allocation->metadata += bg_cache->key.offset;
+		else
+			allocation->system += bg_cache->key.offset;
+		search_start = bg_cache->key.objectid + bg_cache->key.offset;
+	}
+}
+
 int main(int argc, char **argv)
 {
 	char *file;
@@ -1164,6 +1196,7 @@ raid_groups:
 	if (verbose) {
 		char features_buf[64];
 
+		update_chunk_allocation(fs_info, &allocation);
 		printf("Label:              %s\n", label);
 		printf("UUID:               %s\n", mkfs_cfg.fs_uuid);
 		printf("Node size:          %u\n", nodesize);
-- 
2.14.2

[PATCH 7/7] btrfs-progs: mkfs: Separate shrink from rootdir

[Qu Wenruo]

Make --shrink a separate option for --rootdir, and make it default to
off.
So this will cause less confusion.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 Documentation/mkfs.btrfs.asciidoc | 11 +++++++++++
 mkfs/main.c                       | 27 +++++++++++++++++++++------
 mkfs/rootdir.c                    | 21 ++++++++++++++++++++-
 mkfs/rootdir.h                    |  3 ++-
 4 files changed, 54 insertions(+), 8 deletions(-)

diff --git a/Documentation/mkfs.btrfs.asciidoc b/Documentation/mkfs.btrfs.asciidoc
index d53d9e265fb7..5ddbedbcea97 100644
--- a/Documentation/mkfs.btrfs.asciidoc
+++ b/Documentation/mkfs.btrfs.asciidoc
@@ -106,6 +106,17 @@ Please see the mount option 'discard' for that in `btrfs`(5).
 *-r|--rootdir <rootdir>*::
 Populate the toplevel subvolume with files from 'rootdir'.  This does not
 require root permissions and does not mount the filesystem.
++
+NOTE: This option may enlarge the image or file to ensure it's large enough to
+contain the files from 'rootdir'.
+
+*--shrink*:
+Shrink the filesystem to its minimal size, only works with *-r|--rootdir*
+option.
++
+NOTE: If the destination is regular file, this option will also reduce the
+file size. Or it will only reduce the filesystem available space.
+Extra space will not be usable unless resized using 'btrfs filesystem resize'.
 
 *-O|--features <feature1>[,<feature2>...]*::
 A list of filesystem features turned on at mkfs time. Not all features are
diff --git a/mkfs/main.c b/mkfs/main.c
index 6aefb50a8033..1d72702414bc 100644
--- a/mkfs/main.c
+++ b/mkfs/main.c
@@ -731,9 +731,11 @@ int main(int argc, char **argv)
 	int ssd = 0;
 	int force_overwrite = 0;
 	char *source_dir = NULL;
-	int source_dir_set = 0;
+	bool source_dir_set = false;
+	bool shrink_rootdir = false;
 	u64 source_dir_size = 0;
 	u64 min_dev_size;
+	u64 shrink_size;
 	int dev_cnt = 0;
 	int saved_optind;
 	char fs_uuid[BTRFS_UUID_UNPARSED_SIZE] = { 0 };
@@ -743,6 +745,7 @@ int main(int argc, char **argv)
 
 	while(1) {
 		int c;
+		enum { GETOPT_VAL_SHRINK = 257 };
 		static const struct option long_options[] = {
 			{ "alloc-start", required_argument, NULL, 'A'},
 			{ "byte-count", required_argument, NULL, 'b' },
@@ -760,6 +763,7 @@ int main(int argc, char **argv)
 			{ "features", required_argument, NULL, 'O' },
 			{ "uuid", required_argument, NULL, 'U' },
 			{ "quiet", 0, NULL, 'q' },
+			{ "shrink", no_argument, NULL, GETOPT_VAL_SHRINK },
 			{ "help", no_argument, NULL, GETOPT_VAL_HELP },
 			{ NULL, 0, NULL, 0}
 		};
@@ -827,7 +831,7 @@ int main(int argc, char **argv)
 				goto success;
 			case 'r':
 				source_dir = optarg;
-				source_dir_set = 1;
+				source_dir_set = true;
 				break;
 			case 'U':
 				strncpy(fs_uuid, optarg,
@@ -839,6 +843,10 @@ int main(int argc, char **argv)
 			case 'q':
 				verbose = 0;
 				break;
+			case GETOPT_VAL_SHRINK:
+				shrink_rootdir = true;
+				break;
+				break;
 			case GETOPT_VAL_HELP:
 			default:
 				print_usage(c != GETOPT_VAL_HELP);
@@ -861,6 +869,10 @@ int main(int argc, char **argv)
 		error("the option -r is limited to a single device");
 		goto error;
 	}
+	if (shrink_rootdir && !source_dir_set) {
+		error("the option --shrink can only be paired with -r");
+		goto error;
+	}
 
 	if (*fs_uuid) {
 		uuid_t dummy_uuid;
@@ -1186,10 +1198,13 @@ raid_groups:
 			error("error wihle filling filesystem: %d", ret);
 			goto out;
 		}
-		ret = btrfs_mkfs_shrink_fs(fs_info, NULL);
-		if (ret < 0) {
-			error("error while shrinking filesystem: %d", ret);
-			goto out;
+		if (shrink_rootdir) {
+			ret = btrfs_mkfs_shrink_fs(fs_info, &shrink_size,
+						   shrink_rootdir);
+			if (ret < 0) {
+				error("error while shrinking filesystem: %d", ret);
+				goto out;
+			}
 		}
 	}
 
diff --git a/mkfs/rootdir.c b/mkfs/rootdir.c
index 9593bbc25b39..aa42d186a43f 100644
--- a/mkfs/rootdir.c
+++ b/mkfs/rootdir.c
@@ -898,11 +898,13 @@ err:
 	return ret;
 }
 
-int btrfs_mkfs_shrink_fs(struct btrfs_fs_info *fs_info, u64 *new_size_ret)
+int btrfs_mkfs_shrink_fs(struct btrfs_fs_info *fs_info, u64 *new_size_ret,
+			 bool shrink_file_size)
 {
 	u64 new_size;
 	struct btrfs_device *device;
 	struct list_head *cur;
+	struct stat64 file_stat;
 	int nr_devs = 0;
 	int ret;
 
@@ -930,5 +932,22 @@ int btrfs_mkfs_shrink_fs(struct btrfs_fs_info *fs_info, u64 *new_size_ret)
 		return ret;
 	if (new_size_ret)
 		*new_size_ret = new_size;
+
+	if (shrink_file_size) {
+		ret = fstat64(device->fd, &file_stat);
+		if (ret < 0) {
+			error("failed to stat devid %llu: %s", device->devid,
+				strerror(errno));
+			return ret;
+		}
+		if (!S_ISREG(file_stat.st_mode))
+			return ret;
+		ret = ftruncate64(device->fd, new_size);
+		if (ret < 0) {
+			error("failed to truncate device file of devid %llu: %s",
+				device->devid, strerror(errno));
+			return ret;
+		}
+	}
 	return ret;
 }
diff --git a/mkfs/rootdir.h b/mkfs/rootdir.h
index e5b739ede48a..78bc9c90f7c5 100644
--- a/mkfs/rootdir.h
+++ b/mkfs/rootdir.h
@@ -29,5 +29,6 @@ int btrfs_mkfs_fill_dir(const char *source_dir, struct btrfs_root *root,
 			bool verbose);
 u64 btrfs_mkfs_size_dir(const char *dir_name, u32 sectorsize, u64 min_dev_size,
 			u64 meta_profile, u64 data_profile);
-int btrfs_mkfs_shrink_fs(struct btrfs_fs_info *fs_info, u64 *new_size_ret);
+int btrfs_mkfs_shrink_fs(struct btrfs_fs_info *fs_info, u64 *new_size_ret,
+			 bool shrink_file_size);
 #endif
-- 
2.14.2

Re: [PATCH 0/7] btrfs-progs: mkfs: Reword --rootdir

[David Sterba]

On Fri, Oct 20, 2017 at 09:59:00AM +0800, Qu Wenruo wrote:
> Can be fetched from github:
> https://github.com/adam900710/btrfs-progs/tree/mkfs_rootdir_rework
> 
> And fetching from github is preferred method to test, as this patchset
> has 2 prerequisite:
> 
> 1) Minimal device size patchset
>    The image size estimate algorithm heavily relies on the minimal
>    device size calculation
> 
> 2) Rootdir refactor
>    To make life a little easier.
> 
> Both the prerequisite has no further modification in this patchset, just the
> version submitted to mail list, and rebased to v4.13.3 without any
> conflict.

FYI, this patchset is now under close review and is going to be merged
next. The patches look good so far but I still may have some questions
or comments.  The status of the patchset is in tracking pull request #66.

Re: [PATCH 3/7] btrfs-progs: mkfs: Only zero out the first 1M for rootdir

[David Sterba]

On Fri, Oct 20, 2017 at 09:59:03AM +0800, Qu Wenruo wrote:
> It's a waste of IO to fill the whole image before creating btrfs on it,
> just wiping the first 1M, and then write 1 byte to the last position to
> create a sparse file.
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>

Applied, thanks.

Re: [PATCH 4/7] btrfs-progs: mkfs/rootdir: Introduce function to get end position of last device extent

[David Sterba]

On Fri, Oct 20, 2017 at 09:59:04AM +0800, Qu Wenruo wrote:
> Useful for later 'mkfs.btrfs --rootdir' shrink support.
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>

Applied, thanks.

Re: [PATCH 6/7] btrfs-progs: mkfs: Update allocation info before verbose output

[David Sterba]

On Fri, Oct 20, 2017 at 09:59:06AM +0800, Qu Wenruo wrote:
> Since new --rootdir can allocate chunk, it will modify the chunk
> allocation result.
> 
> This patch will update allocation info before verbose output to reflect
> such info.
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>

Applied, thanks.

Re: [PATCH 0/7] btrfs-progs: mkfs: Reword --rootdir

[David Sterba]

On Fri, Oct 20, 2017 at 09:59:00AM +0800, Qu Wenruo wrote:
> Qu Wenruo (7):
>   btrfs-progs: mkfs: Don't use custom chunk allocator for rootdir
>   btrfs-progs: mkfs/rootdir: Use over-reserve method to make size
>     estimate easier
>   btrfs-progs: mkfs: Only zero out the first 1M for rootdir
>   btrfs-progs: mkfs/rootdir: Introduce function to get end position of
>     last device extent
>   btrfs-progs: mkfs/rootdir: Shrink fs for rootdir option
>   btrfs-progs: mkfs: Update allocation info before verbose output
>   btrfs-progs: mkfs: Separate shrink from rootdir

I've merged independent patches or what applied almost cleanly on
current devel. Please refresh and resend patches 1, 2, 5 and 7, thanks.