Skip to contentSkip to conversation

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

PATCH Superseded Josef Bacik 1 participant 16 messages Dec 15, 2021 Btrfs file system

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

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

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(-)
Signature · 1 line
2.26.3
#1 lore raw

PATCH 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 1469f5c3..1af3eb06 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 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 0eab91b5..c522116e 100644
@@ -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)
Signature · 1 line
2.26.3
#3 lore raw

PATCH 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 c522116e..ed38709b 100644
@@ -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;
Signature · 1 line
2.26.3
#4 lore raw

PATCH 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 ed38709b..1b3ea079 100644
@@ -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
Signature · 1 line
2.26.3
#5 lore raw

PATCH 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 1b3ea079..da5aab89 100644
@@ -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);
Signature · 1 line
2.26.3
#6 lore raw

PATCH 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 da5aab89..cee7e7a0 100644
@@ -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++) {
Signature · 1 line
2.26.3
#7 lore raw

PATCH 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 1af3eb06..7beff7ee 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 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 7beff7ee..0c0d7bb9 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 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 9071e627..6784534b 100644
@@ -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);
Signature · 1 line
2.26.3
#10 lore raw

PATCH 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 0c0d7bb9..1b4e6a02 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 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 1b4e6a02..cdfa8f8d 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 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 | 207 +++++++++++++++++++++++++++-----------------------
 1 file changed, 113 insertions(+), 94 deletions(-)
mkfs/common.c +113 -94
index a4412a1f..e4435aaa 100644
@@ -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 */
Signature · 1 line
2.26.3
#13 lore raw

PATCH 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    | 5 +++++
 kernel-shared/print-tree.c | 4 ++++
 3 files changed, 15 insertions(+)
kernel-shared/ctree.h +6 -0
index 82a4a2eb..bfb59fa3 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
 
@@ -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
 /*
kernel-shared/disk-io.c +5 -0
index 40097930..ec838221 100644
@@ -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;
kernel-shared/print-tree.c +4 -0
index a612c3d9..9d0d9cea 100644
@@ -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;
Signature · 1 line
2.26.3
#14 lore raw

PATCH 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 beed511c..2d18e514 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 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 cee7e7a0..16a27a5a 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))
@@ -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;
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