[PATCH v2 00/14] Btrfsck low memory mode with fs/subvol tree check

[PATCH v2 00/14] Btrfsck low memory mode with fs/subvol tree check

[Qu Wenruo]

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

Already merged lowmem mode fsck only works for extent/chunk tree check.
And for fs tree, it's still using original mode codes.

This makes btrfs check still eat tons of memory for large fs.

Now the new lowmem mode code will also cover fs tree now, to make
lowmem mode be really low-memory usage mode.

And the whole patchset goes through the whole fsck test cases, except
the following case:

006: There is a bug in root item repair code, causing backref error.
     However old fsck has another bug to overwrite extent tree error,
     so old fsck will only report error but still return 0.

     That's an unrelated btrfsck repair bug, which I'll address it later.

015: Just wrong test cases. It's not a normal check-repair-check one.
     So the check after repair will still report error.
     Better to put it to fuzz test cases.

Further plan for lowmem mode is:
1) Add support for --repair
   A lot of work again.

2) Separate original and lowmem mode codes into different files
   300+K single source is really too large.
   Better separate them into a dir and multiple files

3) Avoid using find_all_parents() in traversal function
   In lowmmem mode, we are using find_all_parents() function to ensure
   only the root with smallest objectid to check the leaf, so we can
   save some IO.

   However find_all_parents() is still a quite time consuming function, so
   we'd better avoid calling that function.

Lu Fengqi (12):
  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()

Qu Wenruo (1):
  btrfs-progs: check: Enhance leaf traversal function to handle missing
    inode item

Wang Xiaoguang (1):
  btrfs-progs: check: skip shared node or leaf check for low_memory mode

 cmds-check.c | 1763 ++++++++++++++++++++++++++++++++++++++++++++++++++++------
 hash.h       |   10 +
 inode-item.c |    8 +-
 3 files changed, 1600 insertions(+), 181 deletions(-)

-- 
2.10.0

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

[Qu Wenruo]

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

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 913b81a..f7b6ead 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.10.0

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

[Qu Wenruo]

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

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 | 140 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 140 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 998ba63..4e25804 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -3848,6 +3848,146 @@ 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;
+
+	btrfs_init_path(&path);
+	ret = btrfs_search_slot(NULL, root, key, &path, 0, 0);
+	if (ret < 0) {
+		ret = DIR_ITEM_MISSING;
+		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_release_path(&path);
+	return ret;
+}
+
 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 {
 	struct list_head *cur = rec->backrefs.next;
-- 
2.10.0

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

[Qu Wenruo]

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

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 | 76 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 76 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 4e25804..90d5fbc 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,
@@ -3988,6 +3989,81 @@ 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;
+		warning("root %llu INODE_REF[%llu %llu] name too long",
+			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 list_head *cur = rec->backrefs.next;
-- 
2.10.0

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

[Qu Wenruo]

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

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 | 78 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 78 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 90d5fbc..fec8b6e 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -4064,6 +4064,84 @@ 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;
+		warning("root %llu INODE_EXTREF[%llu %llu] name too long",
+			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 list_head *cur = rec->backrefs.next;
-- 
2.10.0

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

[Qu Wenruo]

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

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 | 149 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 149 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index fec8b6e..a261821 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -3852,6 +3852,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
@@ -4142,6 +4143,154 @@ 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 >0 for error bitmap
+ */
+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;
+			warning("root %llu INODE %s[%llu %llu] name too long",
+				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;
+			warning("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 list_head *cur = rec->backrefs.next;
-- 
2.10.0

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

[Qu Wenruo]

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

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 | 125 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 125 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index a261821..d39a81c 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -3853,6 +3853,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
@@ -4291,6 +4293,129 @@ 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;
+			warning("root %llu %s[%llu %llu] name too long",
+				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 list_head *cur = rec->backrefs.next;
-- 
2.10.0

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

[Qu Wenruo]

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

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 | 97 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 97 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index d39a81c..0afbf96 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -3855,6 +3855,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
@@ -4416,6 +4419,100 @@ 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) {
+		struct btrfs_item *e = btrfs_item_nr(slot);
+		u32 item_inline_len;
+
+		item_inline_len = btrfs_file_extent_inline_item_len(node, e);
+		extent_num_bytes = btrfs_file_extent_inline_len(node, slot, fi);
+		if (extent_num_bytes == 0 ||
+		    extent_num_bytes != item_inline_len)
+			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 list_head *cur = rec->backrefs.next;
-- 
2.10.0

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

[Qu Wenruo]

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

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 | 168 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 168 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 0afbf96..5e3ecac 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -3858,6 +3858,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
@@ -4513,6 +4518,169 @@ 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 >0 for error or hit the traversal is done(by error bitmap)
+ */
+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;
+
+	if (inode_id == BTRFS_ORPHAN_OBJECTID) {
+		ret = btrfs_next_item(root, path);
+		if (ret > 0)
+			err |= LAST_ITEM;
+		return err;
+	}
+
+	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) {
+			/* out will fill 'err' rusing current statistics */
+			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)
+				warning("root %llu EXTREF[%llu %llu] isn't supported",
+					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) {
+				warning("root %llu INODE[%llu] mode %u shouldn't have DIR_INDEX[%llu %llu]",
+					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) {
+				warning("root %llu DIR INODE[%llu] shouldn't EXTENT_DATA[%llu %llu]",
+					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);
+		}
+
+		/*
+		 * Just a warning, as dir inode nbytes is just an
+		 * instructive value.
+		 */
+		if (!IS_ALIGNED(nbytes, root->nodesize)) {
+			warning("root %llu DIR INODE[%llu] nbytes should be aligned to %u",
+				root->objectid, inode_id, root->nodesize);
+		}
+
+		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 list_head *cur = rec->backrefs.next;
-- 
2.10.0

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

[Qu Wenruo]

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

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 5e3ecac..6d3c6a8 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -3862,6 +3862,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 */
 
 /*
@@ -4681,6 +4682,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.
+ * Return <0 for error.
+ * All internal error bitmap will be converted to -EIO, to avoid
+ * mixing negative and postive return value.
+ */
+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)
+		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 (key.type == BTRFS_INODE_ITEM_KEY) {
+			ret = check_inode_item(root, path, ext_ref);
+			err |= ret;
+			if (err & LAST_ITEM)
+				goto out;
+			continue;
+		}
+		error("root %llu ITEM[%llu %u %llu] isn't INODE_ITEM, skip to next inode",
+		      root->objectid, key.objectid, key.type,
+		      key.offset);
+
+		err |= NO_INODE_ITEM;
+		inode_id = key.objectid;
+
+		/*
+		 * skip to next inode
+		 * TODO: Maybe search_slot() will be faster?
+		 */
+		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;
+	if (err && !ret)
+		ret = -EIO;
+	btrfs_free_path(path);
+	return ret;
+}
+
 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 {
 	struct list_head *cur = rec->backrefs.next;
-- 
2.10.0

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

[Qu Wenruo]

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

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 6d3c6a8..7593013 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -3864,6 +3864,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
@@ -4757,6 +4759,97 @@ out:
 	return ret;
 }
 
+/*
+ * 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;
+		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;
+		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 list_head *cur = rec->backrefs.next;
-- 
2.10.0

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

[Qu Wenruo]

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

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 | 106 +++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 100 insertions(+), 6 deletions(-)

diff --git a/cmds-check.c b/cmds-check.c
index 7593013..934a3dd 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -4774,8 +4774,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;
@@ -4850,6 +4850,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 list_head *cur = rec->backrefs.next;
@@ -12544,7 +12632,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 (check_mode == CHECK_MODE_LOWMEM)
+		ret = check_fs_roots_v2(root->fs_info);
+	else
+		ret = check_fs_roots(root, &root_cache);
 	if (ret)
 		goto out;
 
@@ -12554,9 +12645,12 @@ 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;
+	/* For low memory mode, check_fs_roots_v2 handles root refs */
+	if (check_mode != CHECK_MODE_LOWMEM) {
+		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.10.0

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

[Qu Wenruo]

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

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 | 47 ++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 36 insertions(+), 11 deletions(-)

diff --git a/cmds-check.c b/cmds-check.c
index 934a3dd..701fff5 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -12337,6 +12337,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;
@@ -12470,10 +12471,12 @@ int cmd_check(int argc, char **argv)
 
 	if((ret = check_mounted(argv[optind])) < 0) {
 		error("could not check mount status: %s", strerror(-ret));
+		err |= !!ret;
 		goto err_out;
 	} else if(ret) {
 		error("%s is currently mounted, aborting", argv[optind]);
 		ret = -EBUSY;
+		err |= !!ret;
 		goto err_out;
 	}
 
@@ -12486,6 +12489,7 @@ int cmd_check(int argc, char **argv)
 	if (!info) {
 		error("cannot open file system");
 		ret = -EIO;
+		err |= !!ret;
 		goto err_out;
 	}
 
@@ -12500,9 +12504,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) {
 			error("failed to zero log tree: %d", ret);
 			goto close_out;
@@ -12514,6 +12520,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;
@@ -12522,6 +12529,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);
@@ -12530,6 +12538,7 @@ int cmd_check(int argc, char **argv)
 	    !extent_buffer_uptodate(info->dev_root->node) ||
 	    !extent_buffer_uptodate(info->chunk_root->node)) {
 		error("critical roots corrupted, unable to check the filesystem");
+		err |= !!ret;
 		ret = -EIO;
 		goto close_out;
 	}
@@ -12541,12 +12550,14 @@ int cmd_check(int argc, char **argv)
 		if (IS_ERR(trans)) {
 			error("error starting transaction");
 			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;
 		}
@@ -12558,11 +12569,13 @@ int cmd_check(int argc, char **argv)
 				error("checksum tree initialization failed: %d",
 						ret);
 				ret = -EIO;
+				err |= !!ret;
 				goto close_out;
 			}
 
 			ret = fill_csum_tree(trans, info->csum_root,
 					     init_extent_tree);
+			err |= !!ret;
 			if (ret) {
 				error("checksum tree refilling failed: %d", ret);
 				return -EIO;
@@ -12573,17 +12586,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)) {
 		error("critical: extent_root, unable to check the filesystem");
 		ret = -EIO;
+		err |= !!ret;
 		goto close_out;
 	}
 	if (!extent_buffer_uptodate(info->csum_root->node)) {
 		error("critical: csum_root, unable to check the filesystem");
 		ret = -EIO;
+		err |= !!ret;
 		goto close_out;
 	}
 
@@ -12593,10 +12609,12 @@ 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)
 		printf("Errors found in extent allocation tree or chunk allocation");
 
 	ret = repair_root_items(info);
+	err |= !!ret;
 	if (ret < 0)
 		goto close_out;
 	if (repair) {
@@ -12609,6 +12627,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;
 	}
 
@@ -12619,6 +12638,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;
 
@@ -12636,11 +12656,13 @@ 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;
 
@@ -12648,6 +12670,7 @@ int cmd_check(int argc, char **argv)
 	/* For low memory mode, check_fs_roots_v2 handles root refs */
 	if (check_mode != CHECK_MODE_LOWMEM) {
 		ret = check_root_refs(root, &root_cache);
+		err |= !!ret;
 		if (ret)
 			goto out;
 	}
@@ -12659,6 +12682,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;
 	}
@@ -12668,32 +12692,33 @@ 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;
 		fprintf(stderr, "checking quota groups\n");
-		err = qgroup_verify_all(info);
-		if (err)
+		ret = qgroup_verify_all(info);
+		err |= !!ret;
+		if (ret)
 			goto out;
 		report_qgroups(0);
-		err = repair_qgroups(info, &qgroups_repaired);
+		ret = repair_qgroups(info, &qgroups_repaired);
+		err |= !!ret;
 		if (err)
 			goto out;
+		ret = 0;
 	}
 
 	if (!list_empty(&root->fs_info->recow_ebs)) {
 		error("transid errors in file system");
 		ret = 1;
+		err |= !!ret;
 	}
 out:
-	/* Don't override original ret */
-	if (!ret && qgroups_repaired)
-		ret = qgroups_repaired;
-
 	if (found_old_backref) { /*
 		 * there was a disk format change when mixed
 		 * backref was in testing tree. The old format
@@ -12703,7 +12728,7 @@ out:
 		       "The old format is not supported! *"
 		       "\n * Please mount the FS in readonly mode, "
 		       "backup data and re-format the FS. *\n\n");
-		ret = 1;
+		err |= 1;
 	}
 	printf("found %llu bytes used err is %d\n",
 	       (unsigned long long)bytes_used, ret);
@@ -12728,5 +12753,5 @@ err_out:
 	if (ctx.progress_enabled)
 		task_deinit(ctx.info);
 
-	return ret;
+	return err;
 }
-- 
2.10.0

[PATCH v2 13/14] btrfs-progs: check: skip shared node or leaf check for low_memory mode

[Qu Wenruo]

From: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>

The basic idea is simple. Assume a middle tree node A is shared and
its referenceing fs/file tree root ids are 5, 258 and 260, then we
only check node A in the tree who has the smallest root id. That means
in this case, when checking root tree(5), we check inode A, for root
tree 258 and 260, we can just skip it.

Notice even with this patch, we still may visit a shared node or leaf
multiple times. This happens when a inode metadata occupies multiple
leaves.

                 leaf_A     leaf_B
When checking inode item in leaf_A, assume inode[512] have file extents
in leaf_B, and leaf_B is shared. In the case, for inode[512], we must
visit leaf_B to have inode item check. After finishing inode[512] check,
here we walk down tree root to leaf_B to check whether node or leaf
is shared, if some node or leaf is shared, we can just skip it and below
nodes or leaf's check.

I also fill a disk partition with linux source codes and create 3
snapshots
in it. Before this patch, it averagely took 46s to finish one btrfsck
execution, with this patch, it averagely took 15s.

Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 390 ++++++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 321 insertions(+), 69 deletions(-)

diff --git a/cmds-check.c b/cmds-check.c
index 701fff5..d290a66 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -113,6 +113,24 @@ struct data_backref {
 	u32 found_ref;
 };
 
+#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 */
+#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 */
+#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 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 */
+
 static inline struct data_backref* to_data_backref(struct extent_backref *back)
 {
 	return container_of(back, struct data_backref, node);
@@ -1839,6 +1857,92 @@ static int process_one_leaf(struct btrfs_root *root, struct extent_buffer *eb,
 	return ret;
 }
 
+struct node_refs {
+	u64 bytenr[BTRFS_MAX_LEVEL];
+	u64 refs[BTRFS_MAX_LEVEL];
+	int need_check[BTRFS_MAX_LEVEL];
+};
+
+static int update_nodes_refs(struct btrfs_root *root, u64 bytenr,
+			     struct node_refs *nrefs, u64 level);
+static int check_inode_item(struct btrfs_root *root, struct btrfs_path *path,
+			    unsigned int ext_ref);
+
+static int process_one_leaf_v2(struct btrfs_root *root, struct btrfs_path *path,
+			       struct node_refs *nrefs, int *level, int ext_ref)
+{
+	struct extent_buffer *cur = path->nodes[0];
+	struct btrfs_key key;
+	u64 cur_bytenr;
+	u32 nritems;
+	int root_level = btrfs_header_level(root->node);
+	int i;
+	int ret = 0; /* Final return value */
+	int err = 0; /* Positive error bitmap */
+
+	cur_bytenr = cur->start;
+
+	/* skip to first inode item in this leaf */
+	nritems = btrfs_header_nritems(cur);
+	for (i = 0; i < nritems; i++) {
+		btrfs_item_key_to_cpu(cur, &key, i);
+		if (key.type == BTRFS_INODE_ITEM_KEY)
+			break;
+	}
+	if (i == nritems) {
+		path->slots[0] = nritems;
+		return 0;
+	}
+	path->slots[0] = i;
+
+again:
+	err |= check_inode_item(root, path, ext_ref);
+
+	if (err & LAST_ITEM)
+		goto out;
+
+	/* still have inode items in thie leaf */
+	if (cur->start == cur_bytenr)
+		goto again;
+
+	/*
+	 * we have switched to another leaf, above nodes may
+	 * have changed, here walk down the path, if a node
+	 * or leaf is shared, check whether we can skip this
+	 * node or leaf.
+	 */
+	for (i = root_level; i >= 0; i--) {
+		if (path->nodes[i]->start == nrefs->bytenr[i])
+			continue;
+
+		ret = update_nodes_refs(root,
+				path->nodes[i]->start,
+				nrefs, i);
+		if (ret)
+			goto out;
+
+		if (!nrefs->need_check[i]) {
+			*level += 1;
+			break;
+		}
+	}
+
+	for (i = 0; i < *level; i++) {
+		free_extent_buffer(path->nodes[i]);
+		path->nodes[i] = NULL;
+	}
+out:
+	err &= ~LAST_ITEM;
+	/*
+	 * Convert any error bitmap to -EIO, as we should avoid
+	 * mixing positive and negative return value to represent
+	 * error
+	 */
+	if (err && !ret)
+		ret = -EIO;
+	return ret;
+}
+
 static void reada_walk_down(struct btrfs_root *root,
 			    struct extent_buffer *node, int slot)
 {
@@ -1912,10 +2016,66 @@ static int check_child_node(struct btrfs_root *root,
 	return ret;
 }
 
-struct node_refs {
-	u64 bytenr[BTRFS_MAX_LEVEL];
-	u64 refs[BTRFS_MAX_LEVEL];
-};
+/*
+ * for a tree node or leaf, if it's shared, indeed we don't need to iterate it
+ * in every fs or file tree check. Here we find its all root ids, and only check
+ * it in the fs or file tree which has the smallest root id.
+ */
+static int need_check(struct btrfs_root *root, struct ulist *roots)
+{
+	struct rb_node *node;
+	struct ulist_node *u;
+
+	if (roots->nnodes == 1)
+		return 1;
+
+	node = rb_first(&roots->root);
+	u = rb_entry(node, struct ulist_node, rb_node);
+	/*
+	 * current root id is not smallest, we skip it and let it be checked
+	 * in the fs or file tree who hash the smallest root id.
+	 */
+	if (root->objectid != u->val)
+		return 0;
+
+	return 1;
+}
+
+/*
+ * for a tree node or leaf, we record its reference count, so later if we still
+ * process this node or leaf, don't need to compute its reference count again.
+ */
+static int update_nodes_refs(struct btrfs_root *root, u64 bytenr,
+			     struct node_refs *nrefs, u64 level)
+{
+	int check, ret;
+	u64 refs;
+	struct ulist *roots;
+
+	if (nrefs->bytenr[level] != bytenr) {
+		ret = btrfs_lookup_extent_info(NULL, root, bytenr,
+				       level, 1, &refs, NULL);
+		if (ret < 0)
+			return ret;
+
+		nrefs->bytenr[level] = bytenr;
+		nrefs->refs[level] = refs;
+		if (refs > 1) {
+			ret = btrfs_find_all_roots(NULL, root->fs_info, bytenr,
+						   0, &roots);
+			if (ret)
+				return -EIO;
+
+			check = need_check(root, roots);
+			ulist_free(roots);
+			nrefs->need_check[level] = check;
+		} else {
+			nrefs->need_check[level] = 1;
+		}
+	}
+
+	return 0;
+}
 
 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
 			  struct walk_control *wc, int *level,
@@ -2046,6 +2206,110 @@ out:
 	return err;
 }
 
+static int check_inode_item(struct btrfs_root *root, struct btrfs_path *path,
+			    unsigned int ext_ref);
+
+static int walk_down_tree_v2(struct btrfs_root *root, struct btrfs_path *path,
+			     int *level, struct node_refs *nrefs, int ext_ref)
+{
+	enum btrfs_tree_block_status status;
+	u64 bytenr;
+	u64 ptr_gen;
+	struct extent_buffer *next;
+	struct extent_buffer *cur;
+	u32 blocksize;
+	int ret;
+
+	WARN_ON(*level < 0);
+	WARN_ON(*level >= BTRFS_MAX_LEVEL);
+
+	ret = update_nodes_refs(root, path->nodes[*level]->start,
+				nrefs, *level);
+	if (ret < 0)
+		return ret;
+
+	while (*level >= 0) {
+		WARN_ON(*level < 0);
+		WARN_ON(*level >= BTRFS_MAX_LEVEL);
+		cur = path->nodes[*level];
+
+		if (btrfs_header_level(cur) != *level)
+			WARN_ON(1);
+
+		if (path->slots[*level] >= btrfs_header_nritems(cur))
+			break;
+		/* Don't forgot to check leaf/node validation */
+		if (*level == 0) {
+			ret = btrfs_check_leaf(root, NULL, cur);
+			if (ret != BTRFS_TREE_BLOCK_CLEAN) {
+				ret = -EIO;
+				break;
+			}
+			ret = process_one_leaf_v2(root, path, nrefs,
+						  level, ext_ref);
+			break;
+		} else {
+			ret = btrfs_check_node(root, NULL, cur);
+			if (ret != BTRFS_TREE_BLOCK_CLEAN) {
+				ret = -EIO;
+				break;
+			}
+		}
+		bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
+		ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
+		blocksize = root->nodesize;
+
+		ret = update_nodes_refs(root, bytenr, nrefs, *level - 1);
+		if (ret)
+			break;
+		if (!nrefs->need_check[*level - 1]) {
+			path->slots[*level]++;
+			continue;
+		}
+
+		next = btrfs_find_tree_block(root, bytenr, blocksize);
+		if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
+			free_extent_buffer(next);
+			reada_walk_down(root, cur, path->slots[*level]);
+			next = read_tree_block(root, bytenr, blocksize,
+					       ptr_gen);
+			if (!extent_buffer_uptodate(next)) {
+				struct btrfs_key node_key;
+
+				btrfs_node_key_to_cpu(path->nodes[*level],
+						      &node_key,
+						      path->slots[*level]);
+				btrfs_add_corrupt_extent_record(root->fs_info,
+						&node_key,
+						path->nodes[*level]->start,
+						root->nodesize, *level);
+				ret = -EIO;
+				break;
+			}
+		}
+
+		ret = check_child_node(root, cur, path->slots[*level], next);
+		if (ret < 0) 
+			break;
+
+		if (btrfs_is_leaf(next))
+			status = btrfs_check_leaf(root, NULL, next);
+		else
+			status = btrfs_check_node(root, NULL, next);
+		if (status != BTRFS_TREE_BLOCK_CLEAN) {
+			free_extent_buffer(next);
+			ret = -EIO;
+			break;
+		}
+
+		*level = *level - 1;
+		free_extent_buffer(path->nodes[*level]);
+		path->nodes[*level] = next;
+		path->slots[*level] = 0;
+	}
+	return ret;
+}
+
 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
 			struct walk_control *wc, int *level)
 {
@@ -2070,6 +2334,27 @@ static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
 	return 1;
 }
 
+static int walk_up_tree_v2(struct btrfs_root *root, struct btrfs_path *path,
+			   int *level)
+{
+	int i;
+	struct extent_buffer *leaf;
+
+	for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
+		leaf = path->nodes[i];
+		if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
+			path->slots[i]++;
+			*level = i;
+			return 0;
+		} else {
+			free_extent_buffer(path->nodes[*level]);
+			path->nodes[*level] = NULL;
+			*level = i + 1;
+		}
+	}
+	return 1;
+}
+
 static int check_root_dir(struct inode_record *rec)
 {
 	struct inode_backref *backref;
@@ -3849,24 +4134,6 @@ 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 */
-#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 */
-#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 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
  * INODE_REF/INODE_EXTREF match.
@@ -4692,69 +4959,54 @@ out:
  *
  * Return 0 if no error found.
  * Return <0 for error.
- * All internal error bitmap will be converted to -EIO, to avoid
- * mixing negative and postive return value.
  */
 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;
+	struct node_refs nrefs;
+	struct btrfs_root_item *root_item = &root->root_item;
+	int ret, wret;
+	int level;
 
 	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)
-		goto out;
+	memset(&nrefs, 0, sizeof(nrefs));
+	level = btrfs_header_level(root->node);
 
-	while (1) {
-		btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+	if (btrfs_root_refs(root_item) > 0 ||
+	    btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
+		path->nodes[level] = root->node;
+		path->slots[level] = 0;
+		extent_buffer_get(root->node);
+	} else {
+		struct btrfs_key key;
 
-		/*
-		 * All check must start with inode item, skip if not
-		 */
-		if (key.type == BTRFS_INODE_ITEM_KEY) {
-			ret = check_inode_item(root, path, ext_ref);
-			err |= ret;
-			if (err & LAST_ITEM)
-				goto out;
-			continue;
-		}
-		error("root %llu ITEM[%llu %u %llu] isn't INODE_ITEM, skip to next inode",
-		      root->objectid, key.objectid, key.type,
-		      key.offset);
+		btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
+		level = root_item->drop_level;
+		path->lowest_level = level;
+		ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
+		if (ret < 0)
+			goto out;
+		ret = 0;
+	}
 
-		err |= NO_INODE_ITEM;
-		inode_id = key.objectid;
+	while (1) {
+		wret = walk_down_tree_v2(root, path, &level, &nrefs, ext_ref);
+		if (wret < 0)
+			ret = wret;
+		if (wret != 0)
+			break;
 
-		/*
-		 * skip to next inode
-		 * TODO: Maybe search_slot() will be faster?
-		 */
-		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);
+		wret = walk_up_tree_v2(root, path, &level);
+		if (wret < 0)
+			ret = wret;
+		if (wret != 0)
+			break;
 	}
 
 out:
-	err &= ~LAST_ITEM;
-	if (err && !ret)
-		ret = -EIO;
 	btrfs_free_path(path);
 	return ret;
 }
-- 
2.10.0

[PATCH v2 14/14] btrfs-progs: check: Enhance leaf traversal function to handle missing inode item

[Qu Wenruo]

The leaf traversal function in lowmem mode will skip to the first inode
item of leaf and begin to check the inode.

That's designed to avoid checking overlapping part of a leaf.

But that will cause problem in fsck/010 test case, as in that case inode
item of the first inode(256) is missing.
So above traversal will check from inode 257 and found nothing wrong.

The fix is done in 2 part:
1) Manually check the first inode
   To avoid case like fsck/010

2) Check inode if ino changes from the first ino of a leaf
   To avoid missing inode_item problem.

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

diff --git a/cmds-check.c b/cmds-check.c
index d290a66..f5be153 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -1875,6 +1875,7 @@ static int process_one_leaf_v2(struct btrfs_root *root, struct btrfs_path *path,
 	struct btrfs_key key;
 	u64 cur_bytenr;
 	u32 nritems;
+	u64 first_ino = 0;
 	int root_level = btrfs_header_level(root->node);
 	int i;
 	int ret = 0; /* Final return value */
@@ -1882,11 +1883,14 @@ static int process_one_leaf_v2(struct btrfs_root *root, struct btrfs_path *path,
 
 	cur_bytenr = cur->start;
 
-	/* skip to first inode item in this leaf */
+	/* skip to first inode item or the first inode number change */
 	nritems = btrfs_header_nritems(cur);
 	for (i = 0; i < nritems; i++) {
 		btrfs_item_key_to_cpu(cur, &key, i);
-		if (key.type == BTRFS_INODE_ITEM_KEY)
+		if (i == 0)
+			first_ino = key.objectid;
+		if (key.type == BTRFS_INODE_ITEM_KEY ||
+		    (first_ino && first_ino != key.objectid))
 			break;
 	}
 	if (i == nritems) {
@@ -4951,6 +4955,34 @@ out:
 	return err;
 }
 
+static int check_fs_first_inode(struct btrfs_root *root, unsigned int ext_ref)
+{
+	struct btrfs_path *path;
+	struct btrfs_key key;
+	int err = 0;
+	int ret;
+
+	path = btrfs_alloc_path();
+	key.objectid = 256;
+	key.type = BTRFS_INODE_ITEM_KEY;
+	key.offset = 0;
+
+	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
+	if (ret < 0)
+		return ret;
+	if (ret > 0) {
+		ret = 0;
+		err |= INODE_ITEM_MISSING;
+	}
+
+	err |= check_inode_item(root, path, ext_ref);
+	err &= ~LAST_ITEM;
+	if (err && !ret)
+		ret = -EIO;
+	btrfs_free_path(path);
+	return ret;
+}
+
 /*
  * Iterate all item on the tree and call check_inode_item() to check.
  *
@@ -4968,6 +5000,16 @@ static int check_fs_root_v2(struct btrfs_root *root, unsigned int ext_ref)
 	int ret, wret;
 	int level;
 
+	/*
+	 * We need to manually check the first inode item(256)
+	 * As the following traversal function will only start from
+	 * the first inode item in the leaf, if inode item(256) is missing
+	 * we will just skip it forever.
+	 */
+	ret = check_fs_first_inode(root, ext_ref);
+	if (ret < 0)
+		return ret;
+
 	path = btrfs_alloc_path();
 	if (!path)
 		return -ENOMEM;
-- 
2.10.0

Re: [PATCH v2 00/14] Btrfsck low memory mode with fs/subvol tree check

[David Sterba]

On Wed, Sep 21, 2016 at 11:15:50AM +0800, Qu Wenruo wrote:
> The branch can be fetched from my github:
> https://github.com/adam900710/btrfs-progs/tree/lowmem_fs_tree

I've put it into integration but haven't reviewed nor tested it.

> Already merged lowmem mode fsck only works for extent/chunk tree check.
> And for fs tree, it's still using original mode codes.
> 
> This makes btrfs check still eat tons of memory for large fs.
> 
> Now the new lowmem mode code will also cover fs tree now, to make
> lowmem mode be really low-memory usage mode.
> 
> And the whole patchset goes through the whole fsck test cases, except
> the following case:
> 
> 006: There is a bug in root item repair code, causing backref error.
>      However old fsck has another bug to overwrite extent tree error,
>      so old fsck will only report error but still return 0.
> 
>      That's an unrelated btrfsck repair bug, which I'll address it later.
> 
> 015: Just wrong test cases. It's not a normal check-repair-check one.
>      So the check after repair will still report error.
>      Better to put it to fuzz test cases.
> 
> Further plan for lowmem mode is:
> 1) Add support for --repair
>    A lot of work again.
> 
> 2) Separate original and lowmem mode codes into different files
>    300+K single source is really too large.
>    Better separate them into a dir and multiple files

Makes sense. We're about to split the files by other criteria (kernel,
etc) so this will possible once the details are fleshed out.

Re: [PATCH v2 00/14] Btrfsck low memory mode with fs/subvol tree check

[David Sterba]

On Wed, Sep 21, 2016 at 11:15:50AM +0800, Qu Wenruo wrote:
> Lu Fengqi (12):
>   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()
> 
> Qu Wenruo (1):
>   btrfs-progs: check: Enhance leaf traversal function to handle missing
>     inode item
> 
> Wang Xiaoguang (1):
>   btrfs-progs: check: skip shared node or leaf check for low_memory mode

I've seen minor issues through the patchset, suitable for cleanups, but
the rest looks good enough to be merged. I did a high level review and
could have missed something, so the low-mem mode status remains.

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

[David Sterba]

On Wed, Sep 21, 2016 at 11:15:52AM +0800, Qu Wenruo wrote:
> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
> 
> 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 | 140 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 140 insertions(+)
> 
> diff --git a/cmds-check.c b/cmds-check.c
> index 998ba63..4e25804 100644
> --- a/cmds-check.c
> +++ b/cmds-check.c
> @@ -3848,6 +3848,146 @@ 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 */

What's the reason for another definition of the error codes? They're
mostly copied from te I_ERR_* counterparts. I'd rather have one set of
error codes.

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

[Qu Wenruo]

At 11/02/2016 11:21 PM, David Sterba wrote:
> On Wed, Sep 21, 2016 at 11:15:52AM +0800, Qu Wenruo wrote:
>> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>>
>> 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 | 140 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>>  1 file changed, 140 insertions(+)
>>
>> diff --git a/cmds-check.c b/cmds-check.c
>> index 998ba63..4e25804 100644
>> --- a/cmds-check.c
>> +++ b/cmds-check.c
>> @@ -3848,6 +3848,146 @@ 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 */
>
> What's the reason for another definition of the error codes? They're
> mostly copied from te I_ERR_* counterparts. I'd rather have one set of
> error codes.

The main reason is, in lowmem fsck mode, we are not checking inodes or 
ref/backref in batch.

If using I_ERR and REF_ERR, we can mixing them up as they share the same 
bits.

So we introduced the new error bitmap, to make sure all error bits won't 
cover each other.

It may be better if we rearrange I_ERR/REF_ERR to avoid conflicts.
E.g, let REF_ERR_ starts from lowest bit and let I_ERR_ starts from high 
bits.

Thanks,
Qu

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

[David Sterba]

On Thu, Nov 03, 2016 at 09:58:21AM +0800, Qu Wenruo wrote:
> 
> 
> At 11/02/2016 11:21 PM, David Sterba wrote:
> > On Wed, Sep 21, 2016 at 11:15:52AM +0800, Qu Wenruo wrote:
> >> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
> >>
> >> 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 | 140 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
> >>  1 file changed, 140 insertions(+)
> >>
> >> diff --git a/cmds-check.c b/cmds-check.c
> >> index 998ba63..4e25804 100644
> >> --- a/cmds-check.c
> >> +++ b/cmds-check.c
> >> @@ -3848,6 +3848,146 @@ 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 */
> >
> > What's the reason for another definition of the error codes? They're
> > mostly copied from te I_ERR_* counterparts. I'd rather have one set of
> > error codes.
> 
> The main reason is, in lowmem fsck mode, we are not checking inodes or 
> ref/backref in batch.
> 
> If using I_ERR and REF_ERR, we can mixing them up as they share the same 
> bits.
> 
> So we introduced the new error bitmap, to make sure all error bits won't 
> cover each other.
> 
> It may be better if we rearrange I_ERR/REF_ERR to avoid conflicts.
> E.g, let REF_ERR_ starts from lowest bit and let I_ERR_ starts from high 
> bits.

Yes please. Third namespace for existing error bits is not a good
option. Move the I_ERR bits to start from 32 and use them in the low-mem
code that's been merged to devel.

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

[Qu Wenruo]

At 11/08/2016 01:05 AM, David Sterba wrote:
> On Thu, Nov 03, 2016 at 09:58:21AM +0800, Qu Wenruo wrote:
>>
>>
>> At 11/02/2016 11:21 PM, David Sterba wrote:
>>> On Wed, Sep 21, 2016 at 11:15:52AM +0800, Qu Wenruo wrote:
>>>> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>>>>
>>>> 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 | 140 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>>>>  1 file changed, 140 insertions(+)
>>>>
>>>> diff --git a/cmds-check.c b/cmds-check.c
>>>> index 998ba63..4e25804 100644
>>>> --- a/cmds-check.c
>>>> +++ b/cmds-check.c
>>>> @@ -3848,6 +3848,146 @@ 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 */
>>>
>>> What's the reason for another definition of the error codes? They're
>>> mostly copied from te I_ERR_* counterparts. I'd rather have one set of
>>> error codes.
>>
>> The main reason is, in lowmem fsck mode, we are not checking inodes or
>> ref/backref in batch.
>>
>> If using I_ERR and REF_ERR, we can mixing them up as they share the same
>> bits.
>>
>> So we introduced the new error bitmap, to make sure all error bits won't
>> cover each other.
>>
>> It may be better if we rearrange I_ERR/REF_ERR to avoid conflicts.
>> E.g, let REF_ERR_ starts from lowest bit and let I_ERR_ starts from high
>> bits.
>
> Yes please. Third namespace for existing error bits is not a good
> option. Move the I_ERR bits to start from 32 and use them in the low-mem
> code that's been merged to devel.
>
>
Should I submit a separate fix or replace the patchset?

Thanks,
Qu

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

[Qu Wenruo]

At 11/08/2016 01:05 AM, David Sterba wrote:
> On Thu, Nov 03, 2016 at 09:58:21AM +0800, Qu Wenruo wrote:
>>
>>
>> At 11/02/2016 11:21 PM, David Sterba wrote:
>>> On Wed, Sep 21, 2016 at 11:15:52AM +0800, Qu Wenruo wrote:
>>>> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>>>>
>>>> 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 | 140 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>>>>  1 file changed, 140 insertions(+)
>>>>
>>>> diff --git a/cmds-check.c b/cmds-check.c
>>>> index 998ba63..4e25804 100644
>>>> --- a/cmds-check.c
>>>> +++ b/cmds-check.c
>>>> @@ -3848,6 +3848,146 @@ 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 */
>>>
>>> What's the reason for another definition of the error codes? They're
>>> mostly copied from te I_ERR_* counterparts. I'd rather have one set of
>>> error codes.
>>
>> The main reason is, in lowmem fsck mode, we are not checking inodes or
>> ref/backref in batch.
>>
>> If using I_ERR and REF_ERR, we can mixing them up as they share the same
>> bits.
>>
>> So we introduced the new error bitmap, to make sure all error bits won't
>> cover each other.
>>
>> It may be better if we rearrange I_ERR/REF_ERR to avoid conflicts.
>> E.g, let REF_ERR_ starts from lowest bit and let I_ERR_ starts from high
>> bits.
>
> Yes please. Third namespace for existing error bits is not a good
> option. Move the I_ERR bits to start from 32 and use them in the low-mem
> code that's been merged to devel.

Hi David,

I didn't see such fix in devel branch.
In cmds-check.c, there I_ERR_* and REF_ERR_* are still using the old range.

Is the fix in another branch? Or I missed something again?

Thanks,
Qu

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

[David Sterba]

On Tue, Nov 08, 2016 at 09:45:54AM +0800, Qu Wenruo wrote:
> > Yes please. Third namespace for existing error bits is not a good
> > option. Move the I_ERR bits to start from 32 and use them in the low-mem
> > code that's been merged to devel.
> >
> Should I submit a separate fix or replace the patchset?

Separate patches please. The check patches are at the beginning of
devel and there are several cleanup patches on top of them so that would
probably cause too many merge conflicts.

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

[David Sterba]

On Wed, Nov 16, 2016 at 10:27:59AM +0800, Qu Wenruo wrote:
> > Yes please. Third namespace for existing error bits is not a good
> > option. Move the I_ERR bits to start from 32 and use them in the low-mem
> > code that's been merged to devel.
> 
> I didn't see such fix in devel branch.

Well, that's because nobody implemented it and I was not intending to do
it myself as it's a followup to yor lowmem patchset in devel.

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

[Qu Wenruo]

At 12/01/2016 12:34 AM, David Sterba wrote:
> On Wed, Nov 16, 2016 at 10:27:59AM +0800, Qu Wenruo wrote:
>>> Yes please. Third namespace for existing error bits is not a good
>>> option. Move the I_ERR bits to start from 32 and use them in the low-mem
>>> code that's been merged to devel.
>>
>> I didn't see such fix in devel branch.
>
> Well, that's because nobody implemented it and I was not intending to do
> it myself as it's a followup to yor lowmem patchset in devel.
>
>
OK, I'm going to fix it soon.

Thanks,
Qu

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

[Qu Wenruo]

At 11/02/2016 11:21 PM, David Sterba wrote:
> On Wed, Sep 21, 2016 at 11:15:52AM +0800, Qu Wenruo wrote:
>> From: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
>>
>> 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 | 140 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>>  1 file changed, 140 insertions(+)
>>
>> diff --git a/cmds-check.c b/cmds-check.c
>> index 998ba63..4e25804 100644
>> --- a/cmds-check.c
>> +++ b/cmds-check.c
>> @@ -3848,6 +3848,146 @@ 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 */
>
> What's the reason for another definition of the error codes? They're
> mostly copied from te I_ERR_* counterparts. I'd rather have one set of
> error codes.

I tried to merge them into a 32bit error bits.

But things turns out that, I_ERR and REF_ERR have already taken 28 bits.
For a int type, we only have extra 4bits.

All fs tree level error code are OK to merge.
But extent tree level errors, including extent ref/backref error bits, 
and tree block level errors, like bad key type in current content or bad 
item size, have no corresponding bits.

These bits are already over 4 bits.


Yes, we can expand the error bit to u64, but that will be a huge 
modification for both the original mode and lowmem mode.


What about letting me separate the lowmem code from cmds-check.c into 
check/lowmem.c and using the current error when you're going to create 
check/ directory?

It should be OK to merge all lowmem error bits into one int type, but 
not possible to do it with original mode error bits without expanding 
the int type.
Since we have different error bit standard, this leads to completely 
different usage on these bits.
A lot of lowmem bit won't be used by original mode and vice-verse.

Thanks,
Qu