[PATCH 00/15] btrfs-progs: extent tree v2 gc tree and metadata ref changes

[PATCH 00/15] btrfs-progs: extent tree v2 gc tree and metadata ref changes

[Josef Bacik]

Hello,

Here's the next set of btrfs-progs patches for the next set of extent tree v2
features, no more metadata reference tracking and support for a garbge
collection tree.

1. No more metadata reference tracking.  For cowonly trees (global roots) we
   never have more than one reference for a block, so the reference counting
   adds a fair bit of overhead for these trees.  This is especially noticeable
   with the extent tree, we have to update the extent tree to include references
   for every block, including blocks in the extent tree, which generates more
   modifications to the extent tree.  In practice there's a stable state so we
   do not recursively use all the disk space describing the extent tree, however
   it generates a certain amount of churn.

   For FS tree's that can be shared we still want a way to know when we can free
   blocks.  That will be accomplished by drop trees in a future patchset and
   described more thoroughly there.

2. Garbage collection tree.  Free'ing objects in btrfs is a more complicated
   operation than in other file systems.  For truncate we can mete out the
   removal of the inode items, but the cleaning up of checksums has to be done
   in the transaction that the extent is freed.  For large files this can be
   quite expensive and cause latencies because we have to hold the transaction
   open for these operations.  Deferring this work to a GC tree will allow us to
   better throttle these long running operations without causing latencies for
   the rest of the system.

   As alluded above, free'ing shared metadata extents via the drop trees will
   be one of these longer running operations, having a GC tree in place will
   allow us to do these heavier operations without requiring they be done in a
   single transaction.

These patches have been tested with the corresponding kernel patches and pass
the xfstests that are able to be run.  Thanks,

Josef

Josef Bacik (15):
  btrfs-progs: extract out free extent accounting handling
  btrfs-progs: check: skip owner ref check for extent tree v2
  btrfs-progs: check: skip extent backref for metadata in extent tree v2
  btrfs-progs: check: calculate normal flags for extent tree v2 metadata
  btrfs-progs: check: make metadata ref counting extent tree v2 aware
  btrfs-progs: check: update block group used properly for extent tree
    v2
  btrfs-progs: do not insert extent items for metadata for extent tree
    v2
  btrfs-progs: do not remove metadata backrefs for extent tree v2
  btrfs-progs: repair: traverse tree blocks for extent tree v2
  btrfs-progs: cache the block group with the free space tree if
    possible
  btrfs-progs: make btrfs_lookup_extent_info extent tree v2 aware
  btrfs-progs: mkfs: don't populate extent tree with extent tree v2
  btrfs-progs: add on-disk items and read support for the gc tree
  btrfs-progs: mkfs: create the gc tree at mkfs time
  btrfs-progs: deal with GC items in check

 check/main.c                     |  98 ++++++++++++++-
 check/mode-original.h            |   1 +
 common/repair.c                  |   6 +
 kernel-shared/ctree.h            |   6 +
 kernel-shared/disk-io.c          |   5 +
 kernel-shared/extent-tree.c      |  82 ++++++++----
 kernel-shared/free-space-cache.c |   3 +
 kernel-shared/print-tree.c       |   4 +
 mkfs/common.c                    | 207 +++++++++++++++++--------------
 mkfs/main.c                      |  13 +-
 10 files changed, 303 insertions(+), 122 deletions(-)

-- 
2.26.3

[PATCH 01/15] btrfs-progs: extract out free extent accounting handling

[Josef Bacik]

__free_extent() currently handles the modification of the tree, but also
the accounting and cleaning up when we free the extent properly.
Extract the accounting portion out into it's own helper so it can be
used in the future.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 kernel-shared/extent-tree.c | 45 +++++++++++++++++++++----------------
 1 file changed, 26 insertions(+), 19 deletions(-)

diff --git a/kernel-shared/extent-tree.c b/kernel-shared/extent-tree.c
index 1469f5c3..1af3eb06 100644
--- a/kernel-shared/extent-tree.c
+++ b/kernel-shared/extent-tree.c
@@ -1905,6 +1905,30 @@ void btrfs_unpin_extent(struct btrfs_fs_info *fs_info,
 	update_pinned_extents(fs_info, bytenr, num_bytes, 0);
 }
 
+static int do_free_extent_accounting(struct btrfs_trans_handle *trans,
+				     u64 bytenr, u64 num_bytes, bool is_data)
+{
+	int ret, mark_free = 0;
+
+	ret = pin_down_bytes(trans, bytenr, num_bytes, is_data);
+	if (ret > 0)
+		mark_free = 1;
+	else if (ret < 0)
+		return ret;
+
+	if (is_data) {
+		ret = btrfs_del_csums(trans, bytenr, num_bytes);
+		if (ret)
+			return ret;
+	}
+
+	ret = add_to_free_space_tree(trans, bytenr, num_bytes);
+	if (ret)
+		return ret;
+	update_block_group(trans, bytenr, num_bytes, 0, mark_free);
+	return ret;
+}
+
 /*
  * remove an extent from the root, returns 0 on success
  */
@@ -2075,8 +2099,6 @@ static int __free_extent(struct btrfs_trans_handle *trans,
 			BUG_ON(ret);
 		}
 	} else {
-		int mark_free = 0;
-
 		if (found_extent) {
 			BUG_ON(is_data && refs_to_drop !=
 			       extent_data_ref_count(path, iref));
@@ -2089,28 +2111,13 @@ static int __free_extent(struct btrfs_trans_handle *trans,
 			}
 		}
 
-		ret = pin_down_bytes(trans, bytenr, num_bytes,
-				     is_data);
-		if (ret > 0)
-			mark_free = 1;
-		BUG_ON(ret < 0);
-
 		ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
 				      num_to_del);
 		BUG_ON(ret);
 		btrfs_release_path(path);
 
-		if (is_data) {
-			ret = btrfs_del_csums(trans, bytenr, num_bytes);
-			BUG_ON(ret);
-		}
-
-		ret = add_to_free_space_tree(trans, bytenr, num_bytes);
-		if (ret) {
-			goto fail;
-		}
-
-		update_block_group(trans, bytenr, num_bytes, 0, mark_free);
+		ret = do_free_extent_accounting(trans, bytenr, num_bytes, is_data);
+		BUG_ON(ret);
 	}
 fail:
 	btrfs_free_path(path);
-- 
2.26.3

[PATCH 02/15] btrfs-progs: check: skip owner ref check for extent tree v2

[Josef Bacik]

We do not track extent references for metadata in extent tree v2, simply
skip this check if it is enabled.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 check/main.c | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/check/main.c b/check/main.c
index 0eab91b5..c522116e 100644
--- a/check/main.c
+++ b/check/main.c
@@ -4102,6 +4102,13 @@ static int check_owner_ref(struct btrfs_root *root,
 	int found = 0;
 	int ret;
 
+	/*
+	 * We don't have extent references for metadata with extent tree v2,
+	 * just return.
+	 */
+	if (btrfs_fs_incompat(gfs_info, EXTENT_TREE_V2))
+		return 0;
+
 	rbtree_postorder_for_each_entry_safe(node, tmp,
 					     &rec->backref_tree, node) {
 		if (node->is_data)
-- 
2.26.3

[PATCH 03/15] btrfs-progs: check: skip extent backref for metadata in extent tree v2

[Josef Bacik]

We do not track backrefs for metadata in the extent root with extent
tree v2, simply skip adding the backref object.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 check/main.c | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/check/main.c b/check/main.c
index c522116e..ed38709b 100644
--- a/check/main.c
+++ b/check/main.c
@@ -4804,6 +4804,13 @@ static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr,
 	int ret;
 	bool insert = false;
 
+	/*
+	 * There are no extent references for metadata in extent tree v2, skip
+	 * this.
+	 */
+	if (btrfs_fs_incompat(gfs_info, EXTENT_TREE_V2))
+		return 0;
+
 	cache = lookup_cache_extent(extent_cache, bytenr, 1);
 	if (!cache) {
 		struct extent_record tmpl;
-- 
2.26.3

[PATCH 04/15] btrfs-progs: check: calculate normal flags for extent tree v2 metadata

[Josef Bacik]

Metadata in extent tree v2 will not have FULL_BACKREF set, so simply
calculate normal flags for any metadata blocks we find.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 check/main.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/check/main.c b/check/main.c
index ed38709b..1b3ea079 100644
--- a/check/main.c
+++ b/check/main.c
@@ -6172,6 +6172,9 @@ static int calc_extent_flag(struct cache_tree *extent_cache,
 
 	rec = container_of(cache, struct extent_record, cache);
 
+	if (btrfs_fs_incompat(gfs_info, EXTENT_TREE_V2))
+		goto normal;
+
 	/*
 	 * Except file/reloc tree, we can not have
 	 * FULL BACKREF MODE
-- 
2.26.3

[PATCH 05/15] btrfs-progs: check: make metadata ref counting extent tree v2 aware

[Josef Bacik]

We do not want to bother validating extent tree references with tree
block references, so only set the references if extent tree v2 isn't set
so that we do not spit out extent tree errors for extent tree v2.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 check/main.c | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)

diff --git a/check/main.c b/check/main.c
index 1b3ea079..da5aab89 100644
--- a/check/main.c
+++ b/check/main.c
@@ -6622,7 +6622,14 @@ static int run_next_block(struct btrfs_root *root,
 				btrfs_node_ptr_generation(buf, i);
 			tmpl.start = ptr;
 			tmpl.nr = size;
-			tmpl.refs = 1;
+
+			/*
+			 * We do not track refs for metadata in the extent tree,
+			 * do not mark it with a ref count.
+			 */
+			if (!btrfs_fs_incompat(gfs_info, EXTENT_TREE_V2))
+				tmpl.refs = 1;
+
 			tmpl.metadata = 1;
 			tmpl.max_size = size;
 			ret = add_extent_rec(extent_cache, &tmpl);
@@ -6675,7 +6682,14 @@ static int add_root_to_pending(struct extent_buffer *buf,
 	tmpl.start = buf->start;
 	tmpl.nr = buf->len;
 	tmpl.is_root = 1;
-	tmpl.refs = 1;
+
+	/*
+	 * Extent tree v2 does not track references for metadata, do not set
+	 * refs if it is set.
+	 */
+	if (!btrfs_fs_incompat(gfs_info, EXTENT_TREE_V2))
+		tmpl.refs = 1;
+
 	tmpl.metadata = 1;
 	tmpl.max_size = buf->len;
 	add_extent_rec(extent_cache, &tmpl);
-- 
2.26.3

[PATCH 06/15] btrfs-progs: check: update block group used properly for extent tree v2

[Josef Bacik]

For extent tree v2 we do not have metadata tracked in the extent root,
so every block we find we must account for as used in the appropriate
block group.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 check/main.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/check/main.c b/check/main.c
index da5aab89..cee7e7a0 100644
--- a/check/main.c
+++ b/check/main.c
@@ -6412,6 +6412,14 @@ static int run_next_block(struct btrfs_root *root,
 	if (ret)
 		goto out;
 
+	/*
+	 * Extent tree v2 doesn't track metadata in the extent tree, mark any
+	 * blocks we find as used for the block group.
+	 */
+	if (btrfs_fs_incompat(gfs_info, EXTENT_TREE_V2))
+		update_block_group_used(block_group_cache, buf->start,
+					gfs_info->nodesize);
+
 	if (btrfs_is_leaf(buf)) {
 		btree_space_waste += btrfs_leaf_free_space(buf);
 		for (i = 0; i < nritems; i++) {
-- 
2.26.3

[PATCH 07/15] btrfs-progs: do not insert extent items for metadata for extent tree v2

[Josef Bacik]

For extent tree v2 we are no longer tracking metadata blocks in the
extent tree, so simply skip this step and remove the space from the free
space tree and do the block group accounting.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 kernel-shared/extent-tree.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

diff --git a/kernel-shared/extent-tree.c b/kernel-shared/extent-tree.c
index 1af3eb06..7beff7ee 100644
--- a/kernel-shared/extent-tree.c
+++ b/kernel-shared/extent-tree.c
@@ -2392,6 +2392,9 @@ static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
 	sinfo = __find_space_info(fs_info, BTRFS_BLOCK_GROUP_METADATA);
 	ASSERT(sinfo);
 
+	if (btrfs_fs_incompat(fs_info, EXTENT_TREE_V2))
+		goto alloc;
+
 	ins.objectid = node->bytenr;
 	if (skinny_metadata) {
 		ins.offset = ref->level;
@@ -2445,11 +2448,12 @@ static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
 	btrfs_mark_buffer_dirty(leaf);
 	btrfs_free_path(path);
 
-	ret = remove_from_free_space_tree(trans, ins.objectid, fs_info->nodesize);
+alloc:
+	ret = remove_from_free_space_tree(trans, node->bytenr, fs_info->nodesize);
 	if (ret)
 		return ret;
 
-	ret = update_block_group(trans, ins.objectid, fs_info->nodesize, 1, 0);
+	ret = update_block_group(trans, node->bytenr, fs_info->nodesize, 1, 0);
 	if (sinfo) {
 		if (fs_info->nodesize > sinfo->bytes_reserved) {
 			WARN_ON(1);
-- 
2.26.3

[PATCH 08/15] btrfs-progs: do not remove metadata backrefs for extent tree v2

[Josef Bacik]

We do not have backrefs for metadata in extent tree v2, skip this work
in __free_extent() and simply do the update of the accounting and free
space tree.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 kernel-shared/extent-tree.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/kernel-shared/extent-tree.c b/kernel-shared/extent-tree.c
index 7beff7ee..0c0d7bb9 100644
--- a/kernel-shared/extent-tree.c
+++ b/kernel-shared/extent-tree.c
@@ -1961,11 +1961,16 @@ static int __free_extent(struct btrfs_trans_handle *trans,
 						owner_offset, refs_to_drop);
 
 	}
+
+	is_data = owner_objectid >= BTRFS_FIRST_FREE_OBJECTID;
+
+	if (btrfs_fs_incompat(trans->fs_info, EXTENT_TREE_V2) && !is_data)
+		return do_free_extent_accounting(trans, bytenr, num_bytes, false);
+
 	path = btrfs_alloc_path();
 	if (!path)
 		return -ENOMEM;
 
-	is_data = owner_objectid >= BTRFS_FIRST_FREE_OBJECTID;
 	if (is_data)
 		skinny_metadata = 0;
 	BUG_ON(!is_data && refs_to_drop != 1);
-- 
2.26.3

[PATCH 09/15] btrfs-progs: repair: traverse tree blocks for extent tree v2

[Josef Bacik]

If we have extent-tree-v2 enabled we can't only rely on the extent trees
to find all the used space, we have to walk all the trees as well.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 common/repair.c | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/common/repair.c b/common/repair.c
index 9071e627..6784534b 100644
--- a/common/repair.c
+++ b/common/repair.c
@@ -210,6 +210,12 @@ int btrfs_mark_used_blocks(struct btrfs_fs_info *fs_info,
 	struct rb_node *n;
 	int ret;
 
+	if (btrfs_fs_incompat(fs_info, EXTENT_TREE_V2)) {
+		ret = btrfs_mark_used_tree_blocks(fs_info, tree);
+		if (ret)
+			return ret;
+	}
+
 	root = btrfs_extent_root(fs_info, 0);
 	while (1) {
 		ret = populate_used_from_extent_root(root, tree);
-- 
2.26.3

[PATCH 10/15] btrfs-progs: cache the block group with the free space tree if possible

[Josef Bacik]

We currently always cache the block group based on the extent tree in
progs.  However with extent-tree-v2 we will not be able to do this, so
we need to load the free space tree.  However the free space tree is
tied into the normal free space cache, which progs doesn't use for
allocation, instead it uses an extent_io_tree.

Handle this by setting the range dirty in our extent_io_tree.  We still
need to be able to load the free space tree into the normal free space
cache stuff for fsck, so simply bail doing the normal free space cache
adding if block_group->free_space_ctl is NULL, which will be the case
unless we're checking it via check.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 kernel-shared/extent-tree.c      | 14 ++++++++++++++
 kernel-shared/free-space-cache.c |  3 +++
 2 files changed, 17 insertions(+)

diff --git a/kernel-shared/extent-tree.c b/kernel-shared/extent-tree.c
index 0c0d7bb9..1b4e6a02 100644
--- a/kernel-shared/extent-tree.c
+++ b/kernel-shared/extent-tree.c
@@ -102,6 +102,15 @@ static int cache_block_group(struct btrfs_root *root,
 	if (block_group->cached)
 		return 0;
 
+	if (btrfs_fs_compat_ro(root->fs_info, FREE_SPACE_TREE) &&
+	    btrfs_fs_compat_ro(root->fs_info, FREE_SPACE_TREE_VALID)) {
+		ret = load_free_space_tree(root->fs_info, block_group);
+		if (!ret) {
+			block_group->cached = 1;
+			return 0;
+		}
+	}
+
 	path = btrfs_alloc_path();
 	if (!path)
 		return -ENOMEM;
@@ -3594,9 +3603,11 @@ int exclude_super_stripes(struct btrfs_fs_info *fs_info,
 u64 add_new_free_space(struct btrfs_block_group *block_group,
 		       struct btrfs_fs_info *info, u64 start, u64 end)
 {
+	struct extent_io_tree *free_space_cache;
 	u64 extent_start, extent_end, size, total_added = 0;
 	int ret;
 
+	free_space_cache = &info->free_space_cache;
 	while (start < end) {
 		ret = find_first_extent_bit(&info->pinned_extents, start,
 					    &extent_start, &extent_end,
@@ -3609,6 +3620,8 @@ u64 add_new_free_space(struct btrfs_block_group *block_group,
 		} else if (extent_start > start && extent_start < end) {
 			size = extent_start - start;
 			total_added += size;
+			set_extent_dirty(free_space_cache, start,
+					 start + size - 1);
 			ret = btrfs_add_free_space(block_group->free_space_ctl,
 						   start, size);
 			BUG_ON(ret); /* -ENOMEM or logic error */
@@ -3621,6 +3634,7 @@ u64 add_new_free_space(struct btrfs_block_group *block_group,
 	if (start < end) {
 		size = end - start;
 		total_added += size;
+		set_extent_dirty(free_space_cache, start, start + size - 1);
 		ret = btrfs_add_free_space(block_group->free_space_ctl, start,
 					   size);
 		BUG_ON(ret); /* -ENOMEM or logic error */
diff --git a/kernel-shared/free-space-cache.c b/kernel-shared/free-space-cache.c
index e74a61e4..11b7fa60 100644
--- a/kernel-shared/free-space-cache.c
+++ b/kernel-shared/free-space-cache.c
@@ -828,6 +828,9 @@ int btrfs_add_free_space(struct btrfs_free_space_ctl *ctl, u64 offset,
 	struct btrfs_free_space *info;
 	int ret = 0;
 
+	if (!ctl)
+		return 0;
+
 	info = calloc(1, sizeof(*info));
 	if (!info)
 		return -ENOMEM;
-- 
2.26.3

[PATCH 11/15] btrfs-progs: make btrfs_lookup_extent_info extent tree v2 aware

[Josef Bacik]

We do not have flags or refs set on metadata in extent tree v2, make
this helper return the proper things if it is set.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 kernel-shared/extent-tree.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/kernel-shared/extent-tree.c b/kernel-shared/extent-tree.c
index 1b4e6a02..cdfa8f8d 100644
--- a/kernel-shared/extent-tree.c
+++ b/kernel-shared/extent-tree.c
@@ -1309,6 +1309,14 @@ int btrfs_lookup_extent_info(struct btrfs_trans_handle *trans,
 	u64 num_refs;
 	u64 extent_flags;
 
+	if (metadata && btrfs_fs_incompat(fs_info, EXTENT_TREE_V2)) {
+		if (flags)
+			*flags = 0;
+		if (refs)
+			*refs = 0;
+		return 0;
+	}
+
 	if (metadata && !btrfs_fs_incompat(fs_info, SKINNY_METADATA)) {
 		offset = fs_info->nodesize;
 		metadata = 0;
-- 
2.26.3

[PATCH 12/15] btrfs-progs: mkfs: don't populate extent tree with extent tree v2

[Josef Bacik]

If we have extent tree v2 set then we don't track metadata in the extent
tree, and we can skip creating these items at mkfs time.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 mkfs/common.c | 207 +++++++++++++++++++++++++++-----------------------
 1 file changed, 113 insertions(+), 94 deletions(-)

diff --git a/mkfs/common.c b/mkfs/common.c
index a4412a1f..e4435aaa 100644
--- a/mkfs/common.c
+++ b/mkfs/common.c
@@ -233,6 +233,109 @@ static int create_block_group_tree(int fd, struct btrfs_mkfs_config *cfg,
 	return 0;
 }
 
+static int fill_extent_tree(int fd, struct btrfs_mkfs_config *cfg,
+			    struct extent_buffer *buf, u64 bg_offset,
+			    u64 bg_size, u64 bg_used,
+			    const enum btrfs_mkfs_block *blocks, int blocks_nr)
+{
+	struct btrfs_extent_item *extent_item;
+	struct btrfs_disk_key disk_key;
+	u64 first_free, ref_root;
+	u32 nritems = 0, itemoff, item_size;
+	int i, ret, blk;
+	bool add_block_group = true;
+	bool skinny_metadata = !!(cfg->features &
+				  BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA);
+
+	first_free = BTRFS_SUPER_INFO_OFFSET + cfg->sectorsize * 2 - 1;
+	first_free &= ~((u64)cfg->sectorsize - 1);
+
+	/* create the items for the extent tree */
+	memset(buf->data + sizeof(struct btrfs_header), 0,
+		cfg->nodesize - sizeof(struct btrfs_header));
+	itemoff = __BTRFS_LEAF_DATA_SIZE(cfg->nodesize);
+	for (i = 0; i < blocks_nr; i++) {
+		blk = blocks[i];
+
+		/* Add the block group item for our temporary chunk. */
+		if (cfg->blocks[blk] > bg_offset && add_block_group) {
+			itemoff -= sizeof(struct btrfs_block_group_item);
+			write_block_group_item(buf, nritems, bg_offset, bg_size,
+					       bg_used,
+					       BTRFS_FIRST_CHUNK_TREE_OBJECTID,
+					       itemoff);
+			add_block_group = false;
+			nritems++;
+		}
+
+		item_size = sizeof(struct btrfs_extent_item);
+		if (!skinny_metadata)
+			item_size += sizeof(struct btrfs_tree_block_info);
+
+		if (cfg->blocks[blk] < first_free) {
+			error("block[%d] below first free: %llu < %llu",
+					i, (unsigned long long)cfg->blocks[blk],
+					(unsigned long long)first_free);
+			return -EINVAL;
+		}
+		if (i > 0 && cfg->blocks[blk] < cfg->blocks[blocks[i - 1]]) {
+			error("blocks %d and %d in reverse order: %llu < %llu",
+				blk, blocks[i - 1],
+				(unsigned long long)cfg->blocks[blk],
+				(unsigned long long)cfg->blocks[blocks[i - 1]]);
+			return -EINVAL;
+		}
+
+		/* create extent item */
+		itemoff -= item_size;
+		btrfs_set_disk_key_objectid(&disk_key, cfg->blocks[blk]);
+		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_item_key(buf, &disk_key, nritems);
+		btrfs_set_item_offset(buf, btrfs_item_nr(nritems),
+				      itemoff);
+		btrfs_set_item_size(buf, btrfs_item_nr(nritems),
+				    item_size);
+		extent_item = btrfs_item_ptr(buf, nritems,
+					     struct btrfs_extent_item);
+		btrfs_set_extent_refs(buf, extent_item, 1);
+		btrfs_set_extent_generation(buf, extent_item, 1);
+		btrfs_set_extent_flags(buf, extent_item,
+				       BTRFS_EXTENT_FLAG_TREE_BLOCK);
+		nritems++;
+
+		/* create extent ref */
+		ref_root = reference_root_table[blk];
+		btrfs_set_disk_key_objectid(&disk_key, cfg->blocks[blk]);
+		btrfs_set_disk_key_offset(&disk_key, ref_root);
+		btrfs_set_disk_key_type(&disk_key, BTRFS_TREE_BLOCK_REF_KEY);
+		btrfs_set_item_key(buf, &disk_key, nritems);
+		btrfs_set_item_offset(buf, btrfs_item_nr(nritems),
+				      itemoff);
+		btrfs_set_item_size(buf, btrfs_item_nr(nritems), 0);
+		nritems++;
+	}
+	btrfs_set_header_bytenr(buf, cfg->blocks[MKFS_EXTENT_TREE]);
+	btrfs_set_header_owner(buf, BTRFS_EXTENT_TREE_OBJECTID);
+	btrfs_set_header_nritems(buf, nritems);
+	csum_tree_block_size(buf, btrfs_csum_type_size(cfg->csum_type), 0,
+			     cfg->csum_type);
+	ret = btrfs_pwrite(fd, buf->data, cfg->nodesize,
+			   cfg->blocks[MKFS_EXTENT_TREE], cfg->zone_size);
+	if (ret != cfg->nodesize)
+		ret = (ret < 0 ? -errno : -EIO);
+	else
+		ret = 0;
+	return ret;
+}
+
 /*
  * @fs_uuid - if NULL, generates a UUID, returns back the new filesystem UUID
  *
@@ -259,7 +362,6 @@ int make_btrfs(int fd, struct btrfs_mkfs_config *cfg)
 	struct btrfs_super_block super;
 	struct extent_buffer *buf;
 	struct btrfs_disk_key disk_key;
-	struct btrfs_extent_item *extent_item;
 	struct btrfs_chunk *chunk;
 	struct btrfs_dev_item *dev_item;
 	struct btrfs_dev_extent *dev_extent;
@@ -272,17 +374,12 @@ int make_btrfs(int fd, struct btrfs_mkfs_config *cfg)
 	int blk;
 	u32 itemoff;
 	u32 nritems = 0;
-	u64 first_free;
-	u64 ref_root;
 	u32 array_size;
 	u32 item_size;
 	u64 total_used = 0;
-	int skinny_metadata = !!(cfg->features &
-				 BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA);
 	u64 num_bytes;
 	u64 system_group_offset = BTRFS_BLOCK_RESERVED_1M_FOR_SUPER;
 	u64 system_group_size = BTRFS_MKFS_SYSTEM_GROUP_SIZE;
-	bool add_block_group = true;
 	bool free_space_tree = !!(cfg->runtime_features &
 				  BTRFS_RUNTIME_FEATURE_FREE_SPACE_TREE);
 	bool extent_tree_v2 = !!(cfg->features &
@@ -295,7 +392,6 @@ int make_btrfs(int fd, struct btrfs_mkfs_config *cfg)
 	if (extent_tree_v2) {
 		blocks = extent_tree_v2_blocks;
 		blocks_nr = ARRAY_SIZE(extent_tree_v2_blocks);
-		add_block_group = false;
 	}
 
 	if ((cfg->features & BTRFS_FEATURE_INCOMPAT_ZONED)) {
@@ -307,9 +403,6 @@ int make_btrfs(int fd, struct btrfs_mkfs_config *cfg)
 	if (!buf)
 		return -ENOMEM;
 
-	first_free = BTRFS_SUPER_INFO_OFFSET + cfg->sectorsize * 2 - 1;
-	first_free &= ~((u64)cfg->sectorsize - 1);
-
 	memset(&super, 0, sizeof(super));
 
 	num_bytes = (cfg->num_bytes / cfg->sectorsize) * cfg->sectorsize;
@@ -390,92 +483,18 @@ int make_btrfs(int fd, struct btrfs_mkfs_config *cfg)
 	if (ret < 0)
 		goto out;
 
-	/* create the items for the extent tree */
-	memset(buf->data + sizeof(struct btrfs_header), 0,
-		cfg->nodesize - sizeof(struct btrfs_header));
-	nritems = 0;
-	itemoff = __BTRFS_LEAF_DATA_SIZE(cfg->nodesize);
-	for (i = 0; i < blocks_nr; i++) {
-		blk = blocks[i];
-
-		/* Add the block group item for our temporary chunk. */
-		if (cfg->blocks[blk] > system_group_offset && add_block_group) {
-			itemoff -= sizeof(struct btrfs_block_group_item);
-			write_block_group_item(buf, nritems,
-					       system_group_offset,
-					       system_group_size, total_used,
-					       BTRFS_FIRST_CHUNK_TREE_OBJECTID,
-					       itemoff);
-			add_block_group = false;
-			nritems++;
-		}
-
-		item_size = sizeof(struct btrfs_extent_item);
-		if (!skinny_metadata)
-			item_size += sizeof(struct btrfs_tree_block_info);
-
-		if (cfg->blocks[blk] < first_free) {
-			error("block[%d] below first free: %llu < %llu",
-					i, (unsigned long long)cfg->blocks[blk],
-					(unsigned long long)first_free);
-			ret = -EINVAL;
+	if (extent_tree_v2) {
+		ret = btrfs_write_empty_tree(fd, cfg, buf,
+					     BTRFS_EXTENT_TREE_OBJECTID,
+					     cfg->blocks[MKFS_EXTENT_TREE]);
+		if (ret)
 			goto out;
-		}
-		if (i > 0 && cfg->blocks[blk] < cfg->blocks[blocks[i - 1]]) {
-			error("blocks %d and %d in reverse order: %llu < %llu",
-				blk, blocks[i - 1],
-				(unsigned long long)cfg->blocks[blk],
-				(unsigned long long)cfg->blocks[blocks[i - 1]]);
-			ret = -EINVAL;
+	} else {
+		ret = fill_extent_tree(fd, cfg, buf, system_group_offset,
+				       system_group_size, total_used, blocks,
+				       blocks_nr);
+		if (ret)
 			goto out;
-		}
-
-		/* create extent item */
-		itemoff -= item_size;
-		btrfs_set_disk_key_objectid(&disk_key, cfg->blocks[blk]);
-		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_item_key(buf, &disk_key, nritems);
-		btrfs_set_item_offset(buf, btrfs_item_nr(nritems),
-				      itemoff);
-		btrfs_set_item_size(buf, btrfs_item_nr(nritems),
-				    item_size);
-		extent_item = btrfs_item_ptr(buf, nritems,
-					     struct btrfs_extent_item);
-		btrfs_set_extent_refs(buf, extent_item, 1);
-		btrfs_set_extent_generation(buf, extent_item, 1);
-		btrfs_set_extent_flags(buf, extent_item,
-				       BTRFS_EXTENT_FLAG_TREE_BLOCK);
-		nritems++;
-
-		/* create extent ref */
-		ref_root = reference_root_table[blk];
-		btrfs_set_disk_key_objectid(&disk_key, cfg->blocks[blk]);
-		btrfs_set_disk_key_offset(&disk_key, ref_root);
-		btrfs_set_disk_key_type(&disk_key, BTRFS_TREE_BLOCK_REF_KEY);
-		btrfs_set_item_key(buf, &disk_key, nritems);
-		btrfs_set_item_offset(buf, btrfs_item_nr(nritems),
-				      itemoff);
-		btrfs_set_item_size(buf, btrfs_item_nr(nritems), 0);
-		nritems++;
-	}
-	btrfs_set_header_bytenr(buf, cfg->blocks[MKFS_EXTENT_TREE]);
-	btrfs_set_header_owner(buf, BTRFS_EXTENT_TREE_OBJECTID);
-	btrfs_set_header_nritems(buf, nritems);
-	csum_tree_block_size(buf, btrfs_csum_type_size(cfg->csum_type), 0,
-			     cfg->csum_type);
-	ret = btrfs_pwrite(fd, buf->data, cfg->nodesize,
-			   cfg->blocks[MKFS_EXTENT_TREE], cfg->zone_size);
-	if (ret != cfg->nodesize) {
-		ret = (ret < 0 ? -errno : -EIO);
-		goto out;
 	}
 
 	/* create the chunk tree */
-- 
2.26.3

[PATCH 13/15] btrfs-progs: add on-disk items and read support for the gc tree

[Josef Bacik]

This add's the necessary on disk structures for the initial garbage
collection tree.  At first we're going to just add orphan item support,
and then add other items as the support lands for those new operations.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 kernel-shared/ctree.h      | 6 ++++++
 kernel-shared/disk-io.c    | 5 +++++
 kernel-shared/print-tree.c | 4 ++++
 3 files changed, 15 insertions(+)

diff --git a/kernel-shared/ctree.h b/kernel-shared/ctree.h
index 82a4a2eb..bfb59fa3 100644
--- a/kernel-shared/ctree.h
+++ b/kernel-shared/ctree.h
@@ -88,6 +88,9 @@ struct btrfs_free_space_ctl;
 /* hold the block group items. */
 #define BTRFS_BLOCK_GROUP_TREE_OBJECTID 11ULL
 
+/* hold the garbage collection items. */
+#define BTRFS_GC_TREE_OBJECTID 12ULL
+
 /* device stats in the device tree */
 #define BTRFS_DEV_STATS_OBJECTID 0ULL
 
@@ -1356,6 +1359,9 @@ static inline u32 BTRFS_MAX_XATTR_SIZE(const struct btrfs_fs_info *info)
 #define BTRFS_XATTR_ITEM_KEY		24
 #define BTRFS_ORPHAN_ITEM_KEY		48
 
+/* Garbage collection items. */
+#define BTRFS_GC_INODE_ITEM_KEY		49
+
 #define BTRFS_DIR_LOG_ITEM_KEY  60
 #define BTRFS_DIR_LOG_INDEX_KEY 72
 /*
diff --git a/kernel-shared/disk-io.c b/kernel-shared/disk-io.c
index 40097930..ec838221 100644
--- a/kernel-shared/disk-io.c
+++ b/kernel-shared/disk-io.c
@@ -1158,6 +1158,11 @@ static int load_global_roots(struct btrfs_fs_info *fs_info, unsigned flags)
 	ret = load_global_roots_objectid(fs_info, path,
 					 BTRFS_FREE_SPACE_TREE_OBJECTID, flags,
 					 "free space");
+	if (ret)
+		goto out;
+	ret = load_global_roots_objectid(fs_info, path,
+					 BTRFS_GC_TREE_OBJECTID, flags,
+					 "garbage collection");
 out:
 	btrfs_free_path(path);
 	return ret;
diff --git a/kernel-shared/print-tree.c b/kernel-shared/print-tree.c
index a612c3d9..9d0d9cea 100644
--- a/kernel-shared/print-tree.c
+++ b/kernel-shared/print-tree.c
@@ -678,6 +678,7 @@ void print_key_type(FILE *stream, u64 objectid, u8 type)
 		[BTRFS_PERSISTENT_ITEM_KEY]	= "PERSISTENT_ITEM",
 		[BTRFS_UUID_KEY_SUBVOL]		= "UUID_KEY_SUBVOL",
 		[BTRFS_UUID_KEY_RECEIVED_SUBVOL] = "UUID_KEY_RECEIVED_SUBVOL",
+		[BTRFS_GC_INODE_ITEM_KEY]	= "GC_INODE_ITEM_KEY",
 	};
 
 	if (type == 0 && objectid == BTRFS_FREE_SPACE_OBJECTID) {
@@ -787,6 +788,9 @@ void print_objectid(FILE *stream, u64 objectid, u8 type)
 	case BTRFS_BLOCK_GROUP_TREE_OBJECTID:
 		fprintf(stream, "BLOCK_GROUP_TREE");
 		break;
+	case BTRFS_GC_TREE_OBJECTID:
+		fprintf(stream, "GC_TREE");
+		break;
 	case (u64)-1:
 		fprintf(stream, "-1");
 		break;
-- 
2.26.3

[PATCH 14/15] btrfs-progs: mkfs: create the gc tree at mkfs time

[Josef Bacik]

Now that progs has the support to read this tree, create it at global
root creation time.  We don't need this root to bootstrap the file
system so just create it at this later point.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 mkfs/main.c | 13 ++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)

diff --git a/mkfs/main.c b/mkfs/main.c
index beed511c..2d18e514 100644
--- a/mkfs/main.c
+++ b/mkfs/main.c
@@ -839,7 +839,18 @@ static int create_global_roots(struct btrfs_trans_handle *trans,
 {
 	int ret, i;
 
-	for (i = 1; i < nr_global_roots; i++) {
+	for (i = 0; i < nr_global_roots; i++) {
+		ret = create_global_root(trans, BTRFS_GC_TREE_OBJECTID, i);
+		if (ret)
+			return ret;
+
+		/*
+		 * The rest of these are created initially so we want to skip
+		 * root id == 0 for them.
+		 */
+		if (i == 0)
+			continue;
+
 		ret = create_global_root(trans, BTRFS_EXTENT_TREE_OBJECTID, i);
 		if (ret)
 			return ret;
-- 
2.26.3

[PATCH 15/15] btrfs-progs: deal with GC items in check

[Josef Bacik]

If we have a GC item then we can treat the inode record like it has an
ORPHAN item, simply ignore it if we have either the ORPHAN item or the
GC item.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 check/main.c          | 55 ++++++++++++++++++++++++++++++++++++++++---
 check/mode-original.h |  1 +
 2 files changed, 53 insertions(+), 3 deletions(-)

diff --git a/check/main.c b/check/main.c
index cee7e7a0..16a27a5a 100644
--- a/check/main.c
+++ b/check/main.c
@@ -627,6 +627,8 @@ static void print_inode_error(struct btrfs_root *root, struct inode_record *rec)
 	if (errors & I_ERR_INVALID_NLINK)
 		fprintf(stderr, ", directory has invalid nlink %d",
 			rec->nlink);
+	if (errors & I_ERR_NO_GC_ITEM)
+		fprintf(stderr, ", no gc item");
 	fprintf(stderr, "\n");
 
 	/* Print the holes if needed */
@@ -884,6 +886,42 @@ static int check_orphan_item(struct btrfs_root *root, u64 ino)
 	return ret;
 }
 
+static void check_inode_gc_item(struct btrfs_root *root, struct inode_record *rec)
+{
+	struct btrfs_root *gc_root;
+	struct rb_node *n;
+	struct btrfs_path path;
+	struct btrfs_key key = {
+		.objectid = root->root_key.objectid,
+		.type = BTRFS_GC_INODE_ITEM_KEY,
+		.offset = rec->ino,
+	};
+	int ret;
+
+	/*
+	 * We may choose to do something fancy with the location of our
+	 * GC_INODE_ITEM entries, so just search all of the gc roots for our
+	 * inode.
+	 */
+	for (n = rb_first(&gfs_info->global_roots_tree); n; n = rb_next(n)) {
+		gc_root = rb_entry(n, struct btrfs_root, rb_node);
+		if (gc_root->root_key.objectid != BTRFS_GC_TREE_OBJECTID)
+			continue;
+		btrfs_init_path(&path);
+		ret = btrfs_search_slot(NULL, gc_root, &key, &path, 0, 0);
+		btrfs_release_path(&path);
+
+		/*
+		 * Found our GC item, that means we don't need an orphan item so
+		 * we can clear both of these errors.
+		 */
+		if (ret == 0) {
+			rec->errors &= ~(I_ERR_NO_GC_ITEM | I_ERR_NO_ORPHAN_ITEM);
+			break;
+		}
+	}
+}
+
 static int process_inode_item(struct extent_buffer *eb,
 			      int slot, struct btrfs_key *key,
 			      struct shared_node *active_node)
@@ -907,8 +945,11 @@ static int process_inode_item(struct extent_buffer *eb,
 	if (btrfs_inode_flags(eb, item) & BTRFS_INODE_NODATASUM)
 		rec->nodatasum = 1;
 	rec->found_inode_item = 1;
-	if (rec->nlink == 0)
+	if (rec->nlink == 0) {
 		rec->errors |= I_ERR_NO_ORPHAN_ITEM;
+		if (btrfs_fs_incompat(gfs_info, EXTENT_TREE_V2))
+			rec->errors |= I_ERR_NO_GC_ITEM;
+	}
 	flags = btrfs_inode_flags(eb, item);
 	if (S_ISLNK(rec->imode) &&
 	    flags & (BTRFS_INODE_IMMUTABLE | BTRFS_INODE_APPEND))
@@ -2571,7 +2612,7 @@ static int repair_inode_no_item(struct btrfs_trans_handle *trans,
 	rec->found_dir_item = 1;
 	rec->imode = mode | btrfs_type_to_imode(filetype);
 	rec->nlink = 0;
-	rec->errors &= ~I_ERR_NO_INODE_ITEM;
+	rec->errors &= ~(I_ERR_NO_INODE_ITEM | I_ERR_NO_GC_ITEM);
 	/* Ensure the inode_nlinks repair function will be called */
 	rec->errors |= I_ERR_LINK_COUNT_WRONG;
 out:
@@ -3085,8 +3126,16 @@ static int check_inode_recs(struct btrfs_root *root,
 
 		if (rec->errors & I_ERR_NO_ORPHAN_ITEM) {
 			ret = check_orphan_item(root, rec->ino);
+
+			/*
+			 * If we have an orphan item we need to not have a gc
+			 * item.
+			 */
 			if (ret == 0)
-				rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
+				rec->errors &= ~(I_ERR_NO_ORPHAN_ITEM |
+						 I_ERR_NO_GC_ITEM);
+
+			check_inode_gc_item(root, rec);
 			if (can_free_inode_rec(rec)) {
 				free_inode_rec(rec);
 				continue;
diff --git a/check/mode-original.h b/check/mode-original.h
index cf06917c..b93d7cca 100644
--- a/check/mode-original.h
+++ b/check/mode-original.h
@@ -187,6 +187,7 @@ struct unaligned_extent_rec_t {
 #define I_ERR_INVALID_IMODE		(1 << 19)
 #define I_ERR_INVALID_GEN		(1 << 20)
 #define I_ERR_INVALID_NLINK		(1 << 21)
+#define I_ERR_NO_GC_ITEM		(1 << 22)
 
 struct inode_record {
 	struct list_head backrefs;
-- 
2.26.3