Skip to contentSkip to conversation

btrfs-progs: extent tree v2 gc tree and metadata ref changes

PATCH New Josef Bacik 1 participant 16 messages Mar 7, 2022 Btrfs file system

lore
Share & tools
lore
#0 lore raw

v2 cover btrfs-progs: extent tree v2 gc tree and metadata ref changes

v1->v2:
- rebased onto devel, depends on "[PATCH v5 00/19] btrfs-progs: extent tree v2 support, global roots"

--- Original email ---

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          |  10 ++
 kernel-shared/extent-tree.c      |  82 +++++++++----
 kernel-shared/free-space-cache.c |   3 +
 kernel-shared/print-tree.c       |   4 +
 mkfs/common.c                    | 201 +++++++++++++++++--------------
 mkfs/main.c                      |  13 +-
 10 files changed, 305 insertions(+), 119 deletions(-)
Signature · 1 line
2.26.3
#1 lore raw

PATCH v2 1/15 btrfs-progs: extract out free extent accounting handling

__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.

---
 kernel-shared/extent-tree.c | 45 +++++++++++++++++++++----------------
 1 file changed, 26 insertions(+), 19 deletions(-)
kernel-shared/extent-tree.c +26 -19
index 697a8a1e..0db0f32d 100644
@@ -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);
Signature · 1 line
2.26.3
#2 lore raw

PATCH v2 2/15 btrfs-progs: check: skip owner ref check for extent tree v2

In reply to Josef Bacik

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

---
 check/main.c | 7 +++++++
 1 file changed, 7 insertions(+)
check/main.c +7 -0
index 6bedd648..2ab68248 100644
@@ -4099,6 +4099,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)
Signature · 1 line
2.26.3
#3 lore raw

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

In reply to Josef Bacik

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

---
 check/main.c | 7 +++++++
 1 file changed, 7 insertions(+)
check/main.c +7 -0
index 2ab68248..b5d08280 100644
@@ -4798,6 +4798,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;
Signature · 1 line
2.26.3
#4 lore raw

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

In reply to Josef Bacik

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

---
 check/main.c | 3 +++
 1 file changed, 3 insertions(+)
check/main.c +3 -0
index b5d08280..420453e0 100644
@@ -6185,6 +6185,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
Signature · 1 line
2.26.3
#5 lore raw

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

In reply to 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.

---
 check/main.c | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)
check/main.c +16 -2
index 420453e0..5fb765c5 100644
@@ -6635,7 +6635,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);
@@ -6688,7 +6695,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);
Signature · 1 line
2.26.3
#6 lore raw

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

In reply to 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.

---
 check/main.c | 8 ++++++++
 1 file changed, 8 insertions(+)
check/main.c +8 -0
index 5fb765c5..aab6b3a0 100644
@@ -6425,6 +6425,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++) {
Signature · 1 line
2.26.3
#7 lore raw

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

In reply to 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.

---
 kernel-shared/extent-tree.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)
kernel-shared/extent-tree.c +6 -2
index 0db0f32d..89b286c6 100644
@@ -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);
Signature · 1 line
2.26.3
#8 lore raw

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

In reply to 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.

---
 kernel-shared/extent-tree.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
kernel-shared/extent-tree.c +6 -1
index 89b286c6..61c53ad2 100644
@@ -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);
Signature · 1 line
2.26.3
#9 lore raw

PATCH v2 9/15 btrfs-progs: repair: traverse tree blocks for extent tree v2

In reply to 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.

---
 common/repair.c | 6 ++++++
 1 file changed, 6 insertions(+)
common/repair.c +6 -0
index 37a6943f..db462955 100644
@@ -219,6 +219,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);
Signature · 1 line
2.26.3
#10 lore raw

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

In reply to 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.

---
 kernel-shared/extent-tree.c      | 14 ++++++++++++++
 kernel-shared/free-space-cache.c |  3 +++
 2 files changed, 17 insertions(+)
kernel-shared/extent-tree.c +14 -0
index 61c53ad2..8921dd07 100644
@@ -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 */
kernel-shared/free-space-cache.c +3 -0
index e74a61e4..11b7fa60 100644
@@ -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;
Signature · 1 line
2.26.3
#11 lore raw

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

In reply to 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.

---
 kernel-shared/extent-tree.c | 8 ++++++++
 1 file changed, 8 insertions(+)
kernel-shared/extent-tree.c +8 -0
index 8921dd07..933e8209 100644
@@ -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;
Signature · 1 line
2.26.3
#12 lore raw

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

In reply to 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.

---
 mkfs/common.c | 201 +++++++++++++++++++++++++++-----------------------
 1 file changed, 110 insertions(+), 91 deletions(-)
mkfs/common.c +110 -91
index 75680d03..2e13da17 100644
@@ -232,6 +232,106 @@ 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 = cfg->leaf_data_size;
+	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, nritems, itemoff);
+		btrfs_set_item_size(buf, 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, nritems, itemoff);
+		btrfs_set_item_size(buf, 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
  *
@@ -258,7 +358,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;
@@ -271,17 +370,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 &
@@ -294,7 +388,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)) {
@@ -306,9 +399,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;
@@ -381,89 +471,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 = cfg->leaf_data_size;
-	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, nritems, itemoff);
-		btrfs_set_item_size(buf, 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, nritems, itemoff);
-		btrfs_set_item_size(buf, 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 */
Signature · 1 line
2.26.3
#13 lore raw

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

In reply to 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.

---
 kernel-shared/ctree.h      |  6 ++++++
 kernel-shared/disk-io.c    | 10 ++++++++++
 kernel-shared/print-tree.c |  4 ++++
 3 files changed, 20 insertions(+)
kernel-shared/ctree.h +6 -0
index d79f49c9..72c87485 100644
@@ -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
 
@@ -1362,6 +1365,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
 /*
kernel-shared/disk-io.c +10 -0
index 4964cd38..35422d8c 100644
@@ -1222,6 +1222,16 @@ 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;
+	if (!btrfs_fs_incompat(fs_info, EXTENT_TREE_V2))
+		goto out;
+	/* We are from mkfs, we haven't setup the GC tree yet. */
+	if (flags & OPEN_CTREE_TEMPORARY_SUPER)
+		goto out;
+	ret = load_global_roots_objectid(fs_info, path,
+					 BTRFS_GC_TREE_OBJECTID, flags,
+					 "garbage collection");
 out:
 	btrfs_free_path(path);
 	return ret;
kernel-shared/print-tree.c +4 -0
index 978d92bc..554cc641 100644
@@ -677,6 +677,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) {
@@ -786,6 +787,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;
Signature · 1 line
2.26.3
#14 lore raw

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

In reply to 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.

---
 mkfs/main.c | 13 ++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)
mkfs/main.c +12 -1
index a603ec58..17b3efc1 100644
@@ -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;
Signature · 1 line
2.26.3
#15 lore raw

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

In reply to 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.

---
 check/main.c          | 55 ++++++++++++++++++++++++++++++++++++++++---
 check/mode-original.h |  1 +
 2 files changed, 53 insertions(+), 3 deletions(-)
check/main.c +52 -3
index aab6b3a0..c5ffd652 100644
@@ -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))
@@ -2569,7 +2610,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:
@@ -3082,8 +3123,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;
check/mode-original.h +1 -0
index cf06917c..b93d7cca 100644
@@ -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;
Signature · 1 line
2.26.3