[PATCH RFC 00/16] Introduce low memory usage btrfsck mode

[PATCH RFC 00/16] Introduce low memory usage btrfsck mode

[Qu Wenruo]

The branch can be fetched from my github:
https://github.com/adam900710/btrfs-progs.git low_mem_fsck_rebasing

Original btrfsck checks extent tree in a very efficient method, by
recording every checked extent in extent record tree to ensure every
extent will be iterated for at most 2 times.

However extent records are all stored in heap memory, and consider how
large a btrfs file system can be, it can easily eat up all memory and
cause OOM for TB-sized metadata.

Instead of such heap memory usage, we introduce low memory usage fsck
mode.

In this mode, we will use btrfs_search_slot() only and avoid any heap
memory allocation.

The work flow is:
1) Iterate extent tree (backref check)
   And check whether the referencer of every backref exists.

2) Iterate other trees (forward ref check)
   And check whether the backref of every tree block/data exists in
   extent tree.

So in theory, every extent is iterated twice just as original one.
But since we don't have extent record, but use btrfs_search_slot() every
time we check, it will cause extra IO.

I assume the extra IO is reasonable and should make btrfsck able to
handle super large fs.

TODO features:
1) Repair
   Repair should be the same as old btrfsck, but still need to determine
   the repair principle.
   Current repair sometimes uses backref to repair data extent,
   sometimes uses data extent to fix backref.
   We need a consistent principle, or we will screw things up.

2) Replace current fsck code
   We assume the low memory mode has less lines of code, and may be
   easier for review and expand.

   If low memory mode is stable enough, we will consider to replace
   current extent and chunk tree check codes to free a lot of lines.

3) Further code refining
   Reduce duplicated codes

4) Unify output
   Make the output of low-memory mode same as the normal one.

Lu Fengqi (16):
  btrfs-progs: fsck: Introduce function to check tree block backref in
    extent tree
  btrfs-progs: fsck: Introduce function to check data backref in extent
    tree
  btrfs-progs: fsck: Introduce function to query tree block level
  btrfs-progs: fsck: Introduce function to check referencer of a backref
  btrfs-progs: fsck: Introduce function to check shared block ref
  btrfs-progs: fsck: Introduce function to check referencer for data
    backref
  btrfs-progs: fsck: Introduce function to check shared data backref
  btrfs-progs: fsck: Introduce function to check an extent
  btrfs-progs: fsck: Introduce function to check dev extent item
  btrfs-progs: fsck: Introduce function to check dev used space
  btrfs-progs: fsck: Introduce function to check block group item
  btrfs-progs: fsck: Introduce function to check chunk item
  btrfs-progs: fsck: Introduce hub function for later fsck
  btrfs-progs: fsck: Introduce function to speed up fs tree check
  btrfs-progs: fsck: Introduce traversal function for fsck
  btrfs-progs: fsck: Introduce low memory mode

 Documentation/btrfs-check.asciidoc |    2 +
 cmds-check.c                       | 1667 +++++++++++++++++++++++++++++++++---
 ctree.h                            |    2 +
 extent-tree.c                      |    2 +-
 4 files changed, 1536 insertions(+), 137 deletions(-)

-- 
2.8.0

[PATCH RFC 01/16] btrfs-progs: fsck: Introduce function to check tree block backref in extent tree

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce function check_tree_block_ref() to check whether a tree block
has correct backref in extent tree.

Unlike old extent tree check method, we only use search_slot() to search
reference, no extra structure will be allocated in heap to record what we
have checked.

This method may cause a little more IO, but should work for super large
fs without triggering OOM.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 163 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 163 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index d59968b..27fc26f 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -313,6 +313,16 @@ struct root_item_info {
 	struct cache_extent cache_extent;
 };
 
+/*
+ * Error bit for low memory mode check.
+ * Return value should be - (ERR_BIT1 | ERR_BIT2 | ...)
+ *
+ * Current no caller cares about it yet.
+ * Just as an internal use error classification
+ */
+#define MISSING_BACKREF	(1 << 0) /* Completely no backref in extent tree */
+#define BAD_BACKREF	(1 << 1) /* Backref mismatch */
+
 static void *print_status_check(void *p)
 {
 	struct task_ctx *priv = p;
@@ -8402,6 +8412,159 @@ loop:
 	goto again;
 }
 
+/*
+ * Check backrefs of a tree block given by @bytenr or @eb.
+ *
+ * @root:	the root containin the @bytenr or @eb
+ * @eb:		tree block extent buffer, can be NULL
+ * @bytenr:	bytenr of the tree block to search
+ * @level:	tree level of the tree block
+ * @owner:	owner of the tree block
+ *
+ * Return < 0 for any error found and output error message
+ * Return 0 for no error found
+ */
+static int check_tree_block_ref(struct btrfs_root *root,
+				struct extent_buffer *eb, u64 bytenr,
+				int level, u64 owner)
+{
+	struct btrfs_key key;
+	struct btrfs_key found_key;
+	struct btrfs_root *extent_root = root->fs_info->extent_root;
+	struct btrfs_path path;
+	struct btrfs_extent_item *ei;
+	struct btrfs_extent_inline_ref *iref;
+	struct extent_buffer *leaf;
+	unsigned long end;
+	unsigned long ptr;
+	int slot;
+	int skinny_level;
+	int type;
+	u32 nodesize = root->nodesize;
+	u32 item_size;
+	u64 offset;
+	int found_ref = 0;
+	int err = 0;
+	int ret;
+
+	btrfs_init_path(&path);
+	key.objectid = bytenr;
+	if (btrfs_fs_incompat(root->fs_info,
+			      BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA))
+		key.type = BTRFS_METADATA_ITEM_KEY;
+	else
+		key.type = BTRFS_EXTENT_ITEM_KEY;
+	key.offset = (u64)-1;
+
+	/* Search for the backref in extent tree */
+	ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
+	if (ret < 0) {
+		err = MISSING_BACKREF;
+		goto out;
+	}
+	ret = btrfs_previous_extent_item(extent_root, &path, bytenr);
+	if (ret) {
+		err = MISSING_BACKREF;
+		goto out;
+	}
+
+	leaf = path.nodes[0];
+	slot = path.slots[0];
+	btrfs_item_key_to_cpu(leaf, &found_key, slot);
+
+	ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
+
+	if (btrfs_key_type(&found_key) == BTRFS_METADATA_ITEM_KEY) {
+		skinny_level = (int)found_key.offset;
+		iref = (struct btrfs_extent_inline_ref *)(ei + 1);
+	} else {
+		struct btrfs_tree_block_info *info;
+
+		info = (struct btrfs_tree_block_info *)(ei + 1);
+		skinny_level = btrfs_tree_block_level(leaf, info);
+		iref = (struct btrfs_extent_inline_ref *)(info + 1);
+	}
+
+	if (eb) {
+		u64 header_gen;
+		u64 extent_gen;
+
+		if (!(btrfs_extent_flags(leaf, ei) &
+		      BTRFS_EXTENT_FLAG_TREE_BLOCK)) {
+			error("Extent[%llu %u] backref type mismatch, missing bit: %llx",
+			      found_key.objectid, nodesize,
+			      BTRFS_EXTENT_FLAG_TREE_BLOCK);
+			err = BAD_BACKREF;
+		}
+		header_gen = btrfs_header_generation(eb);
+		extent_gen = btrfs_extent_generation(leaf, ei);
+		if (header_gen != extent_gen) {
+			error("Extent[%llu %u] backref generation mismatch, wanted: %llu, have: %llu",
+			      found_key.objectid, nodesize, header_gen,
+			      extent_gen);
+			err = BAD_BACKREF;
+		}
+		if (level != skinny_level) {
+			error("Extent[%llu %u] level mismatch, wanted: %u, have: %u",
+			      found_key.objectid, nodesize, level, skinny_level);
+			err = BAD_BACKREF;
+		}
+		if (!is_fstree(owner) && btrfs_extent_refs(leaf, ei) != 1) {
+			error("Extent[%llu %u] is referred by other roots than %llu",
+			      found_key.objectid, nodesize, root->objectid);
+			err = BAD_BACKREF;
+		}
+	}
+
+	/*
+	 * Iterate the extent/metadata item to find the exact backref
+	 */
+	item_size = btrfs_item_size_nr(leaf, slot);
+	ptr = (unsigned long)iref;
+	end = (unsigned long)ei + item_size;
+	while (ptr < end) {
+		iref = (struct btrfs_extent_inline_ref *)ptr;
+		type = btrfs_extent_inline_ref_type(leaf, iref);
+		offset = btrfs_extent_inline_ref_offset(leaf, iref);
+
+		if (type == BTRFS_TREE_BLOCK_REF_KEY &&
+			(offset == root->objectid || offset == owner)) {
+			found_ref = 1;
+		} else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
+			/* Check if the backref points to valid referencer */
+			found_ref = !check_tree_block_ref(root, NULL, offset,
+							  level + 1, owner);
+		}
+
+		if (found_ref)
+			break;
+		ptr += btrfs_extent_inline_ref_size(type);
+	}
+
+	/*
+	 * Inlined extent item doesn't have what we need, check
+	 * TREE_BLOCK_REF_KEY
+	 */
+	if (!found_ref) {
+		btrfs_release_path(&path);
+		key.objectid = bytenr;
+		key.type = BTRFS_TREE_BLOCK_REF_KEY;
+		key.offset = root->objectid;
+
+		ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
+		if (!ret)
+			found_ref = 1;
+	}
+	if (!found_ref)
+		err |= MISSING_BACKREF;
+out:
+	btrfs_release_path(&path);
+	if (eb && (err & MISSING_BACKREF))
+		error("Extent[%llu %u] backret lost(owner: %llu, level: %u)",
+		      bytenr, nodesize, owner, level);
+	return -err;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
-- 
2.8.0

[PATCH RFC 02/16] btrfs-progs: fsck: Introduce function to check data backref in extent tree

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce a new function check_data_extent_item() to check if the
corresponding data backref exists in extent tree.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c  | 151 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ctree.h       |   2 +
 extent-tree.c |   2 +-
 3 files changed, 154 insertions(+), 1 deletion(-)

diff --git a/cmds-check.c b/cmds-check.c
index 27fc26f..d097edd 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -322,6 +322,7 @@ struct root_item_info {
  */
 #define MISSING_BACKREF	(1 << 0) /* Completely no backref in extent tree */
 #define BAD_BACKREF	(1 << 1) /* Backref mismatch */
+#define UNALIGNED_BYTES	(1 << 2) /* Some bytes are not aligned */
 
 static void *print_status_check(void *p)
 {
@@ -8565,6 +8566,156 @@ out:
 	return -err;
 }
 
+/*
+ * Check EXTENT_DATA item, mainly for its dbackref in extent tree
+ *
+ * Return <0 any error found and output error message
+ * Return 0 for no error found
+ */
+static int check_extent_data_item(struct btrfs_root *root,
+				  struct extent_buffer *eb, int slot)
+{
+	struct btrfs_file_extent_item *fi;
+	struct btrfs_path path;
+	struct btrfs_root *extent_root = root->fs_info->extent_root;
+	struct btrfs_key key;
+	struct btrfs_key found_key;
+	struct extent_buffer *leaf;
+	struct btrfs_extent_item *ei;
+	struct btrfs_extent_inline_ref *iref;
+	struct btrfs_extent_data_ref *dref;
+	u64 owner;
+	u64 file_extent_gen;
+	u64 disk_bytenr;
+	u64 disk_num_bytes;
+	u64 extent_num_bytes;
+	u64 extent_flags;
+	u64 extent_gen;
+	u32 item_size;
+	unsigned long end;
+	unsigned long ptr;
+	int type;
+	u64 ref_root;
+	int found_dbackref = 0;
+	int err = 0;
+	int ret;
+
+	btrfs_item_key_to_cpu(eb, &key, slot);
+	fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
+	file_extent_gen = btrfs_file_extent_generation(eb, fi);
+
+	/* Nothing to check for hole and inline data extents */
+	if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE ||
+	    btrfs_file_extent_disk_bytenr(eb, fi) == 0)
+		return 0;
+
+	disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
+	disk_num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
+	extent_num_bytes = btrfs_file_extent_num_bytes(eb, fi);
+	/* Check unaligned disk_num_bytes and num_bytes */
+	if (!IS_ALIGNED(disk_num_bytes, root->sectorsize)) {
+		error("File extent [%llu, %llu] has unaligned disk num bytes: %llu, should be aligned to %u",
+		      key.objectid, key.offset, disk_num_bytes,
+		      root->sectorsize);
+		err |= UNALIGNED_BYTES;
+	} else
+		data_bytes_allocated += disk_num_bytes;
+	if (!IS_ALIGNED(extent_num_bytes, root->sectorsize)) {
+		error("File extent [%llu, %llu] has unaligned num bytes: %llu, should be aligned to %u",
+		      key.objectid, key.offset, extent_num_bytes,
+		      root->sectorsize);
+		err |= UNALIGNED_BYTES;
+	} else
+		data_bytes_referenced += extent_num_bytes;
+	owner = btrfs_header_owner(eb);
+
+	/* Check the data backref in extent tree */
+	btrfs_init_path(&path);
+	key.objectid = btrfs_file_extent_disk_bytenr(eb, fi);
+	key.type = BTRFS_EXTENT_ITEM_KEY;
+	key.offset = btrfs_file_extent_disk_num_bytes(eb, fi);
+
+	ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
+	if (ret) {
+		err |= MISSING_BACKREF;
+		goto error;
+	}
+
+	leaf = path.nodes[0];
+	slot = path.slots[0];
+	btrfs_item_key_to_cpu(leaf, &found_key, slot);
+	ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
+
+	extent_flags = btrfs_extent_flags(leaf, ei);
+	extent_gen = btrfs_extent_generation(leaf, ei);
+
+	btrfs_item_key_to_cpu(eb, &key, slot);
+	if (!(extent_flags & BTRFS_EXTENT_FLAG_DATA)) {
+		error("Extent[%llu %llu] backref type mismatch, wanted bit: %llx",
+		      disk_bytenr, disk_num_bytes,
+		      BTRFS_EXTENT_FLAG_DATA);
+		err |= BAD_BACKREF;
+	}
+
+	if (file_extent_gen != extent_gen) {
+		error("Extent[%llu %llu] backref generation mismatch, wanted: %llu, have: %llu",
+		      disk_bytenr, disk_num_bytes, file_extent_gen,
+		      extent_gen);
+		err = BAD_BACKREF;
+	}
+
+	/* Check data backref */
+	item_size = btrfs_item_size_nr(leaf, path.slots[0]);
+	iref = (struct btrfs_extent_inline_ref *)(ei + 1);
+	ptr = (unsigned long)iref;
+	end = (unsigned long)ei + item_size;
+	while (ptr < end) {
+		iref = (struct btrfs_extent_inline_ref *)ptr;
+		type = btrfs_extent_inline_ref_type(leaf, iref);
+		dref = (struct btrfs_extent_data_ref *)(&iref->offset);
+
+		if (type == BTRFS_EXTENT_DATA_REF_KEY) {
+			ref_root = btrfs_extent_data_ref_root(leaf, dref);
+			if (ref_root == owner || ref_root == root->objectid)
+				found_dbackref = 1;
+		} else if (type == BTRFS_SHARED_DATA_REF_KEY) {
+			found_dbackref = !check_tree_block_ref(root, NULL,
+				btrfs_extent_inline_ref_offset(leaf, iref),
+				0, owner);
+		}
+
+		if (found_dbackref)
+			break;
+		ptr += btrfs_extent_inline_ref_size(type);
+	}
+
+	/* Didn't found inlined data backref, try EXTENT_DATA_REF_KEY */
+	if (!found_dbackref) {
+		btrfs_release_path(&path);
+
+		btrfs_init_path(&path);
+		key.objectid = btrfs_file_extent_disk_bytenr(eb, fi);
+		key.type = BTRFS_EXTENT_DATA_REF_KEY;
+		key.offset = hash_extent_data_ref(root->objectid, owner,
+						  key.offset);
+
+		ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
+					&key, &path, 0, 0);
+		if (!ret)
+			found_dbackref = 1;
+	}
+
+	if (!found_dbackref)
+		err |= MISSING_BACKREF;
+error:
+	btrfs_release_path(&path);
+	if (err & MISSING_BACKREF) {
+		error("Data extent[%llu %llu] backref lost",
+		      disk_bytenr, disk_num_bytes);
+	}
+	return err;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
diff --git a/ctree.h b/ctree.h
index 2da6f77..906d6cd 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2338,6 +2338,8 @@ int exclude_super_stripes(struct btrfs_root *root,
 			  struct btrfs_block_group_cache *cache);
 u64 add_new_free_space(struct btrfs_block_group_cache *block_group,
 		       struct btrfs_fs_info *info, u64 start, u64 end);
+u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset);
+
 /* ctree.c */
 int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2);
 int btrfs_del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
diff --git a/extent-tree.c b/extent-tree.c
index 5ca53fa..607facb 100644
--- a/extent-tree.c
+++ b/extent-tree.c
@@ -598,7 +598,7 @@ static int convert_extent_item_v0(struct btrfs_trans_handle *trans,
 }
 #endif
 
-static u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
+u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
 {
 	u32 high_crc = ~(u32)0;
 	u32 low_crc = ~(u32)0;
-- 
2.8.0

[PATCH RFC 03/16] btrfs-progs: fsck: Introduce function to query tree block level

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce function query_tree_block_level() to resolve tree block level
by reading out the tree block.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index d097edd..6633b6e 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -8716,6 +8716,26 @@ error:
 	return err;
 }
 
+/*
+ * Get real tree block level for case like shared block
+ * Return >= 0 as tree level
+ * Return <0 for error
+ */
+static int query_tree_block_level(struct btrfs_fs_info *fs_info, u64 bytenr)
+{
+	struct extent_buffer *eb;
+	u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
+	int ret = -EIO;
+
+	eb = read_tree_block_fs_info(fs_info, bytenr, nodesize, 0);
+	if (!extent_buffer_uptodate(eb))
+		goto out;
+	ret = btrfs_header_level(eb);
+out:
+	free_extent_buffer(eb);
+	return ret;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
-- 
2.8.0

[PATCH RFC 04/16] btrfs-progs: fsck: Introduce function to check referencer of a backref

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce a new function check_tree_block_backref() to check if a
backref points to correct referencer.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 95 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 95 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 6633b6e..81dd4f3 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -323,6 +323,8 @@ struct root_item_info {
 #define MISSING_BACKREF	(1 << 0) /* Completely no backref in extent tree */
 #define BAD_BACKREF	(1 << 1) /* Backref mismatch */
 #define UNALIGNED_BYTES	(1 << 2) /* Some bytes are not aligned */
+#define MISSING_REFERENCER (1 << 3) /* Referencer not found */
+#define BAD_REFERENCER	(1 << 4) /* Referencer found, but not mismatch */
 
 static void *print_status_check(void *p)
 {
@@ -8736,6 +8738,99 @@ out:
 	return ret;
 }
 
+/*
+ * Check if a tree block backref is valid (points to valid tree block)
+ * if level == -1, level will be resolved
+ */
+static int check_tree_block_backref(struct btrfs_fs_info *fs_info, u64 root_id,
+				    u64 bytenr, int level)
+{
+	struct btrfs_root *root;
+	struct btrfs_key key;
+	struct btrfs_path path;
+	struct extent_buffer *eb;
+	struct extent_buffer *node;
+	u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
+	int err = 0;
+	int ret;
+
+	/* Query level for level == -1 special case */
+	if (level == -1)
+		level = query_tree_block_level(fs_info, bytenr);
+	if (level < 0) {
+		err = MISSING_REFERENCER;
+		goto out;
+	}
+
+	key.objectid = root_id;
+	key.type = BTRFS_ROOT_ITEM_KEY;
+	key.offset = (u64)-1;
+
+	root = btrfs_read_fs_root(fs_info, &key);
+	if (IS_ERR(root)) {
+		err |= MISSING_REFERENCER;
+		goto out;
+	}
+
+	/* Read out the tree block to get item/node key */
+	eb = read_tree_block(root, bytenr, root->nodesize, 0);
+	/* Impossible, as tree block query has read out the tree block */
+	if (!extent_buffer_uptodate(eb)) {
+		err |= MISSING_REFERENCER;
+		free_extent_buffer(eb);
+		goto out;
+	}
+
+	/* Empty tree, no need to check key */
+	if (!btrfs_header_nritems(eb) && !level) {
+		free_extent_buffer(eb);
+		goto out;
+	}
+
+	if (level)
+		btrfs_node_key_to_cpu(eb, &key, 0);
+	else
+		btrfs_item_key_to_cpu(eb, &key, 0);
+
+	free_extent_buffer(eb);
+
+	btrfs_init_path(&path);
+	/* Search with the first key, to ensure we can reach it */
+	ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
+	if (ret) {
+		err |= MISSING_REFERENCER;
+		goto release_out;
+	}
+
+	node = path.nodes[level];
+	if (btrfs_header_bytenr(node) != bytenr) {
+		error("Extent [%llu %d] referencer bytenr mismatch, wanted: %llu, have: %llu",
+		      bytenr, nodesize, bytenr,
+		      btrfs_header_bytenr(node));
+		err |= BAD_REFERENCER;
+	}
+	if (btrfs_header_level(node) != level) {
+		error("Extent [%llu %d] referencer level mismatch, wanted: %d, have: %d",
+		      bytenr, nodesize, level,
+		      btrfs_header_level(node));
+		err |= BAD_REFERENCER;
+	}
+
+release_out:
+	btrfs_release_path(&path);
+out:
+	if (err & MISSING_REFERENCER) {
+		if (level < 0)
+			error("Extent [%llu %d] lost referencer(owner: %llu)",
+			       bytenr, nodesize, root_id);
+		else
+			error("Extent [%llu %d] lost referencer(owner: %llu, level: %u)",
+			       bytenr, nodesize, root_id, level);
+	}
+
+	return -err;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
-- 
2.8.0

[PATCH RFC 05/16] btrfs-progs: fsck: Introduce function to check shared block ref

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce function check_shared_block_backref() to check shared block
ref.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 42 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 42 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 81dd4f3..1d1b198 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -8831,6 +8831,48 @@ out:
 	return -err;
 }
 
+/*
+ * Check referencer for shared block backref
+ * If level == -1, this function will resolve the level.
+ */
+static int check_shared_block_backref(struct btrfs_fs_info *fs_info,
+				     u64 parent, u64 bytenr, int level)
+{
+	struct extent_buffer *eb;
+	u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
+	u32 nr;
+	int found_parent = 0;
+	int i;
+
+	eb = read_tree_block_fs_info(fs_info, parent, nodesize, 0);
+	if (!extent_buffer_uptodate(eb))
+		goto out;
+
+	if (level == -1)
+		level = query_tree_block_level(fs_info, bytenr);
+	if (level < 0)
+		goto out;
+
+	if (level + 1 != btrfs_header_level(eb))
+		goto out;
+
+	nr = btrfs_header_nritems(eb);
+	for (i = 0; i < nr; i++) {
+		if (bytenr == btrfs_node_blockptr(eb, i)) {
+			found_parent = 1;
+			break;
+		}
+	}
+out:
+	free_extent_buffer(eb);
+	if (!found_parent) {
+		error("Shared extent[%llu %u] lost its parent(parent: %llu, level: %u)",
+		      bytenr, nodesize, parent, level);
+		return -MISSING_REFERENCER;
+	}
+	return 0;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
-- 
2.8.0

[PATCH RFC 06/16] btrfs-progs: fsck: Introduce function to check referencer for data backref

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce new function check_extent_data_backref() to search referencer
for a given data backref.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 96 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 96 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 1d1b198..8f971b9 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -8873,6 +8873,102 @@ out:
 	return 0;
 }
 
+/*
+ * Check referencer for normal(inlined) data ref
+ * If len == 0, it will be resolved by searching in extent tree
+ */
+static int check_extent_data_backref(struct btrfs_fs_info *fs_info,
+				     u64 root_id, u64 objectid, u64 offset,
+				     u64 bytenr, u64 len)
+{
+	struct btrfs_root *root;
+	struct btrfs_root *extent_root = fs_info->extent_root;
+	struct btrfs_key key;
+	struct btrfs_path path;
+	struct extent_buffer *leaf;
+	struct btrfs_file_extent_item *fi;
+	int slot;
+	int found_referencer = 0;
+	int ret = 0;
+
+	if (!len) {
+		key.objectid = bytenr;
+		key.type = BTRFS_EXTENT_ITEM_KEY;
+		key.offset = (u64)-1;
+
+		btrfs_init_path(&path);
+		ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
+		if (ret < 0)
+			goto out;
+		ret = btrfs_previous_extent_item(extent_root, &path, bytenr);
+		if (ret)
+			goto out;
+		btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
+		if (key.objectid != bytenr ||
+		    key.type != BTRFS_EXTENT_ITEM_KEY)
+			goto out;
+		len = key.offset;
+		btrfs_release_path(&path);
+	}
+	key.objectid = root_id;
+	btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
+	key.offset = (u64)-1;
+
+	root = btrfs_read_fs_root(fs_info, &key);
+	if (IS_ERR(root))
+		goto out;
+
+	btrfs_init_path(&path);
+	key.objectid = objectid;
+	key.type = BTRFS_EXTENT_DATA_KEY;
+	/* 
+	 * It can be nasty as data backref offset is
+	 * file offset - file extent offset, which is smaller or
+	 * equal to original backref offset.
+	 * The only special case is overflow.
+	 * So we need to special judgement and do further search
+	 */
+	key.offset = offset & (1ULL << 63) ? 0 : offset;
+
+	ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
+	if (ret < 0)
+		goto out;
+
+	/* Search afterwards to get correct one */
+	while (1) {
+		leaf = path.nodes[0];
+		slot = path.slots[0];
+
+		btrfs_item_key_to_cpu(leaf, &key, slot);
+		if (key.objectid != objectid || key.type != BTRFS_EXTENT_DATA_KEY)
+			break;
+		fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
+		/*
+		 * Except normal disk bytenr and disk num bytes, we still
+		 * need to do extra check on dbackref offset as
+		 * dbackref offset = file_offset - file_extent_offset
+		 */
+		if (btrfs_file_extent_disk_bytenr(leaf, fi) == bytenr &&
+		    btrfs_file_extent_disk_num_bytes(leaf, fi) == len &&
+		    (u64)(key.offset - btrfs_file_extent_offset(leaf, fi)) ==
+		    offset) {
+			found_referencer = 1;
+			break;
+		}
+		ret = btrfs_next_item(root, &path);
+		if (ret)
+			break;
+	}
+out:
+	btrfs_release_path(&path);
+	if (!found_referencer) {
+		error("Extent[%llu, %llu] lost referencer(root: %llu, owner: %llu, offset: %llu)",
+		      bytenr, len, root_id, objectid, offset);
+		return -MISSING_REFERENCER;
+	}
+	return 0;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
-- 
2.8.0

[PATCH RFC 07/16] btrfs-progs: fsck: Introduce function to check shared data backref

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce the function check_shared_data_backref() to check the
referencer of a given shared data backref.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 44 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 8f971b9..5588898 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -8969,6 +8969,50 @@ out:
 	return 0;
 }
 
+/*
+ * Check if the referencer of a shared data backref exists
+ */
+static int check_shared_data_backref(struct btrfs_fs_info *fs_info,
+				     u64 parent, u64 bytenr)
+{
+	struct extent_buffer *eb;
+	struct btrfs_key key;
+	struct btrfs_file_extent_item *fi;
+	u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
+	u32 nr;
+	int found_parent = 0;
+	int i;
+
+	eb = read_tree_block_fs_info(fs_info, parent, nodesize, 0);
+	if (!extent_buffer_uptodate(eb))
+		goto out;
+
+	nr = btrfs_header_nritems(eb);
+	for (i = 0; i < nr; i++) {
+		btrfs_item_key_to_cpu(eb, &key, i);
+		if (key.type != BTRFS_EXTENT_DATA_KEY)
+			continue;
+
+		fi = btrfs_item_ptr(eb, i, struct btrfs_file_extent_item);
+		if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE)
+			continue;
+
+		if (btrfs_file_extent_disk_bytenr(eb, fi) == bytenr) {
+			found_parent = 1;
+			break;
+		}
+	}
+
+out:
+	free_extent_buffer(eb);
+	if (!found_parent) {
+		error("Shared extent %llu referencer lost(parent: %llu)",
+		      bytenr, parent);
+		return -MISSING_REFERENCER;
+	}
+	return 0;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
-- 
2.8.0

[PATCH RFC 08/16] btrfs-progs: fsck: Introduce function to check an extent

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce function check_extent_item() using previous introduced
functions.

With previous function to check referencer and backref, this function
can be quite easy.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 113 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 113 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 5588898..7f9f848 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -325,6 +325,9 @@ struct root_item_info {
 #define UNALIGNED_BYTES	(1 << 2) /* Some bytes are not aligned */
 #define MISSING_REFERENCER (1 << 3) /* Referencer not found */
 #define BAD_REFERENCER	(1 << 4) /* Referencer found, but not mismatch */
+#define CROSSING_STRIPE_BOUNDARY (1 << 4) /* For kernel scrub workaround */
+#define BAD_ITEM_SIZE	(1 << 5) /* Bad item size */
+#define UNKNOWN_TYPE	(1 << 6) /* Unknown type */
 
 static void *print_status_check(void *p)
 {
@@ -9013,6 +9016,116 @@ out:
 	return 0;
 }
 
+/*
+ * This function will check a given extent item, including its backref and
+ * itself (like crossing stripe boundary and type)
+ *
+ * Since we don't use extent_record anymore, introduce new error bit
+ */
+static int check_extent_item(struct btrfs_fs_info *fs_info,
+			     struct extent_buffer *eb, int slot, int metadata)
+{
+	struct btrfs_extent_item *ei;
+	struct btrfs_extent_inline_ref *iref;
+	struct btrfs_extent_data_ref *dref;
+	unsigned long end;
+	unsigned long ptr;
+	int type;
+	u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
+	u32 item_size = btrfs_item_size_nr(eb, slot);
+	u64 flags;
+	u64 offset;
+	int level;
+	struct btrfs_key key;
+	int ret;
+	int err = 0;
+
+	btrfs_item_key_to_cpu(eb, &key, slot);
+
+	/*
+	 * XXX: Do we really need to handle such historic
+	 * extent structure?
+	 */
+	if (item_size < sizeof(*ei)) {
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+		struct btrfs_extent_item_v0 *ei0;
+
+		BUG_ON(item_size != sizeof(*ei0));
+		return 1;
+#else
+		BUG();
+#endif
+	}
+
+	if (metadata && check_crossing_stripes(key.objectid, eb->len)) {
+		error("bad metadata [%llu, %llu) crossing stripe boundary",
+		      key.objectid, key.objectid + nodesize);
+		err |= CROSSING_STRIPE_BOUNDARY;
+	}
+
+	ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
+	flags = btrfs_extent_flags(eb, ei);
+
+	ptr = (unsigned long)(ei + 1);
+	if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !metadata) {
+		struct btrfs_tree_block_info *info;
+
+		info = (struct btrfs_tree_block_info *)ptr;
+		level = btrfs_tree_block_level(eb, info);
+		ptr += sizeof(struct btrfs_tree_block_info);
+	} else
+		level = key.offset;
+	end = (unsigned long)ei + item_size;
+
+	if (ptr >= end) {
+		err |= BAD_ITEM_SIZE;
+		goto out;
+	}
+
+	/* Now check every backref in this extent item */
+next:
+	iref = (struct btrfs_extent_inline_ref *)ptr;
+	type = btrfs_extent_inline_ref_type(eb, iref);
+	offset = btrfs_extent_inline_ref_offset(eb, iref);
+	switch (type) {
+	case BTRFS_TREE_BLOCK_REF_KEY:
+		ret = check_tree_block_backref(fs_info, offset, key.objectid,
+					       level);
+		err |= -ret;
+		break;
+	case BTRFS_SHARED_BLOCK_REF_KEY:
+		ret = check_shared_block_backref(fs_info, offset, key.objectid,
+						 level);
+		err |= -ret;
+		break;
+	case BTRFS_EXTENT_DATA_REF_KEY:
+		dref = (struct btrfs_extent_data_ref *)(&iref->offset);
+		ret = check_extent_data_backref(fs_info,
+				btrfs_extent_data_ref_root(eb, dref),
+				btrfs_extent_data_ref_objectid(eb, dref),
+				btrfs_extent_data_ref_offset(eb, dref),
+				key.objectid, key.offset);
+		err |= -ret;
+		break;
+	case BTRFS_SHARED_DATA_REF_KEY:
+		ret = check_shared_data_backref(fs_info, offset, key.objectid);
+		err |= -ret;
+		break;
+	default:
+		error("Extent[%llu %d %llu] has unknown ref type: %d",
+		      key.objectid, key.type, key.offset, type);
+		err |= UNKNOWN_TYPE;
+		goto out;
+	}
+
+	ptr += btrfs_extent_inline_ref_size(type);
+	if (ptr < end)
+		goto next;
+
+out:
+	return -err;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
-- 
2.8.0

[PATCH RFC 09/16] btrfs-progs: fsck: Introduce function to check dev extent item

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce function check_dev_extent_item() to find its referencer chunk.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 57 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 7f9f848..92c254f 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -9126,6 +9126,63 @@ out:
 	return -err;
 }
 
+/*
+ * Check if a dev extent item is referred correctly by its chunk
+ */
+static int check_dev_extent_item(struct btrfs_fs_info *fs_info,
+				 struct extent_buffer *eb, int slot)
+{
+	struct btrfs_root *chunk_root = fs_info->chunk_root;
+	struct btrfs_dev_extent *ptr;
+	struct btrfs_path path;
+	struct btrfs_key key;
+	struct btrfs_key found_key;
+	struct btrfs_chunk *chunk;
+	struct extent_buffer *l;
+	int num_stripes;
+	u64 length;
+	int i;
+	int found_chunk = 0;
+	int ret;
+
+	btrfs_item_key_to_cpu(eb, &found_key, slot);
+	ptr = btrfs_item_ptr(eb, slot, struct btrfs_dev_extent);
+	length = btrfs_dev_extent_length(eb, ptr);
+
+	key.objectid = btrfs_dev_extent_chunk_objectid(eb, ptr);
+	key.type = BTRFS_CHUNK_ITEM_KEY;
+	key.offset = btrfs_dev_extent_chunk_offset(eb, ptr);
+
+	btrfs_init_path(&path);
+	ret = btrfs_search_slot(NULL, chunk_root, &key, &path, 0, 0);
+	if (ret)
+		goto out;
+
+	l = path.nodes[0];
+	chunk = btrfs_item_ptr(l, path.slots[0], struct btrfs_chunk);
+	if (btrfs_chunk_length(l, chunk) != length)
+		goto out;
+
+	num_stripes = btrfs_chunk_num_stripes(l, chunk);
+	for (i = 0; i < num_stripes; i++) {
+		u64 devid = btrfs_stripe_devid_nr(l, chunk, i);
+		u64 offset = btrfs_stripe_offset_nr(l, chunk, i);
+
+		if (devid == found_key.objectid && offset == found_key.offset) {
+			found_chunk= 1;
+			break;
+		}
+	}
+out:
+	btrfs_release_path(&path);
+	if (!found_chunk) {
+		error("Device extent[%llu, %llu, %llu] didn't find the relative chunk",
+		       found_key.objectid, found_key.offset, length);
+		return -MISSING_REFERENCER;
+	}
+	return 0;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
-- 
2.8.0

[PATCH RFC 10/16] btrfs-progs: fsck: Introduce function to check dev used space

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce function check_dev_item() to check used space with dev extent
items.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 64 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 92c254f..e2d1ebf 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -328,6 +328,7 @@ struct root_item_info {
 #define CROSSING_STRIPE_BOUNDARY (1 << 4) /* For kernel scrub workaround */
 #define BAD_ITEM_SIZE	(1 << 5) /* Bad item size */
 #define UNKNOWN_TYPE	(1 << 6) /* Unknown type */
+#define ACCOUNTING_MISMATCH (1 << 7) /* Used space accounting error */
 
 static void *print_status_check(void *p)
 {
@@ -9183,6 +9184,69 @@ out:
 	return 0;
 }
 
+/*
+ * Check the used space is correct with the dev item
+ */
+static int check_dev_item(struct btrfs_fs_info *fs_info,
+			  struct extent_buffer *eb, int slot)
+{
+	struct btrfs_root *dev_root = fs_info->dev_root;
+	struct btrfs_dev_item *dev_item;
+	struct btrfs_path path;
+	struct btrfs_key key;
+	struct btrfs_dev_extent *ptr;
+	u64 dev_id;
+	u64 used;
+	u64 total = 0;
+	int ret;
+
+	dev_item = btrfs_item_ptr(eb, slot, struct btrfs_dev_item);
+	dev_id = btrfs_device_id(eb, dev_item);
+	used = btrfs_device_bytes_used(eb, dev_item);
+
+	key.objectid = dev_id;
+	key.type = BTRFS_DEV_EXTENT_KEY;
+	key.offset = 0;
+
+	btrfs_init_path(&path);
+	ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0);
+	if (ret < 0) {
+		btrfs_item_key_to_cpu(eb, &key, slot);
+		error("Couldn't find any releative dev extent for dev[%llu, %u, %llu]",
+		      key.objectid, key.type, key.offset);
+		btrfs_release_path(&path);
+		return -MISSING_REFERENCER;
+	}
+
+	/* Iterate dev_extents to calculate the used space of a device */
+	while (1) {
+		btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
+
+		if (key.objectid > dev_id)
+			break;
+		if (key.type != BTRFS_DEV_EXTENT_KEY || key.objectid != dev_id)
+			goto next;
+
+		ptr = btrfs_item_ptr(path.nodes[0], path.slots[0],
+				     struct btrfs_dev_extent);
+		total += btrfs_dev_extent_length(path.nodes[0], ptr);
+next:
+		ret = btrfs_next_item(dev_root, &path);
+		if (ret)
+			break;
+	}
+	btrfs_release_path(&path);
+
+	if (used != total) {
+		btrfs_item_key_to_cpu(eb, &key, slot);
+		error("Dev extent's total-byte(%llu) is not equal to byte-used(%llu) in dev[%llu, %u, %llu]",
+		      total, used, BTRFS_ROOT_TREE_OBJECTID,
+		      BTRFS_DEV_EXTENT_KEY, dev_id);
+		return -ACCOUNTING_MISMATCH;
+	}
+	return 0;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
-- 
2.8.0

[PATCH RFC 11/16] btrfs-progs: fsck: Introduce function to check block group item

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce function check_block_group_item() to check a block group item.
It will check the referencer chunk and the used space accounting with
extent tree.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 116 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 116 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index e2d1ebf..b9fbb02 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -329,6 +329,7 @@ struct root_item_info {
 #define BAD_ITEM_SIZE	(1 << 5) /* Bad item size */
 #define UNKNOWN_TYPE	(1 << 6) /* Unknown type */
 #define ACCOUNTING_MISMATCH (1 << 7) /* Used space accounting error */
+#define MISMATCH_TYPE	(1 << 8)
 
 static void *print_status_check(void *p)
 {
@@ -9247,6 +9248,121 @@ next:
 	return 0;
 }
 
+/*
+ * Check a block group item with its referener(chunk) and its used space
+ * with extent/metadata item
+ */
+static int check_block_group_item(struct btrfs_fs_info *fs_info,
+				  struct extent_buffer *eb, int slot)
+{
+	struct btrfs_root *extent_root = fs_info->extent_root;
+	struct btrfs_root *chunk_root = fs_info->chunk_root;
+	struct btrfs_block_group_item *bi;
+	struct btrfs_block_group_item bg_item;
+	struct btrfs_path path;
+	struct btrfs_key key;
+	struct btrfs_key found_key;
+	struct btrfs_chunk *chunk;
+	struct extent_buffer *leaf;
+	struct btrfs_extent_item *ei;
+	u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
+	u64 flags;
+	u64 bg_flags;
+	u64 used;
+	u64 total = 0;
+	int ret;
+	int err = 0;
+
+	btrfs_item_key_to_cpu(eb, &found_key, slot);
+	bi = btrfs_item_ptr(eb, slot, struct btrfs_block_group_item);
+	read_extent_buffer(eb, &bg_item, (unsigned long)bi, sizeof(bg_item));
+	used = btrfs_block_group_used(&bg_item);
+	bg_flags = btrfs_block_group_flags(&bg_item);
+
+	key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
+	key.type = BTRFS_CHUNK_ITEM_KEY;
+	key.offset = found_key.objectid;
+
+	btrfs_init_path(&path);
+	/* Search for the referencer chunk */
+	ret = btrfs_search_slot(NULL, chunk_root, &key, &path, 0, 0);
+	if (ret) {
+		error("Block group[%llu %llu] didn't find the releative chunk item",
+		      found_key.objectid, found_key.offset);
+		err |= MISSING_REFERENCER;
+	} else {
+		chunk = btrfs_item_ptr(path.nodes[0], path.slots[0],
+					struct btrfs_chunk);
+		if (btrfs_chunk_length(path.nodes[0], chunk) !=
+						found_key.offset) {
+			error("Block group[%llu %llu] relative chunk item length don't match",
+			      found_key.objectid, found_key.offset);
+			err |= BAD_REFERENCER;
+		}
+	}
+	btrfs_release_path(&path);
+
+	key.objectid = 0;
+	key.type = BTRFS_METADATA_ITEM_KEY;
+	key.offset = found_key.objectid;
+
+	btrfs_init_path(&path);
+	ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
+	if (ret < 0)
+		goto out;
+
+	/* Iterate extent tree to account used space */
+	while (1) {
+		leaf = path.nodes[0];
+		btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
+		if (key.objectid >= found_key.objectid + found_key.offset)
+			break;
+
+		if (key.type != BTRFS_METADATA_ITEM_KEY &&
+		    key.type != BTRFS_EXTENT_ITEM_KEY)
+			goto next;
+		if (key.objectid < found_key.objectid)
+			goto next;
+
+		if (key.type == BTRFS_METADATA_ITEM_KEY)
+			total += nodesize;
+		else
+			total += key.offset;
+
+		ei = btrfs_item_ptr(leaf, path.slots[0],
+				    struct btrfs_extent_item);
+		flags = btrfs_extent_flags(leaf, ei);
+		if (flags & BTRFS_EXTENT_FLAG_DATA) {
+			if (!(bg_flags & BTRFS_BLOCK_GROUP_DATA)) {
+				error("bad extent[%llu, %llu) type mismatch with chunk",
+				      key.objectid, key.objectid + key.offset);
+				err |= MISMATCH_TYPE;
+			}
+		} else if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
+			if (!(bg_flags & (BTRFS_BLOCK_GROUP_SYSTEM |
+				    BTRFS_BLOCK_GROUP_METADATA))) {
+				error("bad extent[%llu, %llu) type mismatch with chunk",
+				      key.objectid, key.objectid + nodesize);
+				err |= MISMATCH_TYPE;
+			}
+		}
+next:
+		ret = btrfs_next_item(extent_root, &path);
+		if (ret)
+			break;
+	}
+
+out:
+	btrfs_release_path(&path);
+
+	if (total != used) {
+		error("Block group[%llu %llu] used(%llu) but extent items used(%llu)",
+		      found_key.objectid, found_key.offset, used, total);
+		err |= ACCOUNTING_MISMATCH;
+	}
+	return -err;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
-- 
2.8.0

[PATCH RFC 12/16] btrfs-progs: fsck: Introduce function to check chunk item

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce function check_chunk_item() to check a chunk item.
It will check all chunk stripes with dev extents and the corresponding
block group item.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 109 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 109 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index b9fbb02..a02db07 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -9363,6 +9363,115 @@ out:
 	return -err;
 }
 
+/*
+ * Check a chunk item.
+ * Including checking all referred dev_extents and block group
+ */
+static int check_chunk_item(struct btrfs_fs_info *fs_info,
+			    struct extent_buffer *eb, int slot)
+{
+	struct btrfs_root *extent_root = fs_info->extent_root;
+	struct btrfs_root *dev_root = fs_info->dev_root;
+	struct btrfs_path path;
+	struct btrfs_key key;
+	struct btrfs_key found_key;
+	struct btrfs_chunk *chunk;
+	struct extent_buffer *leaf;
+	struct btrfs_block_group_item *bi;
+	struct btrfs_block_group_item bg_item;
+	struct btrfs_dev_extent *ptr;
+	u32 sectorsize = btrfs_super_sectorsize(fs_info->super_copy);
+	u64 length;
+	u64 type;
+	u64 profile;
+	int num_stripes;
+	u64 offset;
+	u64 objectid;
+	int i;
+	int ret;
+	int err = 0;
+
+	btrfs_item_key_to_cpu(eb, &found_key, slot);
+	chunk = btrfs_item_ptr(eb, slot, struct btrfs_chunk);
+	length = btrfs_chunk_length(eb, chunk);
+	if (!IS_ALIGNED(length, sectorsize)) {
+		error("Chunk[%llu %llu] length %llu not aligned to %u",
+		      found_key.objectid, found_key.offset,
+		      length, sectorsize);
+		err |= UNALIGNED_BYTES;
+		goto out;
+	}
+
+	type = btrfs_chunk_type(eb, chunk);
+	profile = type & BTRFS_BLOCK_GROUP_PROFILE_MASK;
+	if (!(type & BTRFS_BLOCK_GROUP_TYPE_MASK)) {
+		error("Chunk[%llu %llu] has no chunk type",
+		      found_key.objectid, found_key.offset);
+		err |= UNKNOWN_TYPE;
+	}
+	if (profile && (profile & (profile - 1))) {
+		error("Chunk[%llu %llu] multiple profiled detected",
+		      found_key.objectid, found_key.offset);
+		err |= UNKNOWN_TYPE;
+	}
+
+	key.objectid = found_key.offset;
+	btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
+	key.offset = length;
+
+	btrfs_init_path(&path);
+	ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
+	if (ret) {
+		error("Chunk[%llu %llu] didn't find the releative block group item",
+		      found_key.objectid, found_key.offset);
+		err |= MISSING_REFERENCER;
+	} else{
+		leaf = path.nodes[0];
+		bi = btrfs_item_ptr(leaf, path.slots[0],
+				    struct btrfs_block_group_item);
+		read_extent_buffer(leaf, &bg_item, (unsigned long)bi,
+				   sizeof(bg_item));
+		if (btrfs_block_group_flags(&bg_item) != type) {
+			error("Chunk[%llu %llu] releative block group item flags mismatch, wanted: %llu, have: %llu",
+			      found_key.objectid, found_key.offset, type,
+			      btrfs_block_group_flags(&bg_item));
+			err |= MISSING_REFERENCER;
+		}
+	}
+
+	num_stripes = btrfs_chunk_num_stripes(eb, chunk);
+	for (i = 0; i < num_stripes; i++) {
+		btrfs_release_path(&path);
+		btrfs_init_path(&path);
+		key.objectid = btrfs_stripe_devid_nr(eb, chunk, i);
+		btrfs_set_key_type(&key, BTRFS_DEV_EXTENT_KEY);
+		key.offset = btrfs_stripe_offset_nr(eb, chunk, i);
+
+		ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0);
+		if (ret)
+			goto not_match_dev;
+
+		leaf = path.nodes[0];
+		ptr = btrfs_item_ptr(leaf, path.slots[0],
+				     struct btrfs_dev_extent);
+		objectid = btrfs_dev_extent_chunk_objectid(leaf, ptr);
+		offset = btrfs_dev_extent_chunk_offset(leaf, ptr);
+		if (objectid != found_key.objectid ||
+		    offset != found_key.offset ||
+		    btrfs_dev_extent_length(leaf, ptr) != length)
+			goto not_match_dev;
+		continue;
+not_match_dev:
+		err |= MISSING_BACKREF;
+		error("Chunk[%llu %llu] stripe %d didn't find the releative dev extent",
+		      found_key.objectid, found_key.offset, i);
+		continue;
+	}
+	btrfs_release_path(&path);
+out:
+	return -err;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
-- 
2.8.0

[PATCH RFC 13/16] btrfs-progs: fsck: Introduce hub function for later fsck

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce a hub function, check_items() to check all known/valuable
items and update related accounting like total_bytes and csum_bytes.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 82 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index a02db07..db6fc8e 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -9472,6 +9472,88 @@ out:
 	return -err;
 }
 
+/*
+ * Hub function to check known items and update related accounting info
+ */
+static int check_leaf_items(struct btrfs_root *root, struct extent_buffer *eb)
+{
+	struct btrfs_fs_info *fs_info = root->fs_info;
+	struct btrfs_key key;
+	int slot = 0;
+	int type;
+	int metadata;
+	struct btrfs_extent_data_ref *dref;
+	int ret;
+	int err = 0;
+
+next:
+	btrfs_item_key_to_cpu(eb, &key, slot);
+	type = btrfs_key_type(&key);
+
+	switch (type) {
+	case BTRFS_EXTENT_DATA_KEY:
+		ret = check_extent_data_item(root, eb, slot);
+		err |= -ret;
+		break;
+	case BTRFS_BLOCK_GROUP_ITEM_KEY:
+		ret = check_block_group_item(fs_info, eb, slot);
+		err |= -ret;
+		break;
+	case BTRFS_DEV_ITEM_KEY:
+		ret = check_dev_item(fs_info, eb, slot);
+		err |= -ret;
+		break;
+	case BTRFS_CHUNK_ITEM_KEY:
+		ret = check_chunk_item(fs_info, eb, slot);
+		err |= -ret;
+		break;
+	case BTRFS_DEV_EXTENT_KEY:
+		ret = check_dev_extent_item(fs_info, eb, slot);
+		err |= -ret;
+		break;
+	case BTRFS_EXTENT_ITEM_KEY:
+	case BTRFS_METADATA_ITEM_KEY:
+		metadata = type == BTRFS_METADATA_ITEM_KEY;
+		ret = check_extent_item(fs_info, eb, slot, metadata);
+		err |= -ret;
+		break;
+	case BTRFS_EXTENT_CSUM_KEY:
+		total_csum_bytes += btrfs_item_size_nr(eb, slot);
+		break;
+	case BTRFS_TREE_BLOCK_REF_KEY:
+		ret = check_tree_block_backref(fs_info, key.offset,
+					       key.objectid, -1);
+		err |= -ret;
+		break;
+	case BTRFS_EXTENT_DATA_REF_KEY:
+		dref = btrfs_item_ptr(eb, slot, struct btrfs_extent_data_ref);
+		ret = check_extent_data_backref(fs_info,
+				btrfs_extent_data_ref_root(eb, dref),
+				btrfs_extent_data_ref_objectid(eb, dref),
+				btrfs_extent_data_ref_offset(eb, dref),
+				key.objectid, 0);
+		err |= -ret;
+		break;
+	case BTRFS_SHARED_BLOCK_REF_KEY:
+		ret = check_shared_block_backref(fs_info, key.offset,
+						 key.objectid, -1);
+		err |= -ret;
+		break;
+	case BTRFS_SHARED_DATA_REF_KEY:
+		ret = check_shared_data_backref(fs_info, key.offset,
+						key.objectid);
+		err |= -ret;
+		break;
+	default:
+		break;
+	}
+
+	if (++slot < btrfs_header_nritems(eb))
+		goto next;
+
+	return err;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
-- 
2.8.0

[PATCH RFC 14/16] btrfs-progs: fsck: Introduce function to speed up fs tree check

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce function should_check() to reduced duplicated tree block check
for fs/subvolume tree.

The idea is, we only check the fs/subvolue tree block if we have the
highest referencer rootid, according to extent tree.

In that case, we can skip a lot of fs/subvolume tree block check if
there are a lot of snapshots.

Although we will do a lot of extent tree search for it.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 90 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 90 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index db6fc8e..92f8aa1 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -9554,6 +9554,96 @@ next:
 	return err;
 }
 
+/*
+ * Helper function for later fs/subvol tree check.
+ * To determine if a tree block should be checked.
+ * This function will ensure only the directly referencer with lowest 
+ * rootid to check a fs/subvolume tree block.
+ *
+ * Backref check at extent tree would detect error like missing subvolume
+ * tree, so we can do aggressive judgement to reduce duplicated check.
+ */
+static int should_check(struct btrfs_root *root, struct extent_buffer *eb)
+{
+	struct btrfs_root *extent_root = root->fs_info->extent_root;
+	struct btrfs_key key;
+	struct btrfs_path path;
+	struct extent_buffer *leaf;
+	int slot;
+	struct btrfs_extent_item *ei;
+	unsigned long ptr;
+	unsigned long end;
+	int type;
+	u32 item_size;
+	u64 offset;
+	struct btrfs_extent_inline_ref *iref;
+	int ret;
+
+	btrfs_init_path(&path);
+	key.objectid = btrfs_header_bytenr(eb);
+	key.type = BTRFS_METADATA_ITEM_KEY;
+	key.offset = (u64)-1;
+
+	/*
+	 * Any failure in backref resolving means we can't determine
+	 * who the tree block belongs to.
+	 * So in that case, we need to check that tree block
+	 */
+	ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
+	if (ret < 0)
+		goto need_check;
+
+	ret = btrfs_previous_extent_item(extent_root, &path,
+					 btrfs_header_bytenr(eb));
+	if (ret)
+		goto need_check;
+
+	leaf = path.nodes[0];
+	slot = path.slots[0];
+	btrfs_item_key_to_cpu(leaf, &key, slot);
+	ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
+
+	if (key.type == BTRFS_METADATA_ITEM_KEY) {
+		iref = (struct btrfs_extent_inline_ref *)(ei + 1);
+	} else {
+		struct btrfs_tree_block_info *info;
+
+		info = (struct btrfs_tree_block_info *)(ei + 1);
+		iref = (struct btrfs_extent_inline_ref *)(info + 1);
+	}
+
+	item_size = btrfs_item_size_nr(leaf, slot);
+	ptr = (unsigned long)iref;
+	end = (unsigned long)ei + item_size;
+	while (ptr < end) {
+		iref = (struct btrfs_extent_inline_ref *)ptr;
+		type = btrfs_extent_inline_ref_type(leaf, iref);
+		offset = btrfs_extent_inline_ref_offset(leaf, iref);
+
+		/*
+		 * We only check the tree block if current root is
+		 * the lowest referencer of it.
+		 */
+		if (type == BTRFS_TREE_BLOCK_REF_KEY &&
+		    offset < root->objectid) {
+			btrfs_release_path(&path);
+			return 0;
+		}
+
+		ptr += btrfs_extent_inline_ref_size(type);
+	}
+	/*
+	 * Normally we should also check keyed tree block ref,
+	 * but that may be very time consuming.
+	 * Inlined ref should already make us skip a lot of refs now.
+	 * So skip search keyed tree block ref.
+	 */
+
+need_check:
+	btrfs_release_path(&path);
+	return 1;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
-- 
2.8.0

[PATCH RFC 15/16] btrfs-progs: fsck: Introduce traversal function for fsck

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce a new function traversal_tree_block() to do pre-order
traversal, to co-operate with new fs/subvolume tree skip function.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 77 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 92f8aa1..85d6cf4 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -9644,6 +9644,83 @@ need_check:
 	return 1;
 }
 
+/*
+ * Traversal function for tree block.
+ * We will do
+ * 1) Skip shared fs/subvolume tree blocks
+ * 2) Update related bytes accounting
+ * 3) Pre-order traversal
+ */
+static int traversal_tree_block(struct btrfs_root *root,
+				struct extent_buffer *node)
+{
+	struct extent_buffer *eb;
+	int level;
+	u64 nr;
+	int i;
+	int err = 0;
+	int ret;
+
+	/*
+	 * Skip shared fs/subvolume tree block, in that case they will
+	 * be checked by referencer with lowest rootid
+	 */
+	if (is_fstree(root->objectid) && !should_check(root, node))
+		return 0;
+
+	/* Update bytes accounting */
+	total_btree_bytes += node->len;
+	if (fs_root_objectid(btrfs_header_owner(node)))
+		total_fs_tree_bytes += node->len;
+	if (btrfs_header_owner(node) == BTRFS_EXTENT_TREE_OBJECTID)
+		total_extent_tree_bytes += node->len;
+	if (!found_old_backref &&
+	    btrfs_header_owner(node) == BTRFS_TREE_RELOC_OBJECTID &&
+	    btrfs_header_backref_rev(node) == BTRFS_MIXED_BACKREF_REV &&
+	    !btrfs_header_flag(node, BTRFS_HEADER_FLAG_RELOC))
+		found_old_backref = 1;
+
+	/* pre-order tranversal, check itself first */
+	level = btrfs_header_level(node);
+	ret = check_tree_block_ref(root, node, btrfs_header_bytenr(node),
+				   btrfs_header_level(node),
+				   btrfs_header_owner(node));
+	err |= -ret;
+	if (err)
+		error("check %s failed root %llu bytenr %llu level %d, force continue check",
+		      level ? "node":"leaf", root->objectid,
+		      btrfs_header_bytenr(node), btrfs_header_level(node));
+
+	if (!level) {
+		btree_space_waste += btrfs_leaf_free_space(root, node);
+		ret = check_leaf_items(root, node);
+		err |= -ret;
+		return -err;
+	}
+
+	nr = btrfs_header_nritems(node);
+	btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) - nr) *
+		sizeof(struct btrfs_key_ptr);
+
+	/* Then check all its children */
+	for (i = 0; i < nr; i++) {
+		u64 blocknr = btrfs_node_blockptr(node, i);
+
+		/*
+		 * As a btrfs tree has most 8 levels(0~7), so it's quite
+		 * safe to call the function itself.
+		 */
+		eb = read_tree_block(root, blocknr, root->nodesize, 0);
+		if (extent_buffer_uptodate(eb)) {
+			ret = traversal_tree_block(root, eb);
+			err |= -ret;
+		}
+		free_extent_buffer(eb);
+	}
+
+	return -err;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
-- 
2.8.0

[PATCH RFC 16/16] btrfs-progs: fsck: Introduce low memory mode

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce a new fsck mode: low memory mode.

Old btrfsck is doing a quite efficient but uses some memory for each
extent item.
Old method will ensure extents are only iterated once at extent/chunk
tree check process.

But since it uses a little memory for each extent item, for large fs
with several TB metadata, this can easily eat up memory and cause OOM.

To handle such limitation and improve scalability, the new low-memory
mode will not use any heap memory to record which extent is checked.
Instead it will use extent backref to avoid most of uneeded check on
shared fs/subvolume tree blocks.
And with the use forward and backward reference cross check, we can also
ensure every tree block is at least checked once.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 Documentation/btrfs-check.asciidoc |  2 +
 cmds-check.c                       | 80 +++++++++++++++++++++++++++++++++++++-
 2 files changed, 80 insertions(+), 2 deletions(-)

diff --git a/Documentation/btrfs-check.asciidoc b/Documentation/btrfs-check.asciidoc
index 7371a23..96eadc8 100644
--- a/Documentation/btrfs-check.asciidoc
+++ b/Documentation/btrfs-check.asciidoc
@@ -35,6 +35,8 @@ run in read-only mode (default)
 create a new CRC tree and recalculate all checksums
 --init-extent-tree::
 create a new extent tree
+--low-memory::
+check fs in low memory usage mode(experimental)
 --check-data-csum::
 verify checksums of data blocks
 -p|--progress::
diff --git a/cmds-check.c b/cmds-check.c
index 85d6cf4..e9d68dd 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -71,6 +71,7 @@ static int repair = 0;
 static int no_holes = 0;
 static int init_extent_tree = 0;
 static int check_data_csum = 0;
+static int low_memory = 0;
 static struct btrfs_fs_info *global_info;
 static struct task_ctx ctx = { 0 };
 static struct cache_tree *roots_info_cache = NULL;
@@ -9721,6 +9722,63 @@ static int traversal_tree_block(struct btrfs_root *root,
 	return -err;
 }
 
+/*
+ * Low memory usage version check_chunks_and_extents.
+ */
+static int check_chunks_and_extents_v2(struct btrfs_root *root)
+{
+	struct btrfs_path path;
+	struct btrfs_key key;
+	struct btrfs_root *root1;
+	struct btrfs_root *cur_root;
+	int err = 0;
+	int ret;
+
+	root1 = root->fs_info->chunk_root;
+	ret = traversal_tree_block(root1, root1->node);
+	err |= -ret;
+
+	root1 = root->fs_info->tree_root;
+	ret = traversal_tree_block(root1, root1->node);
+	err |= -ret;
+
+	btrfs_init_path(&path);
+	key.objectid = BTRFS_EXTENT_TREE_OBJECTID;
+	key.offset = 0;
+	key.type = BTRFS_ROOT_ITEM_KEY;
+
+	ret = btrfs_search_slot(NULL, root1, &key, &path, 0, 0);
+	if (ret) {
+		error("couldn't find extent_tree_root from tree_root");
+		goto out;
+	}
+
+	while (1) {
+		btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
+		if (key.type != BTRFS_ROOT_ITEM_KEY)
+			goto next;
+		key.offset = (u64)-1;
+
+		cur_root = btrfs_read_fs_root(root->fs_info, &key);
+		if (IS_ERR(cur_root) || !cur_root) {
+			error("Fail to read tree: %lld", key.objectid);
+			goto next;
+		}
+
+		ret = traversal_tree_block(cur_root, cur_root->node);
+		err |= ret;
+
+next:
+		ret = btrfs_next_item(root1, &path);
+		if (ret)
+			goto out;
+	}
+
+out:
+	btrfs_release_path(&path);
+	return err;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
@@ -10837,6 +10895,7 @@ const char * const cmd_check_usage[] = {
 	"--readonly                  run in read-only mode (default)",
 	"--init-csum-tree            create a new CRC tree",
 	"--init-extent-tree          create a new extent tree",
+	"--low-memory                check in low memory usage mode(experimental)",
 	"--check-data-csum           verify checkums of data blocks",
 	"-Q|--qgroup-report           print a report on qgroup consistency",
 	"-E|--subvol-extents <subvolid>",
@@ -10868,7 +10927,8 @@ int cmd_check(int argc, char **argv)
 		int c;
 		enum { GETOPT_VAL_REPAIR = 257, GETOPT_VAL_INIT_CSUM,
 			GETOPT_VAL_INIT_EXTENT, GETOPT_VAL_CHECK_CSUM,
-			GETOPT_VAL_READONLY, GETOPT_VAL_CHUNK_TREE };
+			GETOPT_VAL_READONLY, GETOPT_VAL_CHUNK_TREE,
+			GETOPT_VAL_LOW_MEMORY };
 		static const struct option long_options[] = {
 			{ "super", required_argument, NULL, 's' },
 			{ "repair", no_argument, NULL, GETOPT_VAL_REPAIR },
@@ -10886,6 +10946,8 @@ int cmd_check(int argc, char **argv)
 			{ "chunk-root", required_argument, NULL,
 				GETOPT_VAL_CHUNK_TREE },
 			{ "progress", no_argument, NULL, 'p' },
+			{ "low-memory", no_argument, NULL,
+				GETOPT_VAL_LOW_MEMORY },
 			{ NULL, 0, NULL, 0}
 		};
 
@@ -10950,6 +11012,9 @@ int cmd_check(int argc, char **argv)
 			case GETOPT_VAL_CHECK_CSUM:
 				check_data_csum = 1;
 				break;
+			case GETOPT_VAL_LOW_MEMORY:
+				low_memory = 1;
+				break;
 		}
 	}
 
@@ -10967,6 +11032,14 @@ int cmd_check(int argc, char **argv)
 		exit(1);
 	}
 
+	/*
+	 * Not supported yet
+	 */
+	if (repair && low_memory) {
+		error("Low memory mode doesn't support repair yet");
+		exit(1);
+	}
+
 	radix_tree_init();
 	cache_tree_init(&root_cache);
 
@@ -11090,7 +11163,10 @@ int cmd_check(int argc, char **argv)
 
 	if (!ctx.progress_enabled)
 		fprintf(stderr, "checking extents\n");
-	ret = check_chunks_and_extents(root);
+	if (low_memory)
+		ret = check_chunks_and_extents_v2(root);
+	else
+		ret = check_chunks_and_extents(root);
 	if (ret)
 		fprintf(stderr, "Errors found in extent allocation tree or chunk allocation\n");
 
-- 
2.8.0

Re: [PATCH RFC 00/16] Introduce low memory usage btrfsck mode

[Austin S. Hemmelgarn]

On 2016-04-25 23:48, Qu Wenruo wrote:
> The branch can be fetched from my github:
> https://github.com/adam900710/btrfs-progs.git low_mem_fsck_rebasing
>
> Original btrfsck checks extent tree in a very efficient method, by
> recording every checked extent in extent record tree to ensure every
> extent will be iterated for at most 2 times.
>
> However extent records are all stored in heap memory, and consider how
> large a btrfs file system can be, it can easily eat up all memory and
> cause OOM for TB-sized metadata.
>
> Instead of such heap memory usage, we introduce low memory usage fsck
> mode.
>
> In this mode, we will use btrfs_search_slot() only and avoid any heap
> memory allocation.
>
> The work flow is:
> 1) Iterate extent tree (backref check)
>     And check whether the referencer of every backref exists.
>
> 2) Iterate other trees (forward ref check)
>     And check whether the backref of every tree block/data exists in
>     extent tree.
>
> So in theory, every extent is iterated twice just as original one.
> But since we don't have extent record, but use btrfs_search_slot() every
> time we check, it will cause extra IO.
>
> I assume the extra IO is reasonable and should make btrfsck able to
> handle super large fs.
>
> TODO features:
> 1) Repair
>     Repair should be the same as old btrfsck, but still need to determine
>     the repair principle.
>     Current repair sometimes uses backref to repair data extent,
>     sometimes uses data extent to fix backref.
>     We need a consistent principle, or we will screw things up.
>
> 2) Replace current fsck code
>     We assume the low memory mode has less lines of code, and may be
>     easier for review and expand.
>
>     If low memory mode is stable enough, we will consider to replace
>     current extent and chunk tree check codes to free a lot of lines.
>
> 3) Further code refining
>     Reduce duplicated codes
>
> 4) Unify output
>     Make the output of low-memory mode same as the normal one.
>
> Lu Fengqi (16):
>    btrfs-progs: fsck: Introduce function to check tree block backref in
>      extent tree
>    btrfs-progs: fsck: Introduce function to check data backref in extent
>      tree
>    btrfs-progs: fsck: Introduce function to query tree block level
>    btrfs-progs: fsck: Introduce function to check referencer of a backref
>    btrfs-progs: fsck: Introduce function to check shared block ref
>    btrfs-progs: fsck: Introduce function to check referencer for data
>      backref
>    btrfs-progs: fsck: Introduce function to check shared data backref
>    btrfs-progs: fsck: Introduce function to check an extent
>    btrfs-progs: fsck: Introduce function to check dev extent item
>    btrfs-progs: fsck: Introduce function to check dev used space
>    btrfs-progs: fsck: Introduce function to check block group item
>    btrfs-progs: fsck: Introduce function to check chunk item
>    btrfs-progs: fsck: Introduce hub function for later fsck
>    btrfs-progs: fsck: Introduce function to speed up fs tree check
>    btrfs-progs: fsck: Introduce traversal function for fsck
>    btrfs-progs: fsck: Introduce low memory mode
>
>   Documentation/btrfs-check.asciidoc |    2 +
>   cmds-check.c                       | 1667 +++++++++++++++++++++++++++++++++---
>   ctree.h                            |    2 +
>   extent-tree.c                      |    2 +-
>   4 files changed, 1536 insertions(+), 137 deletions(-)
>
I don't really have a stock of broken FS images to test this with, but 
I've checked it against known good ones and it correctly identifies them 
as good (I've tested all the profiles except raid5 and raid6 in both 
normal and mixed-bg variants, with all combinations of profiles between 
data and metadata, and with 2-8 devices for the multi-device levels, 
most of the involved filesystems were on LVM thinp storage with mostly 
sparse files), and it properly repairs the couple of broken filesystems 
I can make by hand (mostly stuff with orphaned inodes or bad ref-counts) 
in the same way the existing code repairs them, all while using 
measurably less memory as advertised, so you can add:

Tested-by: Austin S. Hemmelgarn <ahferroin7@gmail.com>

[PATCH RFC v1.1 02/16] btrfs-progs: fsck: Introduce function to check data backref in extent tree

[Qu Wenruo]

From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>

Introduce a new function check_data_extent_item() to check if the
corresponding data backref exists in extent tree.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
Changelog:
v1.1:
   Fix a typo which passed wrong parameter for hash_extent_data_ref()
   Fix a generation mismatch condition, as for inband dedupe or reflink
   case, file extent generation can be larger than extent item generation. 
---
 cmds-check.c  | 152 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ctree.h       |   2 +
 extent-tree.c |   2 +-
 3 files changed, 155 insertions(+), 1 deletion(-)

diff --git a/cmds-check.c b/cmds-check.c
index 27fc26f..a6ea0fd 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -322,6 +322,7 @@ struct root_item_info {
  */
 #define MISSING_BACKREF	(1 << 0) /* Completely no backref in extent tree */
 #define BAD_BACKREF	(1 << 1) /* Backref mismatch */
+#define UNALIGNED_BYTES	(1 << 2) /* Some bytes are not aligned */
 
 static void *print_status_check(void *p)
 {
@@ -8565,6 +8566,157 @@ out:
 	return -err;
 }
 
+/*
+ * Check EXTENT_DATA item, mainly for its dbackref in extent tree
+ *
+ * Return <0 any error found and output error message
+ * Return 0 for no error found
+ */
+static int check_extent_data_item(struct btrfs_root *root,
+				  struct extent_buffer *eb, int slot)
+{
+	struct btrfs_file_extent_item *fi;
+	struct btrfs_path path;
+	struct btrfs_root *extent_root = root->fs_info->extent_root;
+	struct btrfs_key key;
+	struct btrfs_key orig_key;
+	struct btrfs_key found_key;
+	struct extent_buffer *leaf;
+	struct btrfs_extent_item *ei;
+	struct btrfs_extent_inline_ref *iref;
+	struct btrfs_extent_data_ref *dref;
+	u64 owner;
+	u64 file_extent_gen;
+	u64 disk_bytenr;
+	u64 disk_num_bytes;
+	u64 extent_num_bytes;
+	u64 extent_flags;
+	u64 extent_gen;
+	u32 item_size;
+	unsigned long end;
+	unsigned long ptr;
+	int type;
+	u64 ref_root;
+	int found_dbackref = 0;
+	int err = 0;
+	int ret;
+
+	btrfs_item_key_to_cpu(eb, &orig_key, slot);
+	fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
+	file_extent_gen = btrfs_file_extent_generation(eb, fi);
+
+	/* Nothing to check for hole and inline data extents */
+	if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE ||
+	    btrfs_file_extent_disk_bytenr(eb, fi) == 0)
+		return 0;
+
+	disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
+	disk_num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
+	extent_num_bytes = btrfs_file_extent_num_bytes(eb, fi);
+	/* Check unaligned disk_num_bytes and num_bytes */
+	if (!IS_ALIGNED(disk_num_bytes, root->sectorsize)) {
+		error("File extent [%llu, %llu] has unaligned disk num bytes: %llu, should be aligned to %u",
+		      key.objectid, key.offset, disk_num_bytes,
+		      root->sectorsize);
+		err |= UNALIGNED_BYTES;
+	} else
+		data_bytes_allocated += disk_num_bytes;
+	if (!IS_ALIGNED(extent_num_bytes, root->sectorsize)) {
+		error("File extent [%llu, %llu] has unaligned num bytes: %llu, should be aligned to %u",
+		      key.objectid, key.offset, extent_num_bytes,
+		      root->sectorsize);
+		err |= UNALIGNED_BYTES;
+	} else
+		data_bytes_referenced += extent_num_bytes;
+	owner = btrfs_header_owner(eb);
+
+	/* Check the data backref in extent tree */
+	btrfs_init_path(&path);
+	key.objectid = btrfs_file_extent_disk_bytenr(eb, fi);
+	key.type = BTRFS_EXTENT_ITEM_KEY;
+	key.offset = btrfs_file_extent_disk_num_bytes(eb, fi);
+
+	ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
+	if (ret) {
+		err |= MISSING_BACKREF;
+		goto error;
+	}
+
+	leaf = path.nodes[0];
+	slot = path.slots[0];
+	btrfs_item_key_to_cpu(leaf, &found_key, slot);
+	ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
+
+	extent_flags = btrfs_extent_flags(leaf, ei);
+	extent_gen = btrfs_extent_generation(leaf, ei);
+
+	btrfs_item_key_to_cpu(eb, &key, slot);
+	if (!(extent_flags & BTRFS_EXTENT_FLAG_DATA)) {
+		error("Extent[%llu %llu] backref type mismatch, wanted bit: %llx",
+		      disk_bytenr, disk_num_bytes,
+		      BTRFS_EXTENT_FLAG_DATA);
+		err |= BAD_BACKREF;
+	}
+
+	if (file_extent_gen < extent_gen) {
+		error("Extent[%llu %llu] backref generation mismatch, wanted: <=%llu, have: %llu",
+		      disk_bytenr, disk_num_bytes, file_extent_gen,
+		      extent_gen);
+		err = BAD_BACKREF;
+	}
+
+	/* Check data backref */
+	item_size = btrfs_item_size_nr(leaf, path.slots[0]);
+	iref = (struct btrfs_extent_inline_ref *)(ei + 1);
+	ptr = (unsigned long)iref;
+	end = (unsigned long)ei + item_size;
+	while (ptr < end) {
+		iref = (struct btrfs_extent_inline_ref *)ptr;
+		type = btrfs_extent_inline_ref_type(leaf, iref);
+		dref = (struct btrfs_extent_data_ref *)(&iref->offset);
+
+		if (type == BTRFS_EXTENT_DATA_REF_KEY) {
+			ref_root = btrfs_extent_data_ref_root(leaf, dref);
+			if (ref_root == owner || ref_root == root->objectid)
+				found_dbackref = 1;
+		} else if (type == BTRFS_SHARED_DATA_REF_KEY) {
+			found_dbackref = !check_tree_block_ref(root, NULL,
+				btrfs_extent_inline_ref_offset(leaf, iref),
+				0, owner);
+		}
+
+		if (found_dbackref)
+			break;
+		ptr += btrfs_extent_inline_ref_size(type);
+	}
+
+	/* Didn't found inlined data backref, try EXTENT_DATA_REF_KEY */
+	if (!found_dbackref) {
+		btrfs_release_path(&path);
+
+		btrfs_init_path(&path);
+		key.objectid = btrfs_file_extent_disk_bytenr(eb, fi);
+		key.type = BTRFS_EXTENT_DATA_REF_KEY;
+		key.offset = hash_extent_data_ref(root->objectid,
+				orig_key.objectid, key.offset);
+
+		ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
+					&key, &path, 0, 0);
+		if (!ret)
+			found_dbackref = 1;
+	}
+
+	if (!found_dbackref)
+		err |= MISSING_BACKREF;
+error:
+	btrfs_release_path(&path);
+	if (err & MISSING_BACKREF) {
+		error("Data extent[%llu %llu] backref lost",
+		      disk_bytenr, disk_num_bytes);
+	}
+	return err;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root, int overwrite)
 {
diff --git a/ctree.h b/ctree.h
index 2da6f77..906d6cd 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2338,6 +2338,8 @@ int exclude_super_stripes(struct btrfs_root *root,
 			  struct btrfs_block_group_cache *cache);
 u64 add_new_free_space(struct btrfs_block_group_cache *block_group,
 		       struct btrfs_fs_info *info, u64 start, u64 end);
+u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset);
+
 /* ctree.c */
 int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2);
 int btrfs_del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
diff --git a/extent-tree.c b/extent-tree.c
index 5ca53fa..607facb 100644
--- a/extent-tree.c
+++ b/extent-tree.c
@@ -598,7 +598,7 @@ static int convert_extent_item_v0(struct btrfs_trans_handle *trans,
 }
 #endif
 
-static u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
+u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
 {
 	u32 high_crc = ~(u32)0;
 	u32 low_crc = ~(u32)0;
-- 
2.8.0

Re: [PATCH RFC 01/16] btrfs-progs: fsck: Introduce function to check tree block backref in extent tree

[Josef Bacik]

On 04/25/2016 11:48 PM, Qu Wenruo wrote:
> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>
> Introduce function check_tree_block_ref() to check whether a tree block
> has correct backref in extent tree.
>
> Unlike old extent tree check method, we only use search_slot() to search
> reference, no extra structure will be allocated in heap to record what we
> have checked.
>
> This method may cause a little more IO, but should work for super large
> fs without triggering OOM.
>
> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>

Reviewed-by: Josef Bacik <jbacik@fb.com>

Thanks,

Josef

Re: [PATCH RFC v1.1 02/16] btrfs-progs: fsck: Introduce function to check data backref in extent tree

[Josef Bacik]

On 04/27/2016 09:43 PM, Qu Wenruo wrote:
> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>
> Introduce a new function check_data_extent_item() to check if the
> corresponding data backref exists in extent tree.
>
> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
> ---
> Changelog:
> v1.1:
>    Fix a typo which passed wrong parameter for hash_extent_data_ref()
>    Fix a generation mismatch condition, as for inband dedupe or reflink
>    case, file extent generation can be larger than extent item generation.
> ---
>  cmds-check.c  | 152 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  ctree.h       |   2 +
>  extent-tree.c |   2 +-
>  3 files changed, 155 insertions(+), 1 deletion(-)
>
> diff --git a/cmds-check.c b/cmds-check.c
> index 27fc26f..a6ea0fd 100644
> --- a/cmds-check.c
> +++ b/cmds-check.c
> @@ -322,6 +322,7 @@ struct root_item_info {
>   */
>  #define MISSING_BACKREF	(1 << 0) /* Completely no backref in extent tree */
>  #define BAD_BACKREF	(1 << 1) /* Backref mismatch */
> +#define UNALIGNED_BYTES	(1 << 2) /* Some bytes are not aligned */
>
>  static void *print_status_check(void *p)
>  {
> @@ -8565,6 +8566,157 @@ out:
>  	return -err;
>  }
>
> +/*
> + * Check EXTENT_DATA item, mainly for its dbackref in extent tree
> + *
> + * Return <0 any error found and output error message
> + * Return 0 for no error found
> + */
> +static int check_extent_data_item(struct btrfs_root *root,
> +				  struct extent_buffer *eb, int slot)
> +{
> +	struct btrfs_file_extent_item *fi;
> +	struct btrfs_path path;
> +	struct btrfs_root *extent_root = root->fs_info->extent_root;
> +	struct btrfs_key key;
> +	struct btrfs_key orig_key;
> +	struct btrfs_key found_key;
> +	struct extent_buffer *leaf;
> +	struct btrfs_extent_item *ei;
> +	struct btrfs_extent_inline_ref *iref;
> +	struct btrfs_extent_data_ref *dref;
> +	u64 owner;
> +	u64 file_extent_gen;
> +	u64 disk_bytenr;
> +	u64 disk_num_bytes;
> +	u64 extent_num_bytes;
> +	u64 extent_flags;
> +	u64 extent_gen;
> +	u32 item_size;
> +	unsigned long end;
> +	unsigned long ptr;
> +	int type;
> +	u64 ref_root;
> +	int found_dbackref = 0;
> +	int err = 0;
> +	int ret;
> +
> +	btrfs_item_key_to_cpu(eb, &orig_key, slot);
> +	fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
> +	file_extent_gen = btrfs_file_extent_generation(eb, fi);
> +
> +	/* Nothing to check for hole and inline data extents */
> +	if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE ||
> +	    btrfs_file_extent_disk_bytenr(eb, fi) == 0)
> +		return 0;
> +
> +	disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
> +	disk_num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
> +	extent_num_bytes = btrfs_file_extent_num_bytes(eb, fi);
> +	/* Check unaligned disk_num_bytes and num_bytes */
> +	if (!IS_ALIGNED(disk_num_bytes, root->sectorsize)) {
> +		error("File extent [%llu, %llu] has unaligned disk num bytes: %llu, should be aligned to %u",
> +		      key.objectid, key.offset, disk_num_bytes,
> +		      root->sectorsize);
> +		err |= UNALIGNED_BYTES;
> +	} else
> +		data_bytes_allocated += disk_num_bytes;

Please use the standard kernel format of having

} else {
	//blah
}

for single lined else's combined with multi-line if's.  Once that is 
fixed you can add

Reviewed-by: Josef Bacik <jbacik@fb.com>

Thanks,

Josef

Re: [PATCH RFC 03/16] btrfs-progs: fsck: Introduce function to query tree block level

[Josef Bacik]

On 04/25/2016 11:48 PM, Qu Wenruo wrote:
> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>
> Introduce function query_tree_block_level() to resolve tree block level
> by reading out the tree block.
>
> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
> ---

This skips the check_tree_block if the transid passes, but we could have 
a matching transid but a corrupt item.  You need to fix 
read_tree_block_fs_info to always call check_block so we can be sure 
that our btrfs_header_level() is valid here.  Thanks,

Josef

Re: [PATCH RFC 04/16] btrfs-progs: fsck: Introduce function to check referencer of a backref

[Josef Bacik]

On 04/25/2016 11:48 PM, Qu Wenruo wrote:
> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>
> Introduce a new function check_tree_block_backref() to check if a
> backref points to correct referencer.
>
> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
> ---
>  cmds-check.c | 95 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 95 insertions(+)
>
> diff --git a/cmds-check.c b/cmds-check.c
> index 6633b6e..81dd4f3 100644
> --- a/cmds-check.c
> +++ b/cmds-check.c
> @@ -323,6 +323,8 @@ struct root_item_info {
>  #define MISSING_BACKREF	(1 << 0) /* Completely no backref in extent tree */
>  #define BAD_BACKREF	(1 << 1) /* Backref mismatch */
>  #define UNALIGNED_BYTES	(1 << 2) /* Some bytes are not aligned */
> +#define MISSING_REFERENCER (1 << 3) /* Referencer not found */
> +#define BAD_REFERENCER	(1 << 4) /* Referencer found, but not mismatch */
>
>  static void *print_status_check(void *p)
>  {
> @@ -8736,6 +8738,99 @@ out:
>  	return ret;
>  }
>
> +/*
> + * Check if a tree block backref is valid (points to valid tree block)
> + * if level == -1, level will be resolved
> + */
> +static int check_tree_block_backref(struct btrfs_fs_info *fs_info, u64 root_id,
> +				    u64 bytenr, int level)
> +{
> +	struct btrfs_root *root;
> +	struct btrfs_key key;
> +	struct btrfs_path path;
> +	struct extent_buffer *eb;
> +	struct extent_buffer *node;
> +	u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
> +	int err = 0;
> +	int ret;
> +
> +	/* Query level for level == -1 special case */
> +	if (level == -1)
> +		level = query_tree_block_level(fs_info, bytenr);
> +	if (level < 0) {
> +		err = MISSING_REFERENCER;
> +		goto out;
> +	}
> +
> +	key.objectid = root_id;
> +	key.type = BTRFS_ROOT_ITEM_KEY;
> +	key.offset = (u64)-1;
> +
> +	root = btrfs_read_fs_root(fs_info, &key);
> +	if (IS_ERR(root)) {
> +		err |= MISSING_REFERENCER;
> +		goto out;
> +	}
> +
> +	/* Read out the tree block to get item/node key */
> +	eb = read_tree_block(root, bytenr, root->nodesize, 0);
> +	/* Impossible, as tree block query has read out the tree block */
> +	if (!extent_buffer_uptodate(eb)) {
> +		err |= MISSING_REFERENCER;
> +		free_extent_buffer(eb);
> +		goto out;
> +	}
> +
> +	/* Empty tree, no need to check key */
> +	if (!btrfs_header_nritems(eb) && !level) {
> +		free_extent_buffer(eb);
> +		goto out;
> +	}

Actually this is interesting, because we don't actually catch where we 
would have btrfs_header_nritems(eb) == 0 and !level.  So maybe integrate 
that check into check_block, to make sure we have items in node level 
extent buffers.  Thanks,

Josef

Re: [PATCH RFC 05/16] btrfs-progs: fsck: Introduce function to check shared block ref

[Josef Bacik]

On 04/25/2016 11:48 PM, Qu Wenruo wrote:
> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>
> Introduce function check_shared_block_backref() to check shared block
> ref.
>
> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
> ---

Reviewed-by: Josef Bacik <jbacik@fb.com>

Thanks,

Josef

Re: [PATCH RFC 06/16] btrfs-progs: fsck: Introduce function to check referencer for data backref

[Josef Bacik]

On 04/25/2016 11:48 PM, Qu Wenruo wrote:
> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>
> Introduce new function check_extent_data_backref() to search referencer
> for a given data backref.
>
> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>

Reviewed-by: Josef Bacik <jbacik@fb.com>

Thanks,

Josef

Re: [PATCH RFC 07/16] btrfs-progs: fsck: Introduce function to check shared data backref

[Josef Bacik]

On 04/25/2016 11:48 PM, Qu Wenruo wrote:
> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>
> Introduce the function check_shared_data_backref() to check the
> referencer of a given shared data backref.
>
> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>

Reviewed-by: Josef Bacik <jbacik@fb.com>

Thanks,

Josef

Re: [PATCH RFC 08/16] btrfs-progs: fsck: Introduce function to check an extent

[Josef Bacik]

On 04/25/2016 11:48 PM, Qu Wenruo wrote:
> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>
> Introduce function check_extent_item() using previous introduced
> functions.
>
> With previous function to check referencer and backref, this function
> can be quite easy.
>
> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
> ---
>  cmds-check.c | 113 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 113 insertions(+)
>
> diff --git a/cmds-check.c b/cmds-check.c
> index 5588898..7f9f848 100644
> --- a/cmds-check.c
> +++ b/cmds-check.c
> @@ -325,6 +325,9 @@ struct root_item_info {
>  #define UNALIGNED_BYTES	(1 << 2) /* Some bytes are not aligned */
>  #define MISSING_REFERENCER (1 << 3) /* Referencer not found */
>  #define BAD_REFERENCER	(1 << 4) /* Referencer found, but not mismatch */
> +#define CROSSING_STRIPE_BOUNDARY (1 << 4) /* For kernel scrub workaround */
> +#define BAD_ITEM_SIZE	(1 << 5) /* Bad item size */
> +#define UNKNOWN_TYPE	(1 << 6) /* Unknown type */
>
>  static void *print_status_check(void *p)
>  {
> @@ -9013,6 +9016,116 @@ out:
>  	return 0;
>  }
>
> +/*
> + * This function will check a given extent item, including its backref and
> + * itself (like crossing stripe boundary and type)
> + *
> + * Since we don't use extent_record anymore, introduce new error bit
> + */
> +static int check_extent_item(struct btrfs_fs_info *fs_info,
> +			     struct extent_buffer *eb, int slot, int metadata)
> +{
> +	struct btrfs_extent_item *ei;
> +	struct btrfs_extent_inline_ref *iref;
> +	struct btrfs_extent_data_ref *dref;
> +	unsigned long end;
> +	unsigned long ptr;
> +	int type;
> +	u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
> +	u32 item_size = btrfs_item_size_nr(eb, slot);
> +	u64 flags;
> +	u64 offset;
> +	int level;
> +	struct btrfs_key key;
> +	int ret;
> +	int err = 0;
> +
> +	btrfs_item_key_to_cpu(eb, &key, slot);
> +
> +	/*
> +	 * XXX: Do we really need to handle such historic
> +	 * extent structure?
> +	 */
> +	if (item_size < sizeof(*ei)) {
> +#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
> +		struct btrfs_extent_item_v0 *ei0;
> +
> +		BUG_ON(item_size != sizeof(*ei0));
> +		return 1;
> +#else
> +		BUG();
> +#endif
> +	}

We can actually probably start phasing it out, but either way no BUG(), 
just return an error, the whole point of btrfsck is to find disk 
corruption, if we BUG that's just annoying for users.

> +
> +	if (metadata && check_crossing_stripes(key.objectid, eb->len)) {
> +		error("bad metadata [%llu, %llu) crossing stripe boundary",
> +		      key.objectid, key.objectid + nodesize);
> +		err |= CROSSING_STRIPE_BOUNDARY;
> +	}
> +
> +	ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
> +	flags = btrfs_extent_flags(eb, ei);
> +
> +	ptr = (unsigned long)(ei + 1);
> +	if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !metadata) {
> +		struct btrfs_tree_block_info *info;
> +
> +		info = (struct btrfs_tree_block_info *)ptr;
> +		level = btrfs_tree_block_level(eb, info);
> +		ptr += sizeof(struct btrfs_tree_block_info);
> +	} else
> +		level = key.offset;

Adhere to the normal kernel style guidelines.  Thanks,

Josef

Re: [PATCH RFC 09/16] btrfs-progs: fsck: Introduce function to check dev extent item

[Josef Bacik]

On 04/25/2016 11:48 PM, Qu Wenruo wrote:
> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>
> Introduce function check_dev_extent_item() to find its referencer chunk.
>
> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
> ---

Reviewed-by: Josef Bacik <jbacik@fb.com>

Thanks,

Josef

Re: [PATCH RFC 10/16] btrfs-progs: fsck: Introduce function to check dev used space

[Josef Bacik]

On 04/25/2016 11:48 PM, Qu Wenruo wrote:
> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>
> Introduce function check_dev_item() to check used space with dev extent
> items.
>
> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
> ---
>  cmds-check.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 64 insertions(+)
>
> diff --git a/cmds-check.c b/cmds-check.c
> index 92c254f..e2d1ebf 100644
> --- a/cmds-check.c
> +++ b/cmds-check.c
> @@ -328,6 +328,7 @@ struct root_item_info {
>  #define CROSSING_STRIPE_BOUNDARY (1 << 4) /* For kernel scrub workaround */
>  #define BAD_ITEM_SIZE	(1 << 5) /* Bad item size */
>  #define UNKNOWN_TYPE	(1 << 6) /* Unknown type */
> +#define ACCOUNTING_MISMATCH (1 << 7) /* Used space accounting error */
>
>  static void *print_status_check(void *p)
>  {
> @@ -9183,6 +9184,69 @@ out:
>  	return 0;
>  }
>
> +/*
> + * Check the used space is correct with the dev item
> + */
> +static int check_dev_item(struct btrfs_fs_info *fs_info,
> +			  struct extent_buffer *eb, int slot)
> +{
> +	struct btrfs_root *dev_root = fs_info->dev_root;
> +	struct btrfs_dev_item *dev_item;
> +	struct btrfs_path path;
> +	struct btrfs_key key;
> +	struct btrfs_dev_extent *ptr;
> +	u64 dev_id;
> +	u64 used;
> +	u64 total = 0;
> +	int ret;
> +
> +	dev_item = btrfs_item_ptr(eb, slot, struct btrfs_dev_item);
> +	dev_id = btrfs_device_id(eb, dev_item);
> +	used = btrfs_device_bytes_used(eb, dev_item);
> +
> +	key.objectid = dev_id;
> +	key.type = BTRFS_DEV_EXTENT_KEY;
> +	key.offset = 0;
> +
> +	btrfs_init_path(&path);
> +	ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0);
> +	if (ret < 0) {
> +		btrfs_item_key_to_cpu(eb, &key, slot);
> +		error("Couldn't find any releative dev extent for dev[%llu, %u, %llu]",
> +		      key.objectid, key.type, key.offset);
> +		btrfs_release_path(&path);
> +		return -MISSING_REFERENCER;

Eh?  These are flags, not return values, lets not do negative numbers here.

> +	}
> +
> +	/* Iterate dev_extents to calculate the used space of a device */
> +	while (1) {
> +		btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
> +
> +		if (key.objectid > dev_id)
> +			break;
> +		if (key.type != BTRFS_DEV_EXTENT_KEY || key.objectid != dev_id)
> +			goto next;
> +
> +		ptr = btrfs_item_ptr(path.nodes[0], path.slots[0],
> +				     struct btrfs_dev_extent);
> +		total += btrfs_dev_extent_length(path.nodes[0], ptr);
> +next:
> +		ret = btrfs_next_item(dev_root, &path);
> +		if (ret)
> +			break;
> +	}
> +	btrfs_release_path(&path);
> +
> +	if (used != total) {
> +		btrfs_item_key_to_cpu(eb, &key, slot);
> +		error("Dev extent's total-byte(%llu) is not equal to byte-used(%llu) in dev[%llu, %u, %llu]",
> +		      total, used, BTRFS_ROOT_TREE_OBJECTID,
> +		      BTRFS_DEV_EXTENT_KEY, dev_id);
> +		return -ACCOUNTING_MISMATCH;

Same here.  Thanks,

Josef

Re: [PATCH RFC 04/16] btrfs-progs: fsck: Introduce function to check referencer of a backref

[Josef Bacik]

On 04/25/2016 11:48 PM, Qu Wenruo wrote:
> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>
> Introduce a new function check_tree_block_backref() to check if a
> backref points to correct referencer.
>
> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
> ---
>  cmds-check.c | 95 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 95 insertions(+)
>
> diff --git a/cmds-check.c b/cmds-check.c
> index 6633b6e..81dd4f3 100644
> --- a/cmds-check.c
> +++ b/cmds-check.c
> @@ -323,6 +323,8 @@ struct root_item_info {
>  #define MISSING_BACKREF	(1 << 0) /* Completely no backref in extent tree */
>  #define BAD_BACKREF	(1 << 1) /* Backref mismatch */
>  #define UNALIGNED_BYTES	(1 << 2) /* Some bytes are not aligned */
> +#define MISSING_REFERENCER (1 << 3) /* Referencer not found */
> +#define BAD_REFERENCER	(1 << 4) /* Referencer found, but not mismatch */
>
>  static void *print_status_check(void *p)
>  {
> @@ -8736,6 +8738,99 @@ out:
>  	return ret;
>  }
>
> +/*
> + * Check if a tree block backref is valid (points to valid tree block)
> + * if level == -1, level will be resolved
> + */
> +static int check_tree_block_backref(struct btrfs_fs_info *fs_info, u64 root_id,
> +				    u64 bytenr, int level)
> +{
> +	struct btrfs_root *root;
> +	struct btrfs_key key;
> +	struct btrfs_path path;
> +	struct extent_buffer *eb;
> +	struct extent_buffer *node;
> +	u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
> +	int err = 0;
> +	int ret;
> +
> +	/* Query level for level == -1 special case */
> +	if (level == -1)
> +		level = query_tree_block_level(fs_info, bytenr);
> +	if (level < 0) {
> +		err = MISSING_REFERENCER;
> +		goto out;
> +	}
> +
> +	key.objectid = root_id;
> +	key.type = BTRFS_ROOT_ITEM_KEY;
> +	key.offset = (u64)-1;
> +
> +	root = btrfs_read_fs_root(fs_info, &key);
> +	if (IS_ERR(root)) {
> +		err |= MISSING_REFERENCER;
> +		goto out;
> +	}
> +
> +	/* Read out the tree block to get item/node key */
> +	eb = read_tree_block(root, bytenr, root->nodesize, 0);
> +	/* Impossible, as tree block query has read out the tree block */
> +	if (!extent_buffer_uptodate(eb)) {
> +		err |= MISSING_REFERENCER;
> +		free_extent_buffer(eb);
> +		goto out;
> +	}
> +
> +	/* Empty tree, no need to check key */
> +	if (!btrfs_header_nritems(eb) && !level) {
> +		free_extent_buffer(eb);
> +		goto out;
> +	}
> +
> +	if (level)
> +		btrfs_node_key_to_cpu(eb, &key, 0);
> +	else
> +		btrfs_item_key_to_cpu(eb, &key, 0);
> +
> +	free_extent_buffer(eb);
> +
> +	btrfs_init_path(&path);
> +	/* Search with the first key, to ensure we can reach it */
> +	ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
> +	if (ret) {
> +		err |= MISSING_REFERENCER;
> +		goto release_out;
> +	}
> +
> +	node = path.nodes[level];
> +	if (btrfs_header_bytenr(node) != bytenr) {
> +		error("Extent [%llu %d] referencer bytenr mismatch, wanted: %llu, have: %llu",
> +		      bytenr, nodesize, bytenr,
> +		      btrfs_header_bytenr(node));
> +		err |= BAD_REFERENCER;
> +	}
> +	if (btrfs_header_level(node) != level) {
> +		error("Extent [%llu %d] referencer level mismatch, wanted: %d, have: %d",
> +		      bytenr, nodesize, level,
> +		      btrfs_header_level(node));
> +		err |= BAD_REFERENCER;
> +	}
> +
> +release_out:
> +	btrfs_release_path(&path);
> +out:
> +	if (err & MISSING_REFERENCER) {
> +		if (level < 0)
> +			error("Extent [%llu %d] lost referencer(owner: %llu)",
> +			       bytenr, nodesize, root_id);
> +		else
> +			error("Extent [%llu %d] lost referencer(owner: %llu, level: %u)",
> +			       bytenr, nodesize, root_id, level);
> +	}
> +
> +	return -err;

Sigh I missed this at first, if you are doing flags don't return 
negative numbers.  Fix this and then you can add my reviewed-by.  Thanks,

Josef

Re: [PATCH RFC 00/16] Introduce low memory usage btrfsck mode

[Josef Bacik]

On 04/25/2016 11:48 PM, Qu Wenruo wrote:
> The branch can be fetched from my github:
> https://github.com/adam900710/btrfs-progs.git low_mem_fsck_rebasing
>
> Original btrfsck checks extent tree in a very efficient method, by
> recording every checked extent in extent record tree to ensure every
> extent will be iterated for at most 2 times.
>
> However extent records are all stored in heap memory, and consider how
> large a btrfs file system can be, it can easily eat up all memory and
> cause OOM for TB-sized metadata.
>
> Instead of such heap memory usage, we introduce low memory usage fsck
> mode.
>
> In this mode, we will use btrfs_search_slot() only and avoid any heap
> memory allocation.
>
> The work flow is:
> 1) Iterate extent tree (backref check)
>    And check whether the referencer of every backref exists.
>
> 2) Iterate other trees (forward ref check)
>    And check whether the backref of every tree block/data exists in
>    extent tree.
>
> So in theory, every extent is iterated twice just as original one.
> But since we don't have extent record, but use btrfs_search_slot() every
> time we check, it will cause extra IO.
>
> I assume the extra IO is reasonable and should make btrfsck able to
> handle super large fs.
>
> TODO features:
> 1) Repair
>    Repair should be the same as old btrfsck, but still need to determine
>    the repair principle.
>    Current repair sometimes uses backref to repair data extent,
>    sometimes uses data extent to fix backref.
>    We need a consistent principle, or we will screw things up.
>
> 2) Replace current fsck code
>    We assume the low memory mode has less lines of code, and may be
>    easier for review and expand.
>
>    If low memory mode is stable enough, we will consider to replace
>    current extent and chunk tree check codes to free a lot of lines.
>
> 3) Further code refining
>    Reduce duplicated codes
>
> 4) Unify output
>    Make the output of low-memory mode same as the normal one.
>
> Lu Fengqi (16):
>   btrfs-progs: fsck: Introduce function to check tree block backref in
>     extent tree
>   btrfs-progs: fsck: Introduce function to check data backref in extent
>     tree
>   btrfs-progs: fsck: Introduce function to query tree block level
>   btrfs-progs: fsck: Introduce function to check referencer of a backref
>   btrfs-progs: fsck: Introduce function to check shared block ref
>   btrfs-progs: fsck: Introduce function to check referencer for data
>     backref
>   btrfs-progs: fsck: Introduce function to check shared data backref
>   btrfs-progs: fsck: Introduce function to check an extent
>   btrfs-progs: fsck: Introduce function to check dev extent item
>   btrfs-progs: fsck: Introduce function to check dev used space
>   btrfs-progs: fsck: Introduce function to check block group item
>   btrfs-progs: fsck: Introduce function to check chunk item
>   btrfs-progs: fsck: Introduce hub function for later fsck
>   btrfs-progs: fsck: Introduce function to speed up fs tree check
>   btrfs-progs: fsck: Introduce traversal function for fsck
>   btrfs-progs: fsck: Introduce low memory mode
>

I made it halfway through before I realized you are returning negative 
values for flag related errors.  Please don't do that.  Once you fix 
that up I'll review the rest of the series, and don't put my Reviewed-by 
tags on anything until you fix up the negative return value thing.  Thanks,

Josef

Re: [PATCH RFC 00/16] Introduce low memory usage btrfsck mode

[Qu Wenruo]

Josef Bacik wrote on 2016/04/28 10:32 -0400:
> On 04/25/2016 11:48 PM, Qu Wenruo wrote:
>> The branch can be fetched from my github:
>> https://github.com/adam900710/btrfs-progs.git low_mem_fsck_rebasing
>>
>> Original btrfsck checks extent tree in a very efficient method, by
>> recording every checked extent in extent record tree to ensure every
>> extent will be iterated for at most 2 times.
>>
>> However extent records are all stored in heap memory, and consider how
>> large a btrfs file system can be, it can easily eat up all memory and
>> cause OOM for TB-sized metadata.
>>
>> Instead of such heap memory usage, we introduce low memory usage fsck
>> mode.
>>
>> In this mode, we will use btrfs_search_slot() only and avoid any heap
>> memory allocation.
>>
>> The work flow is:
>> 1) Iterate extent tree (backref check)
>>    And check whether the referencer of every backref exists.
>>
>> 2) Iterate other trees (forward ref check)
>>    And check whether the backref of every tree block/data exists in
>>    extent tree.
>>
>> So in theory, every extent is iterated twice just as original one.
>> But since we don't have extent record, but use btrfs_search_slot() every
>> time we check, it will cause extra IO.
>>
>> I assume the extra IO is reasonable and should make btrfsck able to
>> handle super large fs.
>>
>> TODO features:
>> 1) Repair
>>    Repair should be the same as old btrfsck, but still need to determine
>>    the repair principle.
>>    Current repair sometimes uses backref to repair data extent,
>>    sometimes uses data extent to fix backref.
>>    We need a consistent principle, or we will screw things up.
>>
>> 2) Replace current fsck code
>>    We assume the low memory mode has less lines of code, and may be
>>    easier for review and expand.
>>
>>    If low memory mode is stable enough, we will consider to replace
>>    current extent and chunk tree check codes to free a lot of lines.
>>
>> 3) Further code refining
>>    Reduce duplicated codes
>>
>> 4) Unify output
>>    Make the output of low-memory mode same as the normal one.
>>
>> Lu Fengqi (16):
>>   btrfs-progs: fsck: Introduce function to check tree block backref in
>>     extent tree
>>   btrfs-progs: fsck: Introduce function to check data backref in extent
>>     tree
>>   btrfs-progs: fsck: Introduce function to query tree block level
>>   btrfs-progs: fsck: Introduce function to check referencer of a backref
>>   btrfs-progs: fsck: Introduce function to check shared block ref
>>   btrfs-progs: fsck: Introduce function to check referencer for data
>>     backref
>>   btrfs-progs: fsck: Introduce function to check shared data backref
>>   btrfs-progs: fsck: Introduce function to check an extent
>>   btrfs-progs: fsck: Introduce function to check dev extent item
>>   btrfs-progs: fsck: Introduce function to check dev used space
>>   btrfs-progs: fsck: Introduce function to check block group item
>>   btrfs-progs: fsck: Introduce function to check chunk item
>>   btrfs-progs: fsck: Introduce hub function for later fsck
>>   btrfs-progs: fsck: Introduce function to speed up fs tree check
>>   btrfs-progs: fsck: Introduce traversal function for fsck
>>   btrfs-progs: fsck: Introduce low memory mode
>>
>
> I made it halfway through before I realized you are returning negative
> values for flag related errors.  Please don't do that.  Once you fix
> that up I'll review the rest of the series, and don't put my Reviewed-by
> tags on anything until you fix up the negative return value thing.  Thanks,
>
> Josef
>
>
>
Thanks for the review.

Oh, it seems that I'm too restricted on that any error should cause 
minus return value.

OK, I'll change them into normal >0 return value and apply the comment 
you pointed out.

Thanks,
Qu

Re: [PATCH RFC 03/16] btrfs-progs: fsck: Introduce function to query tree block level

[Qu Wenruo]

Josef Bacik wrote on 2016/04/28 10:13 -0400:
> On 04/25/2016 11:48 PM, Qu Wenruo wrote:
>> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>>
>> Introduce function query_tree_block_level() to resolve tree block level
>> by reading out the tree block.
>>
>> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
>> ---
>
> This skips the check_tree_block if the transid passes, but we could have
> a matching transid but a corrupt item.  You need to fix
> read_tree_block_fs_info to always call check_block so we can be sure
> that our btrfs_header_level() is valid here.  Thanks,
>
> Josef
>
>
read_tree_block_fs_info(or read_tree_block) will call check_tree_block() 
and verify_parent_transid() if it doesn't find a cached extent buffer.

So I don't think we need to do further modification to 
read_tree_block_fs_info().

But your comment reminds me that, we did miss the generation check, as 
we can get generation from backref, and when we can, we should also 
check transid.

We will add transid check from metadata backref.

Thanks,
Qu

Re: [PATCH RFC 04/16] btrfs-progs: fsck: Introduce function to check referencer of a backref

[Qu Wenruo]

Josef Bacik wrote on 2016/04/28 10:17 -0400:
> On 04/25/2016 11:48 PM, Qu Wenruo wrote:
>> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>>
>> Introduce a new function check_tree_block_backref() to check if a
>> backref points to correct referencer.
>>
>> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
>> ---
>>  cmds-check.c | 95
>> ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>>  1 file changed, 95 insertions(+)
>>
>> diff --git a/cmds-check.c b/cmds-check.c
>> index 6633b6e..81dd4f3 100644
>> --- a/cmds-check.c
>> +++ b/cmds-check.c
>> @@ -323,6 +323,8 @@ struct root_item_info {
>>  #define MISSING_BACKREF    (1 << 0) /* Completely no backref in
>> extent tree */
>>  #define BAD_BACKREF    (1 << 1) /* Backref mismatch */
>>  #define UNALIGNED_BYTES    (1 << 2) /* Some bytes are not aligned */
>> +#define MISSING_REFERENCER (1 << 3) /* Referencer not found */
>> +#define BAD_REFERENCER    (1 << 4) /* Referencer found, but not
>> mismatch */
>>
>>  static void *print_status_check(void *p)
>>  {
>> @@ -8736,6 +8738,99 @@ out:
>>      return ret;
>>  }
>>
>> +/*
>> + * Check if a tree block backref is valid (points to valid tree block)
>> + * if level == -1, level will be resolved
>> + */
>> +static int check_tree_block_backref(struct btrfs_fs_info *fs_info,
>> u64 root_id,
>> +                    u64 bytenr, int level)
>> +{
>> +    struct btrfs_root *root;
>> +    struct btrfs_key key;
>> +    struct btrfs_path path;
>> +    struct extent_buffer *eb;
>> +    struct extent_buffer *node;
>> +    u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
>> +    int err = 0;
>> +    int ret;
>> +
>> +    /* Query level for level == -1 special case */
>> +    if (level == -1)
>> +        level = query_tree_block_level(fs_info, bytenr);
>> +    if (level < 0) {
>> +        err = MISSING_REFERENCER;
>> +        goto out;
>> +    }
>> +
>> +    key.objectid = root_id;
>> +    key.type = BTRFS_ROOT_ITEM_KEY;
>> +    key.offset = (u64)-1;
>> +
>> +    root = btrfs_read_fs_root(fs_info, &key);
>> +    if (IS_ERR(root)) {
>> +        err |= MISSING_REFERENCER;
>> +        goto out;
>> +    }
>> +
>> +    /* Read out the tree block to get item/node key */
>> +    eb = read_tree_block(root, bytenr, root->nodesize, 0);
>> +    /* Impossible, as tree block query has read out the tree block */
>> +    if (!extent_buffer_uptodate(eb)) {
>> +        err |= MISSING_REFERENCER;
>> +        free_extent_buffer(eb);
>> +        goto out;
>> +    }
>> +
>> +    /* Empty tree, no need to check key */
>> +    if (!btrfs_header_nritems(eb) && !level) {
>> +        free_extent_buffer(eb);
>> +        goto out;
>> +    }
>
> Actually this is interesting, because we don't actually catch where we
> would have btrfs_header_nritems(eb) == 0 and !level.  So maybe integrate
> that check into check_block, to make sure we have items in node level
> extent buffers.  Thanks,
>
> Josef
>
>
Unfortunately, we can't integrate it into check_tree_block() (or caller 
read_tree_block() and its variants).

As this is a valid case.
(And that's why we don't report error here)

For trees like csum tree and uuid tree, they can be empty, and it 
doesn't break any thing.

So it's a not something we need to integrate into check_tree_block().

And if you mean check_block() in old fsck codes, we won't use it in new 
fsck, so still not a big problem.

Thanks,
Qu

Re: [PATCH RFC 03/16] btrfs-progs: fsck: Introduce function to query tree block level

[Josef Bacik]

On 04/28/2016 11:35 PM, Qu Wenruo wrote:
>
>
> Josef Bacik wrote on 2016/04/28 10:13 -0400:
>> On 04/25/2016 11:48 PM, Qu Wenruo wrote:
>>> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>>>
>>> Introduce function query_tree_block_level() to resolve tree block level
>>> by reading out the tree block.
>>>
>>> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>>> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
>>> ---
>>
>> This skips the check_tree_block if the transid passes, but we could have
>> a matching transid but a corrupt item.  You need to fix
>> read_tree_block_fs_info to always call check_block so we can be sure
>> that our btrfs_header_level() is valid here.  Thanks,
>>
>> Josef
>>
>>
> read_tree_block_fs_info(or read_tree_block) will call check_tree_block()
> and verify_parent_transid() if it doesn't find a cached extent buffer.
>
> So I don't think we need to do further modification to
> read_tree_block_fs_info().
>
> But your comment reminds me that, we did miss the generation check, as
> we can get generation from backref, and when we can, we should also
> check transid.
>
> We will add transid check from metadata backref.
>

Sigh I was looking at an older version of btrfs-progs, you are right. 
Thanks,

Josef

Re: [PATCH RFC 04/16] btrfs-progs: fsck: Introduce function to check referencer of a backref

[Josef Bacik]

On 04/29/2016 01:31 AM, Qu Wenruo wrote:
>
>
> Josef Bacik wrote on 2016/04/28 10:17 -0400:
>> On 04/25/2016 11:48 PM, Qu Wenruo wrote:
>>> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>>>
>>> Introduce a new function check_tree_block_backref() to check if a
>>> backref points to correct referencer.
>>>
>>> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>>> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
>>> ---
>>>  cmds-check.c | 95
>>> ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>>>  1 file changed, 95 insertions(+)
>>>
>>> diff --git a/cmds-check.c b/cmds-check.c
>>> index 6633b6e..81dd4f3 100644
>>> --- a/cmds-check.c
>>> +++ b/cmds-check.c
>>> @@ -323,6 +323,8 @@ struct root_item_info {
>>>  #define MISSING_BACKREF    (1 << 0) /* Completely no backref in
>>> extent tree */
>>>  #define BAD_BACKREF    (1 << 1) /* Backref mismatch */
>>>  #define UNALIGNED_BYTES    (1 << 2) /* Some bytes are not aligned */
>>> +#define MISSING_REFERENCER (1 << 3) /* Referencer not found */
>>> +#define BAD_REFERENCER    (1 << 4) /* Referencer found, but not
>>> mismatch */
>>>
>>>  static void *print_status_check(void *p)
>>>  {
>>> @@ -8736,6 +8738,99 @@ out:
>>>      return ret;
>>>  }
>>>
>>> +/*
>>> + * Check if a tree block backref is valid (points to valid tree block)
>>> + * if level == -1, level will be resolved
>>> + */
>>> +static int check_tree_block_backref(struct btrfs_fs_info *fs_info,
>>> u64 root_id,
>>> +                    u64 bytenr, int level)
>>> +{
>>> +    struct btrfs_root *root;
>>> +    struct btrfs_key key;
>>> +    struct btrfs_path path;
>>> +    struct extent_buffer *eb;
>>> +    struct extent_buffer *node;
>>> +    u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
>>> +    int err = 0;
>>> +    int ret;
>>> +
>>> +    /* Query level for level == -1 special case */
>>> +    if (level == -1)
>>> +        level = query_tree_block_level(fs_info, bytenr);
>>> +    if (level < 0) {
>>> +        err = MISSING_REFERENCER;
>>> +        goto out;
>>> +    }
>>> +
>>> +    key.objectid = root_id;
>>> +    key.type = BTRFS_ROOT_ITEM_KEY;
>>> +    key.offset = (u64)-1;
>>> +
>>> +    root = btrfs_read_fs_root(fs_info, &key);
>>> +    if (IS_ERR(root)) {
>>> +        err |= MISSING_REFERENCER;
>>> +        goto out;
>>> +    }
>>> +
>>> +    /* Read out the tree block to get item/node key */
>>> +    eb = read_tree_block(root, bytenr, root->nodesize, 0);
>>> +    /* Impossible, as tree block query has read out the tree block */
>>> +    if (!extent_buffer_uptodate(eb)) {
>>> +        err |= MISSING_REFERENCER;
>>> +        free_extent_buffer(eb);
>>> +        goto out;
>>> +    }
>>> +
>>> +    /* Empty tree, no need to check key */
>>> +    if (!btrfs_header_nritems(eb) && !level) {
>>> +        free_extent_buffer(eb);
>>> +        goto out;
>>> +    }
>>
>> Actually this is interesting, because we don't actually catch where we
>> would have btrfs_header_nritems(eb) == 0 and !level.  So maybe integrate
>> that check into check_block, to make sure we have items in node level
>> extent buffers.  Thanks,
>>
>> Josef
>>
>>
> Unfortunately, we can't integrate it into check_tree_block() (or caller
> read_tree_block() and its variants).
>
> As this is a valid case.
> (And that's why we don't report error here)
>
> For trees like csum tree and uuid tree, they can be empty, and it
> doesn't break any thing.
>
> So it's a not something we need to integrate into check_tree_block().
>
> And if you mean check_block() in old fsck codes, we won't use it in new
> fsck, so still not a big problem.
>

But empty trees the root is still level 0, we shouldn't have a node that 
is empty, it should just be removed, right?  Thanks,

Josef

Re: [PATCH RFC 04/16] btrfs-progs: fsck: Introduce function to check referencer of a backref

[Qu Wenruo]

Josef Bacik wrote on 2016/04/29 09:52 -0400:
> On 04/29/2016 01:31 AM, Qu Wenruo wrote:
>>
>>
>> Josef Bacik wrote on 2016/04/28 10:17 -0400:
>>> On 04/25/2016 11:48 PM, Qu Wenruo wrote:
>>>> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>>>>
>>>> Introduce a new function check_tree_block_backref() to check if a
>>>> backref points to correct referencer.
>>>>
>>>> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>>>> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
>>>> ---
>>>>  cmds-check.c | 95
>>>> ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>>>>  1 file changed, 95 insertions(+)
>>>>
>>>> diff --git a/cmds-check.c b/cmds-check.c
>>>> index 6633b6e..81dd4f3 100644
>>>> --- a/cmds-check.c
>>>> +++ b/cmds-check.c
>>>> @@ -323,6 +323,8 @@ struct root_item_info {
>>>>  #define MISSING_BACKREF    (1 << 0) /* Completely no backref in
>>>> extent tree */
>>>>  #define BAD_BACKREF    (1 << 1) /* Backref mismatch */
>>>>  #define UNALIGNED_BYTES    (1 << 2) /* Some bytes are not aligned */
>>>> +#define MISSING_REFERENCER (1 << 3) /* Referencer not found */
>>>> +#define BAD_REFERENCER    (1 << 4) /* Referencer found, but not
>>>> mismatch */
>>>>
>>>>  static void *print_status_check(void *p)
>>>>  {
>>>> @@ -8736,6 +8738,99 @@ out:
>>>>      return ret;
>>>>  }
>>>>
>>>> +/*
>>>> + * Check if a tree block backref is valid (points to valid tree block)
>>>> + * if level == -1, level will be resolved
>>>> + */
>>>> +static int check_tree_block_backref(struct btrfs_fs_info *fs_info,
>>>> u64 root_id,
>>>> +                    u64 bytenr, int level)
>>>> +{
>>>> +    struct btrfs_root *root;
>>>> +    struct btrfs_key key;
>>>> +    struct btrfs_path path;
>>>> +    struct extent_buffer *eb;
>>>> +    struct extent_buffer *node;
>>>> +    u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
>>>> +    int err = 0;
>>>> +    int ret;
>>>> +
>>>> +    /* Query level for level == -1 special case */
>>>> +    if (level == -1)
>>>> +        level = query_tree_block_level(fs_info, bytenr);
>>>> +    if (level < 0) {
>>>> +        err = MISSING_REFERENCER;
>>>> +        goto out;
>>>> +    }
>>>> +
>>>> +    key.objectid = root_id;
>>>> +    key.type = BTRFS_ROOT_ITEM_KEY;
>>>> +    key.offset = (u64)-1;
>>>> +
>>>> +    root = btrfs_read_fs_root(fs_info, &key);
>>>> +    if (IS_ERR(root)) {
>>>> +        err |= MISSING_REFERENCER;
>>>> +        goto out;
>>>> +    }
>>>> +
>>>> +    /* Read out the tree block to get item/node key */
>>>> +    eb = read_tree_block(root, bytenr, root->nodesize, 0);
>>>> +    /* Impossible, as tree block query has read out the tree block */
>>>> +    if (!extent_buffer_uptodate(eb)) {
>>>> +        err |= MISSING_REFERENCER;
>>>> +        free_extent_buffer(eb);
>>>> +        goto out;
>>>> +    }
>>>> +
>>>> +    /* Empty tree, no need to check key */
>>>> +    if (!btrfs_header_nritems(eb) && !level) {
>>>> +        free_extent_buffer(eb);
>>>> +        goto out;
>>>> +    }
>>>
>>> Actually this is interesting, because we don't actually catch where we
>>> would have btrfs_header_nritems(eb) == 0 and !level.  So maybe integrate
>>> that check into check_block, to make sure we have items in node level
>>> extent buffers.  Thanks,
>>>
>>> Josef
>>>
>>>
>> Unfortunately, we can't integrate it into check_tree_block() (or caller
>> read_tree_block() and its variants).
>>
>> As this is a valid case.
>> (And that's why we don't report error here)
>>
>> For trees like csum tree and uuid tree, they can be empty, and it
>> doesn't break any thing.
>>
>> So it's a not something we need to integrate into check_tree_block().
>>
>> And if you mean check_block() in old fsck codes, we won't use it in new
>> fsck, so still not a big problem.
>>
>
> But empty trees the root is still level 0, we shouldn't have a node that
> is empty, it should just be removed, right?  Thanks,
>
> Josef
>
>
>
Oh, You mean any tree level higher than 0 shouldn't have nritems == 0.

That makes sense, I'll send a independent patch for that.

Thanks,
Qu