[PATCH 00/13] btrfs-progs: check: check fs roots in low_memory mode

[PATCH 00/13] btrfs-progs: check: check fs roots in low_memory mode

[Lu Fengqi]

This patchset implements check fs trees in low memory mode, and fix the
return value bug of the function cmd_check().

Lu Fengqi (13):
  btrfs-progs: move btrfs_extref_hash() to hash.h
  btrfs-progs: check: introduce function to find dir_item
  btrfs-progs: check: introduce function to check inode_ref
  btrfs-progs: check: introduce function to check inode_extref
  btrfs-progs: check: introduce function to find inode_ref
  btrfs-progs: check: introduce a function to check dir_item
  btrfs-progs: check: introduce function to check file extent
  btrfs-progs: check: introduce function to check inode item
  btrfs-progs: check: introduce function to check fs root
  btrfs-progs: check: introduce function to check root ref
  btrfs-progs: check: introduce low_memory mode fs_tree check
  btrfs-progs: check: fix the return value bug of cmd_check()
  btrfs-progs: check: fix false warning for check_extent_item()

 cmds-check.c | 1165 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 hash.h       |   10 +
 inode-item.c |    8 +-
 3 files changed, 1164 insertions(+), 19 deletions(-)

-- 
2.7.4

[PATCH 01/13] btrfs-progs: move btrfs_extref_hash() to hash.h

[Lu Fengqi]

Move btrfs_extref_hash() from inode-item.c to hash.h,
so that the function can be called elsewhere.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 hash.h       | 10 ++++++++++
 inode-item.c |  8 +-------
 2 files changed, 11 insertions(+), 7 deletions(-)

diff --git a/hash.h b/hash.h
index ac4c411..9ff6761 100644
--- a/hash.h
+++ b/hash.h
@@ -25,4 +25,14 @@ static inline u64 btrfs_name_hash(const char *name, int len)
 {
 	return crc32c((u32)~1, name, len);
 }
+
+/*
+ * Figure the key offset of an extended inode ref
+ */
+static inline u64 btrfs_extref_hash(u64 parent_objectid, const char *name,
+				    int len)
+{
+	return (u64)btrfs_crc32c(parent_objectid, name, len);
+}
+
 #endif
diff --git a/inode-item.c b/inode-item.c
index 522d25a..df5011e 100644
--- a/inode-item.c
+++ b/inode-item.c
@@ -19,7 +19,7 @@
 #include "ctree.h"
 #include "disk-io.h"
 #include "transaction.h"
-#include "crc32c.h"
+#include "hash.h"
 
 static int find_name_in_backref(struct btrfs_path *path, const char * name,
 			 int name_len, struct btrfs_inode_ref **ref_ret)
@@ -184,12 +184,6 @@ out:
 		return ret_inode_ref;
 }
 
-static inline u64 btrfs_extref_hash(u64 parent_ino, const char *name,
-				    int namelen)
-{
-	return (u64)btrfs_crc32c(parent_ino, name, namelen);
-}
-
 static int btrfs_find_name_in_ext_backref(struct btrfs_path *path,
 		u64 parent_ino, const char *name, int namelen,
 		struct btrfs_inode_extref **extref_ret)
-- 
2.7.4

[PATCH 02/13] btrfs-progs: check: introduce function to find dir_item

[Lu Fengqi]

Introduce a new function find_dir_item() to find DIR_ITEM for the given
key, and check it with the specified INODE_REF/INODE_EXTREF match.

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

diff --git a/cmds-check.c b/cmds-check.c
index dd1b708..7e6f2a9 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -3878,6 +3878,144 @@ out:
 	return err;
 }
 
+#define ROOT_DIR_ERROR		(1<<1)	/* bad root_dir */
+#define DIR_ITEM_MISSING	(1<<2)	/* DIR_ITEM not found */
+#define DIR_ITEM_MISMATCH	(1<<3)	/* DIR_ITEM found but not match */
+
+/*
+ * Find DIR_ITEM/DIR_INDEX for the given key and check it with the specified
+ * INODE_REF/INODE_EXTREF match.
+ *
+ * @root:	the root of the fs/file tree
+ * @ref_key:	the key of the INODE_REF/INODE_EXTREF
+ * @key:	the key of the DIR_ITEM/DIR_INDEX
+ * @index:	the index in the INODE_REF/INODE_EXTREF, be used to
+ *		distinguish root_dir between normal dir/file
+ * @name:	the name in the INODE_REF/INODE_EXTREF
+ * @namelen:	the length of name in the INODE_REF/INODE_EXTREF
+ * @mode:	the st_mode of INODE_ITEM
+ *
+ * Return 0 if no error occurred.
+ * Return ROOT_DIR_ERROR if found DIR_ITEM/DIR_INDEX for root_dir.
+ * Return DIR_ITEM_MISSING if couldn't find DIR_ITEM/DIR_INDEX for normal
+ * dir/file.
+ * Return DIR_ITEM_MISMATCH if INODE_REF/INODE_EXTREF and DIR_ITEM/DIR_INDEX
+ * not match for normal dir/file.
+ */
+static int find_dir_item(struct btrfs_root *root, struct btrfs_key *ref_key,
+			 struct btrfs_key *key, u64 index, char *name,
+			 u32 namelen, u32 mode)
+{
+	struct btrfs_path *path;
+	struct extent_buffer *node;
+	struct btrfs_dir_item *di;
+	struct btrfs_key location;
+	char namebuf[BTRFS_NAME_LEN] = {0};
+	u32 total;
+	u32 cur = 0;
+	u32 len;
+	u32 name_len;
+	u32 data_len;
+	u8 filetype;
+	int slot;
+	int ret;
+
+	path = btrfs_alloc_path();
+	ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
+	if (ret < 0)
+		goto out;
+
+	/* Process root dir and goto out*/
+	if (index == 0) {
+		if (ret == 0) {
+			ret = ROOT_DIR_ERROR;
+			error(
+			"root %llu INODE %s[%llu %llu] ROOT_DIR shouldn't have %s",
+				root->objectid,
+				ref_key->type == BTRFS_INODE_REF_KEY ?
+					"REF" : "EXTREF",
+				ref_key->objectid, ref_key->offset,
+				key->type == BTRFS_DIR_ITEM_KEY ?
+					"DIR_ITEM" : "DIR_INDEX");
+		} else {
+			ret = 0;
+		}
+
+		goto out;
+	}
+
+	/* Process normal file/dir */
+	if (ret > 0) {
+		ret = DIR_ITEM_MISSING;
+		error(
+		"root %llu INODE %s[%llu %llu] doesn't have related %s[%llu %llu] namelen %u filename %s filetype %d",
+			root->objectid,
+			ref_key->type == BTRFS_INODE_REF_KEY ? "REF" : "EXTREF",
+			ref_key->objectid, ref_key->offset,
+			key->type == BTRFS_DIR_ITEM_KEY ?
+				"DIR_ITEM" : "DIR_INDEX",
+			key->objectid, key->offset, namelen, name,
+			imode_to_type(mode));
+		goto out;
+	}
+
+	/* Check whether inode_id/filetype/name match */
+	node = path->nodes[0];
+	slot = path->slots[0];
+	di = btrfs_item_ptr(node, slot, struct btrfs_dir_item);
+	total = btrfs_item_size_nr(node, slot);
+	while (cur < total) {
+		ret = DIR_ITEM_MISMATCH;
+		name_len = btrfs_dir_name_len(node, di);
+		data_len = btrfs_dir_data_len(node, di);
+
+		btrfs_dir_item_key_to_cpu(node, di, &location);
+		if (location.objectid != ref_key->objectid ||
+		    location.type !=  BTRFS_INODE_ITEM_KEY ||
+		    location.offset != 0)
+			goto next;
+
+		filetype = btrfs_dir_type(node, di);
+		if (imode_to_type(mode) != filetype)
+			goto next;
+
+		if (name_len <= BTRFS_NAME_LEN) {
+			len = name_len;
+		} else {
+			len = BTRFS_NAME_LEN;
+			fprintf(stderr,
+			"Warning: root %llu %s[%llu %llu] name too long\n",
+			root->objectid,
+			key->type == BTRFS_DIR_ITEM_KEY ?
+			"DIR_ITEM" : "DIR_INDEX",
+			key->objectid, key->offset);
+		}
+		read_extent_buffer(node, namebuf, (unsigned long)(di + 1), len);
+		if (len != namelen || strncmp(namebuf, name, len))
+			goto next;
+
+		ret = 0;
+		goto out;
+next:
+		len = sizeof(*di) + name_len + data_len;
+		di = (struct btrfs_dir_item *)((char *)di + len);
+		cur += len;
+	}
+	if (ret == DIR_ITEM_MISMATCH)
+		error(
+		"root %llu INODE %s[%llu %llu] and %s[%llu %llu] mismatch namelen %u filename %s filetype %d",
+			root->objectid,
+			ref_key->type == BTRFS_INODE_REF_KEY ? "REF" : "EXTREF",
+			ref_key->objectid, ref_key->offset,
+			key->type == BTRFS_DIR_ITEM_KEY ?
+				"DIR_ITEM" : "DIR_INDEX",
+			key->objectid, key->offset, namelen, name,
+			imode_to_type(mode));
+out:
+	btrfs_free_path(path);
+	return ret;
+}
+
 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 {
 	struct rb_node *n;
-- 
2.7.4

Re: [PATCH 02/13] btrfs-progs: check: introduce function to find dir_item

[David Sterba]

On Thu, Jul 28, 2016 at 03:08:14PM +0800, Lu Fengqi wrote:
> +static int find_dir_item(struct btrfs_root *root, struct btrfs_key *ref_key,
> +			 struct btrfs_key *key, u64 index, char *name,
> +			 u32 namelen, u32 mode)
> +{
> +	struct btrfs_path *path;
> +	struct extent_buffer *node;
> +	struct btrfs_dir_item *di;
> +	struct btrfs_key location;
> +	char namebuf[BTRFS_NAME_LEN] = {0};
> +	u32 total;
> +	u32 cur = 0;
> +	u32 len;
> +	u32 name_len;
> +	u32 data_len;
> +	u8 filetype;
> +	int slot;
> +	int ret;
> +
> +	path = btrfs_alloc_path();

Unhandled error (and there's one more in check_root_ref). Also, the
function can return negative values, but the caller does not propagate
the falue as it rather expects the bitmask of the specific errors.

Fixing that seems to be more intrusive, as the whole callchain does not
expect that consistently.

Please fix that and resend the whole patchset.

[PATCH 03/13] btrfs-progs: check: introduce function to check inode_ref

[Lu Fengqi]

Introduce a new function check_inode_ref() to check INODE_REF,
and call find_dir_item() to find the related DIR_ITEM/DIR_INDEX.

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 7e6f2a9..be35240 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -41,6 +41,7 @@
 #include "rbtree-utils.h"
 #include "backref.h"
 #include "ulist.h"
+#include "hash.h"
 
 enum task_position {
 	TASK_EXTENTS,
@@ -4016,6 +4017,82 @@ out:
 	return ret;
 }
 
+/*
+ * Traverse the given INODE_REF and call find_dir_item() to find related
+ * DIR_ITEM/DIR_INDEX.
+ *
+ * @root:	the root of the fs/file tree
+ * @ref_key:	the key of the INODE_REF
+ * @refs:	the count of INODE_REF
+ * @mode:	the st_mode of INODE_ITEM
+ *
+ * Return 0 if no error occurred.
+ */
+static int check_inode_ref(struct btrfs_root *root, struct btrfs_key *ref_key,
+			   struct extent_buffer *node, int slot, u64 *refs,
+			   int mode)
+{
+	struct btrfs_key key;
+	struct btrfs_inode_ref *ref;
+	char namebuf[BTRFS_NAME_LEN] = {0};
+	u32 total;
+	u32 cur = 0;
+	u32 len;
+	u32 name_len;
+	u64 index;
+	int ret, err = 0;
+
+	ref = btrfs_item_ptr(node, slot, struct btrfs_inode_ref);
+	total = btrfs_item_size_nr(node, slot);
+
+next:
+	/* Update inode ref count */
+	(*refs)++;
+
+	index = btrfs_inode_ref_index(node, ref);
+	name_len = btrfs_inode_ref_name_len(node, ref);
+	if (name_len <= BTRFS_NAME_LEN) {
+		len = name_len;
+	} else {
+		len = BTRFS_NAME_LEN;
+		fprintf(stderr,
+		"Warning: root %llu INODE_REF[%llu %llu] name too long\n",
+		root->objectid, ref_key->objectid, ref_key->offset);
+	}
+
+	read_extent_buffer(node, namebuf, (unsigned long)(ref + 1), len);
+
+	/* Check root dir ref name */
+	if (index == 0 && strncmp(namebuf, "..", name_len)) {
+		error(
+		"root %llu INODE_REF[%llu %llu] ROOT_DIR name shouldn't be %s",
+		root->objectid, ref_key->objectid, ref_key->offset, namebuf);
+		err |= ROOT_DIR_ERROR;
+	}
+
+	/* Find related dir_index */
+	key.objectid = ref_key->offset;
+	key.type = BTRFS_DIR_INDEX_KEY;
+	key.offset = index;
+	ret = find_dir_item(root, ref_key, &key, index, namebuf, len, mode);
+	err |= ret;
+
+	/* Find related dir_item */
+	key.objectid = ref_key->offset;
+	key.type = BTRFS_DIR_ITEM_KEY;
+	key.offset = btrfs_name_hash(namebuf, len);
+	ret = find_dir_item(root, ref_key, &key, index, namebuf, len, mode);
+	err |= ret;
+
+	len = sizeof(*ref) + name_len;
+	ref = (struct btrfs_inode_ref *)((char *)ref + len);
+	cur += len;
+	if (cur < total)
+		goto next;
+
+	return err;
+}
+
 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 {
 	struct rb_node *n;
-- 
2.7.4

[PATCH 04/13] btrfs-progs: check: introduce function to check inode_extref

[Lu Fengqi]

Introduce a new function check_inode_extref() to check INODE_EXTREF, and
call find_dir_item() to find the related DIR_ITEM/DIR_INDEX.

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

diff --git a/cmds-check.c b/cmds-check.c
index be35240..f9d5c8c 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -4093,6 +4093,85 @@ next:
 	return err;
 }
 
+/*
+ * Traverse the given INODE_EXTREF and call find_dir_item() to find related
+ * DIR_ITEM/DIR_INDEX.
+ *
+ * @root:	the root of the fs/file tree
+ * @ref_key:	the key of the INODE_EXTREF
+ * @refs:	the count of INODE_EXTREF
+ * @mode:	the st_mode of INODE_ITEM
+ *
+ * Return 0 if no error occurred.
+ */
+static int check_inode_extref(struct btrfs_root *root,
+			      struct btrfs_key *ref_key,
+			      struct extent_buffer *node, int slot, u64 *refs,
+			      int mode)
+{
+	struct btrfs_key key;
+	struct btrfs_inode_extref *extref;
+	char namebuf[BTRFS_NAME_LEN] = {0};
+	u32 total;
+	u32 cur = 0;
+	u32 len;
+	u32 name_len;
+	u64 index;
+	u64 parent;
+	int ret;
+	int err = 0;
+
+	extref = btrfs_item_ptr(node, slot, struct btrfs_inode_extref);
+	total = btrfs_item_size_nr(node, slot);
+
+next:
+	/* update inode ref count */
+	(*refs)++;
+	name_len = btrfs_inode_extref_name_len(node, extref);
+	index = btrfs_inode_extref_index(node, extref);
+	parent = btrfs_inode_extref_parent(node, extref);
+	if (name_len <= BTRFS_NAME_LEN) {
+		len = name_len;
+	} else {
+		len = BTRFS_NAME_LEN;
+		fprintf(stderr,
+		"Warning: root %llu INODE_EXTREF[%llu %llu] name too long\n",
+		root->objectid, ref_key->objectid, ref_key->offset);
+	}
+	read_extent_buffer(node, namebuf, (unsigned long)(extref + 1), len);
+
+	/* Check root dir ref name */
+	if (index == 0 && strncmp(namebuf, "..", name_len)) {
+		error(
+		"root %llu INODE_EXTREF[%llu %llu] ROOT_DIR name shouldn't be %s",
+		root->objectid, ref_key->objectid, ref_key->offset, namebuf);
+		err |= ROOT_DIR_ERROR;
+	}
+
+	/* find related dir_index */
+	key.objectid = parent;
+	key.type = BTRFS_DIR_INDEX_KEY;
+	key.offset = index;
+	ret = find_dir_item(root, ref_key, &key, index, namebuf, len, mode);
+	err |= ret;
+
+	/* find related dir_item */
+	key.objectid = parent;
+	key.type = BTRFS_DIR_ITEM_KEY;
+	key.offset = btrfs_name_hash(namebuf, len);
+	ret = find_dir_item(root, ref_key, &key, index, namebuf, len, mode);
+	err |= ret;
+
+	len = sizeof(*extref) + name_len;
+	extref = (struct btrfs_inode_extref *)((char *)extref + len);
+	cur += len;
+
+	if (cur < total)
+		goto next;
+
+	return err;
+}
+
 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 {
 	struct rb_node *n;
-- 
2.7.4

[PATCH 05/13] btrfs-progs: check: introduce function to find inode_ref

[Lu Fengqi]

Introduce a new function find_inode_ref() to find
INODE_REF/INODE_EXTREF for the given key, and check it with the
specified DIR_ITEM/DIR_INDEX match.

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

diff --git a/cmds-check.c b/cmds-check.c
index f9d5c8c..501c5e0 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -3882,6 +3882,7 @@ out:
 #define ROOT_DIR_ERROR		(1<<1)	/* bad root_dir */
 #define DIR_ITEM_MISSING	(1<<2)	/* DIR_ITEM not found */
 #define DIR_ITEM_MISMATCH	(1<<3)	/* DIR_ITEM found but not match */
+#define INODE_REF_MISSING	(1<<4)	/* INODE_REF/INODE_EXTREF not found */
 
 /*
  * Find DIR_ITEM/DIR_INDEX for the given key and check it with the specified
@@ -4172,6 +4173,157 @@ next:
 	return err;
 }
 
+/*
+ * Find INODE_REF/INODE_EXTREF for the given key and check it with the specified
+ * DIR_ITEM/DIR_INDEX match.
+ *
+ * @root:	the root of the fs/file tree
+ * @key:	the key of the INODE_REF/INODE_EXTREF
+ * @name:	the name in the INODE_REF/INODE_EXTREF
+ * @namelen:	the length of name in the INODE_REF/INODE_EXTREF
+ * @index:	the index in the INODE_REF/INODE_EXTREF, for DIR_ITEM set index
+ * to (u64)-1
+ * @ext_ref:	the EXTENDED_IREF feature
+ *
+ * Return 0 if no error occurred.
+ * Return INODE_REF_MISSING if couldn't find related INODE_REF/INODE_EXTREF for
+ * specified DIR_ITEM/DIR_INDEX.
+ */
+static int find_inode_ref(struct btrfs_root *root, struct btrfs_key *key,
+			  char *name, int namelen, u64 index,
+			  unsigned int ext_ref)
+{
+	struct btrfs_path path;
+	struct btrfs_inode_ref *ref;
+	struct btrfs_inode_extref *extref;
+	struct extent_buffer *node;
+	char ref_namebuf[BTRFS_NAME_LEN] = {0};
+	u32 total;
+	u32 cur = 0;
+	u32 len;
+	u32 ref_namelen;
+	u64 ref_index;
+	u64 parent;
+	u64 dir_id;
+	int slot;
+	int ret;
+
+	btrfs_init_path(&path);
+	ret = btrfs_search_slot(NULL, root, key, &path, 0, 0);
+	if (ret) {
+		ret = INODE_REF_MISSING;
+		goto extref;
+	}
+
+	node = path.nodes[0];
+	slot = path.slots[0];
+
+	ref = btrfs_item_ptr(node, slot, struct btrfs_inode_ref);
+	total = btrfs_item_size_nr(node, slot);
+
+	/* Iterate all entry of INODE_REF */
+	while (cur < total) {
+		ret = INODE_REF_MISSING;
+
+		ref_namelen = btrfs_inode_ref_name_len(node, ref);
+		ref_index = btrfs_inode_ref_index(node, ref);
+		if (index != (u64)-1 && index != ref_index)
+			goto next_ref;
+
+		if (ref_namelen <= BTRFS_NAME_LEN) {
+			len = ref_namelen;
+		} else {
+			len = BTRFS_NAME_LEN;
+			fprintf(stderr,
+				"Warning: root %llu INODE %s[%llu %llu] name too long\n",
+				root->objectid,
+				key->type == BTRFS_INODE_REF_KEY ?
+					"REF" : "EXTREF",
+				key->objectid, key->offset);
+		}
+		read_extent_buffer(node, ref_namebuf, (unsigned long)(ref + 1),
+				   len);
+
+		if (len != namelen || strncmp(ref_namebuf, name, len))
+			goto next_ref;
+
+		ret = 0;
+		goto out;
+next_ref:
+		len = sizeof(*ref) + ref_namelen;
+		ref = (struct btrfs_inode_ref *)((char *)ref + len);
+		cur += len;
+	}
+
+extref:
+	/* Skip if not support EXTENDED_IREF feature */
+	if (!ext_ref)
+		goto out;
+
+	btrfs_release_path(&path);
+	btrfs_init_path(&path);
+
+	dir_id = key->offset;
+	key->type = BTRFS_INODE_EXTREF_KEY;
+	key->offset = btrfs_extref_hash(dir_id, name, namelen);
+
+	ret = btrfs_search_slot(NULL, root, key, &path, 0, 0);
+	if (ret) {
+		ret = INODE_REF_MISSING;
+		goto out;
+	}
+
+	node = path.nodes[0];
+	slot = path.slots[0];
+
+	extref = btrfs_item_ptr(node, slot, struct btrfs_inode_extref);
+	cur = 0;
+	total = btrfs_item_size_nr(node, slot);
+
+	/* Iterate all entry of INODE_EXTREF */
+	while (cur < total) {
+		ret = INODE_REF_MISSING;
+
+		ref_namelen = btrfs_inode_extref_name_len(node, extref);
+		ref_index = btrfs_inode_extref_index(node, extref);
+		parent = btrfs_inode_extref_parent(node, extref);
+		if (index != (u64)-1 && index != ref_index)
+			goto next_extref;
+
+		if (parent != dir_id)
+			goto next_extref;
+
+		if (ref_namelen <= BTRFS_NAME_LEN) {
+			len = ref_namelen;
+		} else {
+			len = BTRFS_NAME_LEN;
+			fprintf(stderr,
+				"Warning: root %llu INODE %s[%llu %llu] name too long\n",
+				root->objectid,
+				key->type == BTRFS_INODE_REF_KEY ?
+					"REF" : "EXTREF",
+				key->objectid, key->offset);
+		}
+		read_extent_buffer(node, ref_namebuf,
+				   (unsigned long)(extref + 1), len);
+
+		if (len != namelen || strncmp(ref_namebuf, name, len))
+			goto next_extref;
+
+		ret = 0;
+		goto out;
+
+next_extref:
+		len = sizeof(*extref) + ref_namelen;
+		extref = (struct btrfs_inode_extref *)((char *)extref + len);
+		cur += len;
+
+	}
+out:
+	btrfs_release_path(&path);
+	return ret;
+}
+
 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 {
 	struct rb_node *n;
-- 
2.7.4

[PATCH 06/13] btrfs-progs: check: introduce a function to check dir_item

[Lu Fengqi]

Introduce a new function check_dir_item() to check DIR_ITEM/DIR_INDEX,
and call find_inode_ref() to find the related INODE_REF/INODE_EXTREF.

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

diff --git a/cmds-check.c b/cmds-check.c
index 501c5e0..ad261f2 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -3883,6 +3883,8 @@ out:
 #define DIR_ITEM_MISSING	(1<<2)	/* DIR_ITEM not found */
 #define DIR_ITEM_MISMATCH	(1<<3)	/* DIR_ITEM found but not match */
 #define INODE_REF_MISSING	(1<<4)	/* INODE_REF/INODE_EXTREF not found */
+#define INODE_ITEM_MISSING	(1<<5)	/* INODE_ITEM not found */
+#define INODE_ITEM_MISMATCH	(1<<6)	/* INODE_ITEM found but not match */
 
 /*
  * Find DIR_ITEM/DIR_INDEX for the given key and check it with the specified
@@ -4324,6 +4326,141 @@ out:
 	return ret;
 }
 
+/*
+ * Traverse the given DIR_ITEM/DIR_INDEX and check related INODE_ITEM and
+ * call find_inode_ref() to check related INODE_REF/INODE_EXTREF.
+ *
+ * @root:	the root of the fs/file tree
+ * @key:	the key of the INODE_REF/INODE_EXTREF
+ * @size:	the st_size of the INODE_ITEM
+ * @ext_ref:	the EXTENDED_IREF feature
+ *
+ * Return 0 if no error occurred.
+ */
+static int check_dir_item(struct btrfs_root *root, struct btrfs_key *key,
+			  struct extent_buffer *node, int slot, u64 *size,
+			  unsigned int ext_ref)
+{
+	struct btrfs_dir_item *di;
+	struct btrfs_inode_item *ii;
+	struct btrfs_path path;
+	struct btrfs_key location;
+	char namebuf[BTRFS_NAME_LEN] = {0};
+	u32 total;
+	u32 cur = 0;
+	u32 len;
+	u32 name_len;
+	u32 data_len;
+	u8 filetype;
+	u32 mode;
+	u64 index;
+	int ret;
+	int err = 0;
+
+	/*
+	 * For DIR_ITEM set index to (u64)-1, so that find_inode_ref
+	 * ignore index check.
+	 */
+	index = (key->type == BTRFS_DIR_INDEX_KEY) ? key->offset : (u64)-1;
+
+	di = btrfs_item_ptr(node, slot, struct btrfs_dir_item);
+	total = btrfs_item_size_nr(node, slot);
+
+	while (cur < total) {
+		data_len = btrfs_dir_data_len(node, di);
+		if (data_len)
+			error(
+			"root %llu %s[%llu %llu] data_len shouldn't be %u",
+			root->objectid,
+			key->type == BTRFS_DIR_ITEM_KEY ?
+			"DIR_ITEM" : "DIR_INDEX",
+			key->objectid, key->offset, data_len);
+
+		name_len = btrfs_dir_name_len(node, di);
+		if (name_len <= BTRFS_NAME_LEN) {
+			len = name_len;
+		} else {
+			len = BTRFS_NAME_LEN;
+			fprintf(stderr,
+				"Warning: root %llu %s[%llu %llu] name too long\n",
+				root->objectid,
+				key->type == BTRFS_DIR_ITEM_KEY ?
+				"DIR_ITEM" : "DIR_INDEX",
+				key->objectid, key->offset);
+		}
+		(*size) += name_len;
+
+		read_extent_buffer(node, namebuf, (unsigned long)(di + 1), len);
+		filetype = btrfs_dir_type(node, di);
+
+		btrfs_init_path(&path);
+		btrfs_dir_item_key_to_cpu(node, di, &location);
+
+		/* Ignore related ROOT_ITEM check */
+		if (location.type == BTRFS_ROOT_ITEM_KEY)
+			goto next;
+
+		/* Check relative INODE_ITEM(existence/filetype) */
+		ret = btrfs_search_slot(NULL, root, &location, &path, 0, 0);
+		if (ret) {
+			err |= INODE_ITEM_MISSING;
+			error(
+			"root %llu %s[%llu %llu] couldn't find relative INODE_ITEM[%llu] namelen %u filename %s filetype %x",
+			root->objectid,
+			key->type == BTRFS_DIR_ITEM_KEY ?
+			"DIR_ITEM" : "DIR_INDEX",
+			key->objectid, key->offset, location.objectid,
+			name_len, namebuf, filetype);
+			goto next;
+		}
+
+		ii = btrfs_item_ptr(path.nodes[0], path.slots[0],
+				    struct btrfs_inode_item);
+		mode = btrfs_inode_mode(path.nodes[0], ii);
+
+		if (imode_to_type(mode) != filetype) {
+			err |= INODE_ITEM_MISMATCH;
+			error(
+			"root %llu %s[%llu %llu] relative INODE_ITEM filetype mismatch namelen %u filename %s filetype %d",
+			root->objectid,
+			key->type == BTRFS_DIR_ITEM_KEY ?
+			"DIR_ITEM" : "DIR_INDEX",
+			key->objectid, key->offset, name_len, namebuf,
+			filetype);
+		}
+
+		/* Check relative INODE_REF/INODE_EXTREF */
+		location.type = BTRFS_INODE_REF_KEY;
+		location.offset = key->objectid;
+		ret = find_inode_ref(root, &location, namebuf, len,
+				       index, ext_ref);
+		err |= ret;
+		if (ret & INODE_REF_MISSING)
+			error(
+			"root %llu %s[%llu %llu] relative INODE_REF missing namelen %u filename %s filetype %d",
+			root->objectid,
+			key->type == BTRFS_DIR_ITEM_KEY ?
+			"DIR_ITEM" : "DIR_INDEX",
+			key->objectid, key->offset, name_len, namebuf,
+			filetype);
+
+next:
+		btrfs_release_path(&path);
+		len = sizeof(*di) + name_len + data_len;
+		di = (struct btrfs_dir_item *)((char *)di + len);
+		cur += len;
+
+		if (key->type == BTRFS_DIR_INDEX_KEY && cur < total) {
+			error(
+			"root %llu DIR_INDEX[%llu %llu] should contain only one entry",
+			root->objectid, key->objectid, key->offset);
+			break;
+		}
+	}
+
+	return err;
+}
+
 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 {
 	struct rb_node *n;
-- 
2.7.4

[PATCH 07/13] btrfs-progs: check: introduce function to check file extent

[Lu Fengqi]

Introduce a new function check_file_extent() to check file extent,
such as datasum, hole, size.

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

diff --git a/cmds-check.c b/cmds-check.c
index ad261f2..28ee8b6 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -3885,6 +3885,9 @@ out:
 #define INODE_REF_MISSING	(1<<4)	/* INODE_REF/INODE_EXTREF not found */
 #define INODE_ITEM_MISSING	(1<<5)	/* INODE_ITEM not found */
 #define INODE_ITEM_MISMATCH	(1<<6)	/* INODE_ITEM found but not match */
+#define FILE_EXTENT_ERROR	(1<<7)	/* bad file extent */
+#define ODD_CSUM_ITEM		(1<<8)	/* CSUM_ITEM ERROR */
+#define CSUM_ITEM_MISSING	(1<<9)	/* CSUM_ITEM not found */
 
 /*
  * Find DIR_ITEM/DIR_INDEX for the given key and check it with the specified
@@ -4461,6 +4464,97 @@ next:
 	return err;
 }
 
+/*
+ * Check file extent datasum/hole, update the size of the file extents,
+ * check and update the last offset of the file extent.
+ *
+ * @root:	the root of fs/file tree.
+ * @fkey:	the key of the file extent.
+ * @nodatasum:	INODE_NODATASUM feature.
+ * @size:	the sum of all EXTENT_DATA items size for this inode.
+ * @end:	the offset of the last extent.
+ *
+ * Return 0 if no error occurred.
+ */
+static int check_file_extent(struct btrfs_root *root, struct btrfs_key *fkey,
+			     struct extent_buffer *node, int slot,
+			     unsigned int nodatasum, u64 *size, u64 *end)
+{
+	struct btrfs_file_extent_item *fi;
+	u64 disk_bytenr;
+	u64 disk_num_bytes;
+	u64 extent_num_bytes;
+	u64 found;
+	unsigned int extent_type;
+	unsigned int is_hole;
+	int ret;
+	int err = 0;
+
+	fi = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item);
+
+	extent_type = btrfs_file_extent_type(node, fi);
+	/* Skip if file extent is inline */
+	if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
+		extent_num_bytes = btrfs_file_extent_inline_len(node, slot, fi);
+		if (extent_num_bytes == 0)
+			err |= FILE_EXTENT_ERROR;
+		*size += extent_num_bytes;
+		return err;
+	}
+
+	/* Check extent type */
+	if (extent_type != BTRFS_FILE_EXTENT_REG &&
+			extent_type != BTRFS_FILE_EXTENT_PREALLOC) {
+		err |= FILE_EXTENT_ERROR;
+		error("root %llu EXTENT_DATA[%llu %llu] type bad",
+		      root->objectid, fkey->objectid, fkey->offset);
+		return err;
+	}
+
+	/* Check REG_EXTENT/PREALLOC_EXTENT */
+	disk_bytenr = btrfs_file_extent_disk_bytenr(node, fi);
+	disk_num_bytes = btrfs_file_extent_disk_num_bytes(node, fi);
+	extent_num_bytes = btrfs_file_extent_num_bytes(node, fi);
+	is_hole = (disk_bytenr == 0) && (disk_num_bytes == 0);
+
+	/* Check EXTENT_DATA datasum */
+	ret = count_csum_range(root, disk_bytenr, disk_num_bytes, &found);
+	if (found > 0 && nodatasum) {
+		err |= ODD_CSUM_ITEM;
+		error(
+		"root %llu EXTENT_DATA[%llu %llu] nodatasum shouldn't have datasum",
+		root->objectid, fkey->objectid, fkey->offset);
+	} else if (extent_type == BTRFS_FILE_EXTENT_REG && !nodatasum &&
+		   !is_hole &&
+		   (ret < 0 || found == 0 || found < disk_num_bytes)) {
+		err |= CSUM_ITEM_MISSING;
+		error("root %llu EXTENT_DATA[%llu %llu] datasum missing",
+		      root->objectid, fkey->objectid, fkey->offset);
+	} else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC && found > 0) {
+		err |= ODD_CSUM_ITEM;
+		error(
+		"root %llu EXTENT_DATA[%llu %llu] prealloc shouldn't have datasum",
+		root->objectid, fkey->objectid, fkey->offset);
+	}
+
+	/* Check EXTENT_DATA hole */
+	if (no_holes && is_hole) {
+		err |= FILE_EXTENT_ERROR;
+		error("root %llu EXTENT_DATA[%llu %llu] shouldn't be hole",
+				root->objectid, fkey->objectid, fkey->offset);
+	} else if (!no_holes && *end != fkey->offset) {
+		err |= FILE_EXTENT_ERROR;
+		error("root %llu EXTENT_DATA[%llu %llu] interrupt",
+				root->objectid, fkey->objectid, fkey->offset);
+	}
+
+	*end += extent_num_bytes;
+	if (!is_hole)
+		*size += extent_num_bytes;
+
+	return err;
+}
+
 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 {
 	struct rb_node *n;
-- 
2.7.4

[PATCH 08/13] btrfs-progs: check: introduce function to check inode item

[Lu Fengqi]

Introduce a new function check_inode_item() to check INODE_ITEM and
related ITEMs that have the same inode id.

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

diff --git a/cmds-check.c b/cmds-check.c
index 28ee8b6..a9a5c08 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -3888,6 +3888,11 @@ out:
 #define FILE_EXTENT_ERROR	(1<<7)	/* bad file extent */
 #define ODD_CSUM_ITEM		(1<<8)	/* CSUM_ITEM ERROR */
 #define CSUM_ITEM_MISSING	(1<<9)	/* CSUM_ITEM not found */
+#define LINK_COUNT_ERROR	(1<<10)	/* INODE_ITEM nlink count error */
+#define NBYTES_ERROR		(1<<11)	/* INODE_ITEM nbytes count error */
+#define ISIZE_ERROR		(1<<12)	/* INODE_ITEM size count error */
+#define ORPHAN_ITEM		(1<<13) /* INODE_ITEM no reference */
+#define LAST_ITEM		(1<<15)	/* Complete this tree traversal */
 
 /*
  * Find DIR_ITEM/DIR_INDEX for the given key and check it with the specified
@@ -4555,6 +4560,171 @@ static int check_file_extent(struct btrfs_root *root, struct btrfs_key *fkey,
 	return err;
 }
 
+/*
+ * Check INODE_ITEM and related ITEMs(the same inode id)
+ * 1. check link count
+ * 2. check inode ref/extref
+ * 3. check dir item/index
+ *
+ * @ext_ref:	the EXTENDED_IREF feature
+ *
+ * Return 0 if no error occurred.
+ * Return LAST_ITEM if complete the tree traversal.
+ * Return -EIO if the tree traversal failed.
+ */
+static int check_inode_item(struct btrfs_root *root, struct btrfs_path *path,
+			    unsigned int ext_ref)
+{
+	struct extent_buffer *node;
+	struct btrfs_inode_item *ii;
+	struct btrfs_key key;
+	u64 inode_id;
+	u32 mode;
+	u64 nlink;
+	u64 nbytes;
+	u64 isize;
+	u64 size = 0;
+	u64 refs = 0;
+	u64 extent_end = 0;
+	u64 extent_size = 0;
+	unsigned int dir;
+	unsigned int nodatasum;
+	int slot;
+	int ret;
+	int err = 0;
+
+	node = path->nodes[0];
+	slot = path->slots[0];
+
+	btrfs_item_key_to_cpu(node, &key, slot);
+	inode_id = key.objectid;
+
+	ii = btrfs_item_ptr(node, slot, struct btrfs_inode_item);
+	isize = btrfs_inode_size(node, ii);
+	nbytes = btrfs_inode_nbytes(node, ii);
+	mode = btrfs_inode_mode(node, ii);
+	dir = imode_to_type(mode) == BTRFS_FT_DIR;
+	nlink = btrfs_inode_nlink(node, ii);
+	nodatasum = btrfs_inode_flags(node, ii) & BTRFS_INODE_NODATASUM;
+
+	while (1) {
+		ret = btrfs_next_item(root, path);
+		if (ret < 0) {
+			err = -EIO;
+			error("btrfs_next_item corrupt root %llu inode %llu",
+					root->objectid, inode_id);
+			goto out;
+		} else if (ret > 0) {
+			err |= LAST_ITEM;
+			goto out;
+		}
+
+		node = path->nodes[0];
+		slot = path->slots[0];
+		btrfs_item_key_to_cpu(node, &key, slot);
+		if (key.objectid != inode_id)
+			goto out;
+
+		switch (key.type) {
+		case BTRFS_INODE_REF_KEY:
+			ret = check_inode_ref(root, &key, node, slot, &refs,
+					      mode);
+			err |= ret;
+			break;
+		case BTRFS_INODE_EXTREF_KEY:
+			if (key.type == BTRFS_INODE_EXTREF_KEY && !ext_ref)
+				fprintf(stderr,
+				"Warning: root %llu EXTREF[%llu %llu] isn't supported\n",
+					root->objectid, key.objectid,
+					key.offset);
+			ret = check_inode_extref(root, &key, node, slot, &refs,
+						 mode);
+			err |= ret;
+			break;
+		case BTRFS_DIR_ITEM_KEY:
+		case BTRFS_DIR_INDEX_KEY:
+			if (!dir) {
+				fprintf(stderr,
+				"Warning: root %llu INODE[%llu] mode %u shouldn't have DIR_INDEX[%llu %llu]\n",
+					root->objectid,	inode_id,
+					imode_to_type(mode), key.objectid,
+					key.offset);
+			}
+			ret = check_dir_item(root, &key, node, slot, &size,
+					     ext_ref);
+			err |= ret;
+			break;
+		case BTRFS_EXTENT_DATA_KEY:
+			if (dir) {
+				fprintf(stderr,
+				"Warning: root %llu DIR INODE[%llu] shouldn't EXTENT_DATA[%llu %llu]\n",
+					root->objectid, inode_id, key.objectid,
+					key.offset);
+			}
+			ret = check_file_extent(root, &key, node, slot,
+						nodatasum, &extent_size,
+						&extent_end);
+			err |= ret;
+			break;
+		case BTRFS_XATTR_ITEM_KEY:
+			break;
+		default:
+			error("ITEM[%llu %u %llu] UNKNOWN TYPE",
+			      key.objectid, key.type, key.offset);
+		}
+	}
+
+out:
+	/* verify INODE_ITEM nlink/isize/nbytes */
+	if (dir) {
+		if (nlink != 1) {
+			err |= LINK_COUNT_ERROR;
+			error(
+			"root %llu DIR INODE[%llu] shouldn't have more than one link(%llu)",
+			root->objectid, inode_id, nlink);
+		}
+
+		if (!IS_ALIGNED(nbytes, root->nodesize)) {
+			err |= NBYTES_ERROR;
+			error(
+			"root %llu DIR INODE[%llu] nbytes shouldn't be %llu",
+			root->objectid,	inode_id, nbytes);
+		}
+
+		if (isize != size) {
+			err |= ISIZE_ERROR;
+			error(
+			"root %llu DIR INODE [%llu] size(%llu) not equal to %llu",
+			root->objectid, inode_id, isize, size);
+		}
+	} else {
+		if (nlink != refs) {
+			err |= LINK_COUNT_ERROR;
+			error(
+			"root %llu INODE[%llu] nlink(%llu) not equal to inode_refs(%llu)",
+			root->objectid, inode_id, nlink, refs);
+		} else if (!nlink) {
+			err |= ORPHAN_ITEM;
+		}
+
+		if (!nbytes && !no_holes && extent_end != isize) {
+			err |= NBYTES_ERROR;
+			error(
+			"root %llu INODE[%llu] size (%llu) should have a file extent hole",
+			root->objectid, inode_id, isize);
+		}
+
+		if (nbytes != extent_size) {
+			err |= NBYTES_ERROR;
+			error(
+			"root %llu INODE[%llu] nbytes(%llu) not equal to extent_size(%llu)",
+			root->objectid, inode_id, nbytes, extent_size);
+		}
+	}
+
+	return err;
+}
+
 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 {
 	struct rb_node *n;
-- 
2.7.4

[PATCH 09/13] btrfs-progs: check: introduce function to check fs root

[Lu Fengqi]

Introduce a new function check_fs_root_v2() to check fs root,
and call check_inode_item to check the items in the tree.

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

diff --git a/cmds-check.c b/cmds-check.c
index a9a5c08..756e7a1 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -3892,6 +3892,7 @@ out:
 #define NBYTES_ERROR		(1<<11)	/* INODE_ITEM nbytes count error */
 #define ISIZE_ERROR		(1<<12)	/* INODE_ITEM size count error */
 #define ORPHAN_ITEM		(1<<13) /* INODE_ITEM no reference */
+#define NO_INODE_ITEM		(1<<14) /* no inode_item */
 #define LAST_ITEM		(1<<15)	/* Complete this tree traversal */
 
 /*
@@ -4725,6 +4726,81 @@ out:
 	return err;
 }
 
+/*
+ * Iterate all item on the tree and call check_inode_item() to check.
+ *
+ * @root:	the root of the tree to be checked.
+ * @ext_ref:	the EXTENDED_IREF feature
+ *
+ * Return 0 if no error found.
+ */
+static int check_fs_root_v2(struct btrfs_root *root, unsigned int ext_ref)
+{
+	struct btrfs_path *path;
+	struct btrfs_key key;
+	u64 inode_id;
+	int ret, err = 0;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	key.objectid = 0;
+	key.type = 0;
+	key.offset = 0;
+
+	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
+	if (ret < 0) {
+		err = ret;
+		goto out;
+	}
+
+	while (1) {
+		btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+
+		/*
+		 * All check must start with inode item, skip if not
+		 */
+		if (btrfs_key_type(&key) == BTRFS_INODE_ITEM_KEY) {
+			ret = check_inode_item(root, path, ext_ref);
+			if (ret == -EIO)
+				goto out;
+			err |= ret;
+			if (err & LAST_ITEM)
+				goto out;
+		} else {
+			error(
+			"root %llu ITEM[%llu %u %llu] isn't INODE_ITEM, skip to next inode",
+			root->objectid, key.objectid, key.type, key.offset);
+			goto skip;
+		}
+
+		continue;
+
+skip:
+		err |= NO_INODE_ITEM;
+		inode_id = key.objectid;
+
+		/* skip to next inode */
+		do {
+			ret = btrfs_next_item(root, path);
+			if (ret > 0) {
+				goto out;
+			} else if (ret < 0) {
+				err = ret;
+				goto out;
+			}
+			btrfs_item_key_to_cpu(path->nodes[0], &key,
+					      path->slots[0]);
+		} while (inode_id == key.objectid);
+	}
+
+out:
+	err &= ~LAST_ITEM;
+	btrfs_free_path(path);
+	return err;
+}
+
 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 {
 	struct rb_node *n;
-- 
2.7.4

[PATCH 10/13] btrfs-progs: check: introduce function to check root ref

[Lu Fengqi]

Introduce a new function check_root_ref() to check
root_ref/root_backref.

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

diff --git a/cmds-check.c b/cmds-check.c
index 756e7a1..4dc9345 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -3894,6 +3894,8 @@ out:
 #define ORPHAN_ITEM		(1<<13) /* INODE_ITEM no reference */
 #define NO_INODE_ITEM		(1<<14) /* no inode_item */
 #define LAST_ITEM		(1<<15)	/* Complete this tree traversal */
+#define ROOT_REF_MISSING	(1<<16)	/* ROOT_REF not found */
+#define ROOT_REF_MISMATCH	(1<<17)	/* ROOT_REF found but not match */
 
 /*
  * Find DIR_ITEM/DIR_INDEX for the given key and check it with the specified
@@ -4801,6 +4803,97 @@ out:
 	return err;
 }
 
+/*
+ * Find the relative ref for root_ref and root_backref.
+ *
+ * @root:	the root of the root tree.
+ * @ref_key:	the key of the root ref.
+ *
+ * Return 0 if no error occurred.
+ */
+static int check_root_ref(struct btrfs_root *root, struct btrfs_key *ref_key,
+			  struct extent_buffer *node, int slot)
+{
+	struct btrfs_path *path;
+	struct btrfs_key key;
+	struct btrfs_root_ref *ref;
+	struct btrfs_root_ref *backref;
+	char ref_name[BTRFS_NAME_LEN];
+	char backref_name[BTRFS_NAME_LEN];
+	u64 ref_dirid;
+	u64 ref_seq;
+	u32 ref_namelen;
+	u64 backref_dirid;
+	u64 backref_seq;
+	u32 backref_namelen;
+	u32 len;
+	int ret;
+	int err = 0;
+
+	ref = btrfs_item_ptr(node, slot, struct btrfs_root_ref);
+	ref_dirid = btrfs_root_ref_dirid(node, ref);
+	ref_seq = btrfs_root_ref_sequence(node, ref);
+	ref_namelen = btrfs_root_ref_name_len(node, ref);
+
+	if (ref_namelen <= BTRFS_NAME_LEN) {
+		len = ref_namelen;
+	} else {
+		len = BTRFS_NAME_LEN;
+		fprintf(stderr, "Warning: %s[%llu %llu] ref_name too long",
+			ref_key->type == BTRFS_ROOT_REF_KEY ?
+			"ROOT_REF" : "ROOT_BACKREF", ref_key->objectid,
+			ref_key->offset);
+	}
+	read_extent_buffer(node, ref_name, (unsigned long)(ref + 1), len);
+
+	/* Find relative root_ref */
+	key.objectid = ref_key->offset;
+	key.type = BTRFS_ROOT_BACKREF_KEY + BTRFS_ROOT_REF_KEY - ref_key->type;
+	key.offset = ref_key->objectid;
+
+	path = btrfs_alloc_path();
+	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
+	if (ret) {
+		err |= ROOT_REF_MISSING;
+		error("%s[%llu %llu] couldn't find relative ref",
+		      ref_key->type == BTRFS_ROOT_REF_KEY ?
+		      "ROOT_REF" : "ROOT_BACKREF",
+		      ref_key->objectid, ref_key->offset);
+		goto out;
+	}
+
+	backref = btrfs_item_ptr(path->nodes[0], path->slots[0],
+				 struct btrfs_root_ref);
+	backref_dirid = btrfs_root_ref_dirid(path->nodes[0], backref);
+	backref_seq = btrfs_root_ref_sequence(path->nodes[0], backref);
+	backref_namelen = btrfs_root_ref_name_len(path->nodes[0], backref);
+
+	if (backref_namelen <= BTRFS_NAME_LEN) {
+		len = backref_namelen;
+	} else {
+		len = BTRFS_NAME_LEN;
+		fprintf(stderr, "Warning: %s[%llu %llu] ref_name too long",
+			key.type == BTRFS_ROOT_REF_KEY ?
+			"ROOT_REF" : "ROOT_BACKREF",
+			key.objectid, key.offset);
+	}
+	read_extent_buffer(path->nodes[0], backref_name,
+			   (unsigned long)(backref + 1), len);
+
+	if (ref_dirid != backref_dirid || ref_seq != backref_seq ||
+	    ref_namelen != backref_namelen ||
+	    strncmp(ref_name, backref_name, len)) {
+		err |= ROOT_REF_MISMATCH;
+		error("%s[%llu %llu] mismatch relative ref",
+		      ref_key->type == BTRFS_ROOT_REF_KEY ?
+		      "ROOT_REF" : "ROOT_BACKREF",
+		      ref_key->objectid, ref_key->offset);
+	}
+out:
+	btrfs_free_path(path);
+	return err;
+}
+
 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 {
 	struct rb_node *n;
-- 
2.7.4

[PATCH 11/13] btrfs-progs: check: introduce low_memory mode fs_tree check

[Lu Fengqi]

Introduce a new function check_fs_roots_v2() for check fs_tree in
low_memory mode. It call check_fs_root_v2() to check fs_root, and call
check_root_ref() to check root_ref.

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

diff --git a/cmds-check.c b/cmds-check.c
index 4dc9345..e43dce1 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -4818,8 +4818,8 @@ static int check_root_ref(struct btrfs_root *root, struct btrfs_key *ref_key,
 	struct btrfs_key key;
 	struct btrfs_root_ref *ref;
 	struct btrfs_root_ref *backref;
-	char ref_name[BTRFS_NAME_LEN];
-	char backref_name[BTRFS_NAME_LEN];
+	char ref_name[BTRFS_NAME_LEN] = {0};
+	char backref_name[BTRFS_NAME_LEN] = {0};
 	u64 ref_dirid;
 	u64 ref_seq;
 	u32 ref_namelen;
@@ -4894,6 +4894,94 @@ out:
 	return err;
 }
 
+/*
+ * Check all fs/file tree in low_memory mode.
+ *
+ * 1. for fs tree root item, call check_fs_root_v2()
+ * 2. for fs tree root ref/backref, call check_root_ref()
+ *
+ * Return 0 if no error occurred.
+ */
+static int check_fs_roots_v2(struct btrfs_fs_info *fs_info)
+{
+	struct btrfs_root *tree_root = fs_info->tree_root;
+	struct btrfs_root *cur_root = NULL;
+	struct btrfs_path *path;
+	struct btrfs_key key;
+	struct extent_buffer *node;
+	unsigned int ext_ref;
+	int slot;
+	int ret;
+	int err = 0;
+
+	ext_ref = btrfs_fs_incompat(fs_info,
+				    BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF);
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	key.objectid = BTRFS_FS_TREE_OBJECTID;
+	key.offset = 0;
+	key.type = BTRFS_ROOT_ITEM_KEY;
+
+	ret = btrfs_search_slot(NULL, tree_root, &key, path, 0, 0);
+	if (ret < 0) {
+		err = ret;
+		goto out;
+	} else if (ret > 0) {
+		err = -ENOENT;
+		goto out;
+	}
+
+	while (1) {
+		node = path->nodes[0];
+		slot = path->slots[0];
+		btrfs_item_key_to_cpu(node, &key, slot);
+		if (key.objectid > BTRFS_LAST_FREE_OBJECTID)
+			goto out;
+		if (key.type == BTRFS_ROOT_ITEM_KEY &&
+		    fs_root_objectid(key.objectid)) {
+			if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
+				cur_root = btrfs_read_fs_root_no_cache(fs_info,
+								       &key);
+			} else {
+				key.offset = (u64)-1;
+				cur_root = btrfs_read_fs_root(fs_info, &key);
+			}
+
+			if (IS_ERR(cur_root)) {
+				error("Fail to read fs/subvol tree: %lld",
+				      key.objectid);
+				err = -EIO;
+				goto next;
+			}
+
+			ret = check_fs_root_v2(cur_root, ext_ref);
+			err |= ret;
+
+			if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)
+				btrfs_free_fs_root(cur_root);
+		} else if (key.type == BTRFS_ROOT_REF_KEY ||
+				key.type == BTRFS_ROOT_BACKREF_KEY) {
+			ret = check_root_ref(tree_root, &key, node, slot);
+			err |= ret;
+		}
+next:
+		ret = btrfs_next_item(tree_root, path);
+		if (ret > 0)
+			goto out;
+		if (ret < 0) {
+			err = ret;
+			goto out;
+		}
+	}
+
+out:
+	btrfs_free_path(path);
+	return err;
+}
+
 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 {
 	struct rb_node *n;
@@ -12429,7 +12517,10 @@ int cmd_check(int argc, char **argv)
 				     BTRFS_FEATURE_INCOMPAT_NO_HOLES);
 	if (!ctx.progress_enabled)
 		fprintf(stderr, "checking fs roots\n");
-	ret = check_fs_roots(root, &root_cache);
+	if (low_memory)
+		ret = check_fs_roots_v2(root->fs_info);
+	else
+		ret = check_fs_roots(root, &root_cache);
 	if (ret)
 		goto out;
 
@@ -12439,9 +12530,11 @@ int cmd_check(int argc, char **argv)
 		goto out;
 
 	fprintf(stderr, "checking root refs\n");
-	ret = check_root_refs(root, &root_cache);
-	if (ret)
-		goto out;
+	if (!low_memory) {
+		ret = check_root_refs(root, &root_cache);
+		if (ret)
+			goto out;
+	}
 
 	while (repair && !list_empty(&root->fs_info->recow_ebs)) {
 		struct extent_buffer *eb;
-- 
2.7.4

[PATCH 12/13] btrfs-progs: check: fix the return value bug of cmd_check()

[Lu Fengqi]

The function cmd_check() is called by the main function of btrfs.c, its
return value will be returned by exit(). Resulting in the loss of
significant bits in some cases, for example this value is greater than
0377. If use a bool value "err" to store all of the return value, this
will solve the problem.

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, 35 insertions(+), 7 deletions(-)

diff --git a/cmds-check.c b/cmds-check.c
index e43dce1..c52eebc 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -12227,6 +12227,7 @@ int cmd_check(int argc, char **argv)
 	u64 chunk_root_bytenr = 0;
 	char uuidbuf[BTRFS_UUID_UNPARSED_SIZE];
 	int ret;
+	int err = 0;
 	u64 num;
 	int init_csum_tree = 0;
 	int readonly = 0;
@@ -12356,10 +12357,12 @@ int cmd_check(int argc, char **argv)
 
 	if((ret = check_mounted(argv[optind])) < 0) {
 		fprintf(stderr, "Could not check mount status: %s\n", strerror(-ret));
+		err |= !!ret;
 		goto err_out;
 	} else if(ret) {
 		fprintf(stderr, "%s is currently mounted. Aborting.\n", argv[optind]);
 		ret = -EBUSY;
+		err |= !!ret;
 		goto err_out;
 	}
 
@@ -12372,6 +12375,7 @@ int cmd_check(int argc, char **argv)
 	if (!info) {
 		fprintf(stderr, "Couldn't open file system\n");
 		ret = -EIO;
+		err |= !!ret;
 		goto err_out;
 	}
 
@@ -12386,9 +12390,11 @@ int cmd_check(int argc, char **argv)
 		ret = ask_user("repair mode will force to clear out log tree, Are you sure?");
 		if (!ret) {
 			ret = 1;
+			err |= !!ret;
 			goto close_out;
 		}
 		ret = zero_log_tree(root);
+		err |= !!ret;
 		if (ret) {
 			fprintf(stderr, "fail to zero log tree\n");
 			goto close_out;
@@ -12400,6 +12406,7 @@ int cmd_check(int argc, char **argv)
 		printf("Print quota groups for %s\nUUID: %s\n", argv[optind],
 		       uuidbuf);
 		ret = qgroup_verify_all(info);
+		err |= !!ret;
 		if (ret == 0)
 			report_qgroups(1);
 		goto close_out;
@@ -12408,6 +12415,7 @@ int cmd_check(int argc, char **argv)
 		printf("Print extent state for subvolume %llu on %s\nUUID: %s\n",
 		       subvolid, argv[optind], uuidbuf);
 		ret = print_extent_state(info, subvolid);
+		err |= !!ret;
 		goto close_out;
 	}
 	printf("Checking filesystem on %s\nUUID: %s\n", argv[optind], uuidbuf);
@@ -12417,6 +12425,7 @@ int cmd_check(int argc, char **argv)
 	    !extent_buffer_uptodate(info->chunk_root->node)) {
 		fprintf(stderr, "Critical roots corrupted, unable to fsck the FS\n");
 		ret = -EIO;
+		err |= !!ret;
 		goto close_out;
 	}
 
@@ -12427,12 +12436,14 @@ int cmd_check(int argc, char **argv)
 		if (IS_ERR(trans)) {
 			fprintf(stderr, "Error starting transaction\n");
 			ret = PTR_ERR(trans);
+			err |= !!ret;
 			goto close_out;
 		}
 
 		if (init_extent_tree) {
 			printf("Creating a new extent tree\n");
 			ret = reinit_extent_tree(trans, info);
+			err |= !!ret;
 			if (ret)
 				goto close_out;
 		}
@@ -12443,6 +12454,7 @@ int cmd_check(int argc, char **argv)
 			if (ret) {
 				fprintf(stderr, "crc root initialization failed\n");
 				ret = -EIO;
+				err |= !!ret;
 				goto close_out;
 			}
 
@@ -12458,17 +12470,20 @@ int cmd_check(int argc, char **argv)
 		 * extent entries for all of the items it finds.
 		 */
 		ret = btrfs_commit_transaction(trans, info->extent_root);
+		err |= !!ret;
 		if (ret)
 			goto close_out;
 	}
 	if (!extent_buffer_uptodate(info->extent_root->node)) {
 		fprintf(stderr, "Critical roots corrupted, unable to fsck the FS\n");
 		ret = -EIO;
+		err |= !!ret;
 		goto close_out;
 	}
 	if (!extent_buffer_uptodate(info->csum_root->node)) {
 		fprintf(stderr, "Checksum root corrupted, rerun with --init-csum-tree option\n");
 		ret = -EIO;
+		err |= !!ret;
 		goto close_out;
 	}
 
@@ -12478,15 +12493,18 @@ int cmd_check(int argc, char **argv)
 		ret = check_chunks_and_extents_v2(root);
 	else
 		ret = check_chunks_and_extents(root);
+	err |= !!ret;
 	if (ret)
 		fprintf(stderr, "Errors found in extent allocation tree or chunk allocation\n");
 
 	ret = repair_root_items(info);
+	err |= !!ret;
 	if (ret < 0)
 		goto close_out;
 	if (repair) {
 		fprintf(stderr, "Fixed %d roots.\n", ret);
 		ret = 0;
+		err |= !!ret;
 	} else if (ret > 0) {
 		fprintf(stderr,
 		       "Found %d roots with an outdated root item.\n",
@@ -12494,6 +12512,7 @@ int cmd_check(int argc, char **argv)
 		fprintf(stderr,
 			"Please run a filesystem check with the option --repair to fix them.\n");
 		ret = 1;
+		err |= !!ret;
 		goto close_out;
 	}
 
@@ -12504,6 +12523,7 @@ int cmd_check(int argc, char **argv)
 			fprintf(stderr, "checking free space cache\n");
 	}
 	ret = check_space_cache(root);
+	err |= !!ret;
 	if (ret)
 		goto out;
 
@@ -12521,17 +12541,20 @@ int cmd_check(int argc, char **argv)
 		ret = check_fs_roots_v2(root->fs_info);
 	else
 		ret = check_fs_roots(root, &root_cache);
+	err |= !!ret;
 	if (ret)
 		goto out;
 
 	fprintf(stderr, "checking csums\n");
 	ret = check_csums(root);
+	err |= !!ret;
 	if (ret)
 		goto out;
 
 	fprintf(stderr, "checking root refs\n");
 	if (!low_memory) {
 		ret = check_root_refs(root, &root_cache);
+		err |= !!ret;
 		if (ret)
 			goto out;
 	}
@@ -12543,6 +12566,7 @@ int cmd_check(int argc, char **argv)
 				      struct extent_buffer, recow);
 		list_del_init(&eb->recow);
 		ret = recow_extent_buffer(root, eb);
+		err |= !!ret;
 		if (ret)
 			break;
 	}
@@ -12552,26 +12576,29 @@ int cmd_check(int argc, char **argv)
 
 		bad = list_first_entry(&delete_items, struct bad_item, list);
 		list_del_init(&bad->list);
-		if (repair)
+		if (repair) {
 			ret = delete_bad_item(root, bad);
+			err |= !!ret;
+		}
 		free(bad);
 	}
 
 	if (info->quota_enabled) {
-		int err;
+		int error;
 		fprintf(stderr, "checking quota groups\n");
-		err = qgroup_verify_all(info);
-		if (err)
+		error = qgroup_verify_all(info);
+		if (error)
 			goto out;
 		report_qgroups(0);
-		err = repair_qgroups(info, &qgroups_repaired);
-		if (err)
+		error = repair_qgroups(info, &qgroups_repaired);
+		if (error)
 			goto out;
 	}
 
 	if (!list_empty(&root->fs_info->recow_ebs)) {
 		fprintf(stderr, "Transid errors in file system\n");
 		ret = 1;
+		err |= !!ret;
 	}
 out:
 	/* Don't override original ret */
@@ -12588,6 +12615,7 @@ out:
 		       "\n * Please mount the FS in readonly mode, "
 		       "backup data and re-format the FS. *\n\n");
 		ret = 1;
+		err |= !!ret;
 	}
 	printf("found %llu bytes used err is %d\n",
 	       (unsigned long long)bytes_used, ret);
@@ -12612,5 +12640,5 @@ err_out:
 	if (ctx.progress_enabled)
 		task_deinit(ctx.info);
 
-	return ret;
+	return err;
 }
-- 
2.7.4

[PATCH 13/13] btrfs-progs: check: fix false warning for check_extent_item()

[Lu Fengqi]

In the case that a extent doesn't have inline ref, this function
shouldn't report ITEM_SIZE_MISMATCH.

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

diff --git a/cmds-check.c b/cmds-check.c
index c52eebc..9fe3643 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -10373,7 +10373,11 @@ static int check_extent_item(struct btrfs_fs_info *fs_info,
 	}
 	end = (unsigned long)ei + item_size;
 
-	if (ptr >= end) {
+	if (ptr == end) {
+		goto out;
+	} else if (ptr > end) {
+		error("bad extent item [%llu %u %llu] size wrong",
+		      key.objectid, key.type, key.offset);
 		err |= ITEM_SIZE_MISMATCH;
 		goto out;
 	}
-- 
2.7.4

Re: [PATCH 00/13] btrfs-progs: check: check fs roots in low_memory mode

[David Sterba]

On Thu, Jul 28, 2016 at 03:08:12PM +0800, Lu Fengqi wrote:
> This patchset implements check fs trees in low memory mode, and fix the
> return value bug of the function cmd_check().
> 
> Lu Fengqi (13):
>   btrfs-progs: move btrfs_extref_hash() to hash.h
>   btrfs-progs: check: introduce function to find dir_item
>   btrfs-progs: check: introduce function to check inode_ref
>   btrfs-progs: check: introduce function to check inode_extref
>   btrfs-progs: check: introduce function to find inode_ref
>   btrfs-progs: check: introduce a function to check dir_item
>   btrfs-progs: check: introduce function to check file extent
>   btrfs-progs: check: introduce function to check inode item
>   btrfs-progs: check: introduce function to check fs root
>   btrfs-progs: check: introduce function to check root ref
>   btrfs-progs: check: introduce low_memory mode fs_tree check
>   btrfs-progs: check: fix the return value bug of cmd_check()
>   btrfs-progs: check: fix false warning for check_extent_item()

FYI, I'm going to promote this series within devel and schedule it for
the next release. The preparatory subset will be merged, but I might do
some modificaions to the command line interface.

Re: [PATCH 00/13] btrfs-progs: check: check fs roots in low_memory mode

[Wang Xiaoguang]

Hi

On 08/18/2016 01:00 AM, David Sterba wrote:
> On Thu, Jul 28, 2016 at 03:08:12PM +0800, Lu Fengqi wrote:
>> This patchset implements check fs trees in low memory mode, and fix the
>> return value bug of the function cmd_check().
>>
>> Lu Fengqi (13):
>>    btrfs-progs: move btrfs_extref_hash() to hash.h
>>    btrfs-progs: check: introduce function to find dir_item
>>    btrfs-progs: check: introduce function to check inode_ref
>>    btrfs-progs: check: introduce function to check inode_extref
>>    btrfs-progs: check: introduce function to find inode_ref
>>    btrfs-progs: check: introduce a function to check dir_item
>>    btrfs-progs: check: introduce function to check file extent
>>    btrfs-progs: check: introduce function to check inode item
>>    btrfs-progs: check: introduce function to check fs root
>>    btrfs-progs: check: introduce function to check root ref
>>    btrfs-progs: check: introduce low_memory mode fs_tree check
>>    btrfs-progs: check: fix the return value bug of cmd_check()
>>    btrfs-progs: check: fix false warning for check_extent_item()
> FYI, I'm going to promote this series within devel and schedule it for
> the next release. The preparatory subset will be merged, but I might do
> some modificaions to the command line interface.
In current low memory fs trees check, it dose not check whether
node or leaf is shared, which will casue btrfsck much slower when
fs has one or more snapshots. I have prepared a patch to improve
this issue, if you have some free time, please check it, thanks.

And this patch is based on my previous patch "btrfs-progs: eliminate 
some unnecessary
btrfs_lookup_extent_info() calls in walk_down_tree()".


Regards,
Xiaoguang Wang

> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>
>

Re: [PATCH 00/13] btrfs-progs: check: check fs roots in low_memory mode

[David Sterba]

On Fri, Aug 19, 2016 at 05:57:44PM +0800, Wang Xiaoguang wrote:
> Hi
> 
> On 08/18/2016 01:00 AM, David Sterba wrote:
> > On Thu, Jul 28, 2016 at 03:08:12PM +0800, Lu Fengqi wrote:
> >> This patchset implements check fs trees in low memory mode, and fix the
> >> return value bug of the function cmd_check().
> >>
> >> Lu Fengqi (13):
> >>    btrfs-progs: move btrfs_extref_hash() to hash.h
> >>    btrfs-progs: check: introduce function to find dir_item
> >>    btrfs-progs: check: introduce function to check inode_ref
> >>    btrfs-progs: check: introduce function to check inode_extref
> >>    btrfs-progs: check: introduce function to find inode_ref
> >>    btrfs-progs: check: introduce a function to check dir_item
> >>    btrfs-progs: check: introduce function to check file extent
> >>    btrfs-progs: check: introduce function to check inode item
> >>    btrfs-progs: check: introduce function to check fs root
> >>    btrfs-progs: check: introduce function to check root ref
> >>    btrfs-progs: check: introduce low_memory mode fs_tree check
> >>    btrfs-progs: check: fix the return value bug of cmd_check()
> >>    btrfs-progs: check: fix false warning for check_extent_item()
> > FYI, I'm going to promote this series within devel and schedule it for
> > the next release. The preparatory subset will be merged, but I might do
> > some modificaions to the command line interface.
> In current low memory fs trees check, it dose not check whether
> node or leaf is shared, which will casue btrfsck much slower when
> fs has one or more snapshots. I have prepared a patch to improve
> this issue, if you have some free time, please check it, thanks.

The low-memory mode has an experimental status (and thus is not on by
default) so the improvements are welcome of course.