[PATCH v3 0/7] btrfs-progs: lowmem: bug fixes and inode_extref repair

[PATCH v3 0/7] btrfs-progs: lowmem: bug fixes and inode_extref repair

[Su Yue]

This patchset can be fetched from my github:
https://github.com/Damenly/btrfs-progs/tree/lowmem_extref
based on kdave/devel whose HEAD is:
commit 4f20c27ab33aab3efffe13cdae1b8837c821d0d7 (kdave/devel)
Author: Nikolay Borisov <nborisov@suse.com>
Date:   Fri Jun 15 07:13:50 2018 +0000
btrfs-progs: tests: test for FST corruption detection/repair

The patchset aims to support check and repair errors about
inode_extref in lowmem mode. 
patch[1-2] let btrfs_unlink() detect inode_extref.
patch[3] fixes a minor bug in check_dir_item due to my careless
	 long ago.
patch[4] fixes a bug about inconsistent path in check_fs_roots()
	 under repair.
patch[5] fixes a corner case about traversal of inode items.
patch[6] enable inode_extref repair support and remove unnecessary
	 checks.
patch[7] add a test image, it can verify above patches except
	 patch[3].

Changelog:
v3:
   Handle fatal errors instead of BUG_ON() in patch[4, 6].
   	  Thanks, Qu Wenruo and Nikolay Borisov.
   Change comments and move declarations in patch[3]. Pointed by Qu Wenruo.
   Handle corner case mentioned in patch[5] in walk_up_tree() not
   	  process_one_leaf().
   Test image are only with inode_extref now.  Suggested by Qu Wenruo.
v2:
   Resend with patches in right order.
   
Su Yue (7):
  btrfs-progs: adjust arguments of btrfs_lookup_inode_extref()
  btrfs-progs: make btrfs_unlink() lookup inode_extref
  btrfs-progs: lowmem check: find dir_item by di_key in check_dir_item()
  btrfs-progs: lowmem: search key of root again after check_fs_root()
    after repair
  btrfs-progs: lowmem: do missing check of last item after
    check_inode_item()
  btrfs-progs: lowmem: optimization and repair for check_inode_extref()
  btrfs-progs: fsck-tests: add test case inode_extref without dir_item
    and dir_index

 check/mode-lowmem.c                           | 206 ++++++++++++++----
 ctree.h                                       |   9 +-
 inode-item.c                                  |   9 +-
 inode.c                                       |  14 +-
 ...node_extref_without_dir_item_and_index.img | Bin 0 -> 4096 bytes
 ... inode_ref_without_dir_item_and_index.img} | Bin
 6 files changed, 188 insertions(+), 50 deletions(-)
 create mode 100644 tests/fsck-tests/009-no-dir-item-or-index/inode_extref_without_dir_item_and_index.img
 rename tests/fsck-tests/009-no-dir-item-or-index/{default_case.img => inode_ref_without_dir_item_and_index.img} (100%)

-- 
2.17.1

[PATCH v3 1/7] btrfs-progs: adjust arguments of btrfs_lookup_inode_extref()

[Su Yue]

The argument index is not used in btrfs_lookup_inode_extref(),
so remove it.
And adjust positions its arguments to make it consistent with
kernel part.

No functional change.

Fixes: 260675657767 ("btrfs-progs: Import btrfs_insert/del/lookup_extref() functions.")
Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
Reviewed-by: Qu Wenruo <wqu@suse.com>
---
 ctree.h      | 9 +++++----
 inode-item.c | 9 +++++----
 2 files changed, 10 insertions(+), 8 deletions(-)

diff --git a/ctree.h b/ctree.h
index 2a2437070ef9..541055a335c2 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2710,10 +2710,11 @@ int btrfs_insert_inode(struct btrfs_trans_handle *trans, struct btrfs_root
 int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root
 		       *root, struct btrfs_path *path,
 		       struct btrfs_key *location, int mod);
-struct btrfs_inode_extref *btrfs_lookup_inode_extref(struct btrfs_trans_handle
-		*trans, struct btrfs_path *path, struct btrfs_root *root,
-		u64 ino, u64 parent_ino, u64 index, const char *name,
-		int namelen, int ins_len);
+struct btrfs_inode_extref *
+btrfs_lookup_inode_extref(struct btrfs_trans_handle *trans,
+			  struct btrfs_root *root, struct btrfs_path *path,
+			  const char *name, int namelen, u64 ino,
+			  u64 parent_ino, int ins_len);
 int btrfs_del_inode_extref(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root,
 			   const char *name, int name_len,
diff --git a/inode-item.c b/inode-item.c
index 1cc106670cd4..ca0052bc2f87 100644
--- a/inode-item.c
+++ b/inode-item.c
@@ -227,10 +227,11 @@ static int btrfs_find_name_in_ext_backref(struct btrfs_path *path,
 	return 0;
 }
 
-struct btrfs_inode_extref *btrfs_lookup_inode_extref(struct btrfs_trans_handle
-		*trans, struct btrfs_path *path, struct btrfs_root *root,
-		u64 ino, u64 parent_ino, u64 index, const char *name,
-		int namelen, int ins_len)
+struct btrfs_inode_extref *
+btrfs_lookup_inode_extref(struct btrfs_trans_handle *trans,
+			  struct btrfs_root *root, struct btrfs_path *path,
+			  const char *name, int namelen, u64 ino,
+			  u64 parent_ino, int ins_len)
 {
 	struct btrfs_key key;
 	struct btrfs_inode_extref *extref;
-- 
2.17.1

[PATCH v3 2/7] btrfs-progs: make btrfs_unlink() lookup inode_extref

[Su Yue]

btrfs_unlink() uses btrfs_lookup_inode_ref() to look up inode_ref
but forget inode_extref case.

Let btrfs_unlink() call btrfs_lookup_inode_extref() if inode_ref is
found and EXTENDED_IREF feature is enabled.

Fixes: 0cc75eddd093 ("btrfs-progs: Add btrfs_unlink() and btrfs_add_link() functions.")
Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
Reviewed-by: Qu Wenruo <wqu@suse.com>
---
 inode.c | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

diff --git a/inode.c b/inode.c
index 2398bca4a109..598ad0ab6b4c 100644
--- a/inode.c
+++ b/inode.c
@@ -277,6 +277,7 @@ int btrfs_unlink(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 	struct btrfs_key key;
 	struct btrfs_inode_item *inode_item;
 	struct btrfs_inode_ref *inode_ref;
+	struct btrfs_inode_extref *inode_extref = NULL;
 	struct btrfs_dir_item *dir_item;
 	u64 inode_size;
 	u32 nlinks;
@@ -296,7 +297,18 @@ int btrfs_unlink(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 		ret = PTR_ERR(inode_ref);
 		goto out;
 	}
-	if (inode_ref)
+
+	if (!inode_ref && btrfs_fs_incompat(root->fs_info, EXTENDED_IREF)) {
+		btrfs_release_path(path);
+		inode_extref = btrfs_lookup_inode_extref(trans, root, path,
+					 name, namelen, ino, parent_ino, 0);
+		if (IS_ERR(inode_extref)) {
+			ret = PTR_ERR(inode_extref);
+			goto out;
+		}
+	}
+
+	if (inode_ref || inode_extref)
 		del_inode_ref = 1;
 	btrfs_release_path(path);
 
-- 
2.17.1

[PATCH v3 3/7] btrfs-progs: lowmem check: find dir_item by di_key in check_dir_item()

[Su Yue]

In check_dir_item, we are going to search corresponding
dir_item/index.

Commit 564901eac7a4 ("btrfs-progs: check: introduce
print_dir_item_err()") Changed argument name from key to di_key but
forgot to change the key name for dir_item search.
So @key shouldn't be used here. It should be @di_key.
Change comment about parameters too.

To keep compactness, move declarations into while loop in
check_dir_item().

Fixes: 564901eac7a4 ("btrfs-progs: check: introduce print_dir_item_err()")
Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
---
 check/mode-lowmem.c | 22 +++++++++++-----------
 1 file changed, 11 insertions(+), 11 deletions(-)

diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
index 1bce44f5658a..4db12cc7f9fe 100644
--- a/check/mode-lowmem.c
+++ b/check/mode-lowmem.c
@@ -1529,7 +1529,7 @@ static void print_dir_item_err(struct btrfs_root *root, struct btrfs_key *key,
  * 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
+ * @di_key:	the key of the dir_item/dir_index
  * @path:       the path
  * @size:	the st_size of the INODE_ITEM
  *
@@ -1540,20 +1540,11 @@ static int check_dir_item(struct btrfs_root *root, struct btrfs_key *di_key,
 			  struct btrfs_path *path, u64 *size)
 {
 	struct btrfs_dir_item *di;
-	struct btrfs_inode_item *ii;
-	struct btrfs_key key;
-	struct btrfs_key location;
 	struct extent_buffer *node;
 	int slot;
 	char namebuf[BTRFS_NAME_LEN] = {0};
 	u32 total;
 	u32 cur = 0;
-	u32 len;
-	u32 name_len;
-	u32 data_len;
-	u8 filetype;
-	u32 mode = 0;
-	u64 index;
 	int ret;
 	int err;
 	int tmp_err;
@@ -1588,6 +1579,15 @@ begin:
 	memset(namebuf, 0, sizeof(namebuf) / sizeof(*namebuf));
 
 	while (cur < total) {
+		struct btrfs_inode_item *ii;
+		struct btrfs_key key;
+		struct btrfs_key location;
+		u8 filetype;
+		u32 data_len;
+		u32 name_len;
+		u32 len;
+		u32 mode = 0;
+		u64 index;
 		/*
 		 * For DIR_ITEM set index to (u64)-1, so that find_inode_ref
 		 * ignore index check.
@@ -1658,7 +1658,7 @@ begin:
 
 		/* check relative INDEX/ITEM */
 		key.objectid = di_key->objectid;
-		if (key.type == BTRFS_DIR_ITEM_KEY) {
+		if (di_key->type == BTRFS_DIR_ITEM_KEY) {
 			key.type = BTRFS_DIR_INDEX_KEY;
 			key.offset = index;
 		} else {
-- 
2.17.1

[PATCH v3 4/7] btrfs-progs: lowmem: search key of root again after check_fs_root() after repair

[Su Yue]

In check_fs_roots_lowmem(), we do search and follow the resulted path
to call check_fs_root(), then call btrfs_next_item() to check next
root.
However, if repair is enabled, the root tree can be cowed, the
existed path can cause strange errors.

Solution:
  If repair, save the key before calling check_fs_root,
  search the saved key again before checking next root.

Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
---
 check/mode-lowmem.c | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)

diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
index 4db12cc7f9fe..db44456fd85b 100644
--- a/check/mode-lowmem.c
+++ b/check/mode-lowmem.c
@@ -4967,9 +4967,13 @@ int check_fs_roots_lowmem(struct btrfs_fs_info *fs_info)
 	}
 
 	while (1) {
+		struct btrfs_key saved_key;
+
 		node = path.nodes[0];
 		slot = path.slots[0];
 		btrfs_item_key_to_cpu(node, &key, slot);
+		if (repair)
+			saved_key = key;
 		if (key.objectid > BTRFS_LAST_FREE_OBJECTID)
 			goto out;
 		if (key.type == BTRFS_ROOT_ITEM_KEY &&
@@ -5000,6 +5004,24 @@ int check_fs_roots_lowmem(struct btrfs_fs_info *fs_info)
 			err |= ret;
 		}
 next:
+		/*
+		 * Since root tree can be cowed during repair,
+		 * here search the saved key again.
+		 */
+		if (repair) {
+			btrfs_release_path(&path);
+			ret = btrfs_search_slot(NULL, fs_info->tree_root,
+						&saved_key, &path, 0, 0);
+			/* Repair never deletes trees, search must succeed. */
+			if (ret > 0)
+				ret = -ENOENT;
+			if (ret) {
+				error(
+			"search root key[%llu %u %llu] failed after repair: %s",
+				      saved_key.objectid, saved_key.type,
+				      saved_key.offset, strerror(-ret));
+			}
+		}
 		ret = btrfs_next_item(tree_root, &path);
 		if (ret > 0)
 			goto out;
-- 
2.17.1

[PATCH v3 5/7] btrfs-progs: lowmem: do missing check of last item after check_inode_item()

[Su Yue]

After call of check_inode_item(), path may point to the last unchecked
slot of the leaf. The outer walk_up_tree() always treats the position
as checked slot then skips to the next. The last item will never be
checked.

While checking backrefs, path passed to walk_up_tree() always
points to a checked slot.
While checking fs trees, path passed to walk_up_tree() always
points to an unchecked slot.

Solution:
Add an argument @is_checked to walk_up_tree() to decide whether
to skip current slot.

Fixes: 5e2dc770471b ("btrfs-progs: check: skip shared node or leaf check for low_memory mode")
Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
---
 check/mode-lowmem.c | 37 +++++++++++++++++++++++++++++++++----
 1 file changed, 33 insertions(+), 4 deletions(-)

diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
index db44456fd85b..612e5e28e45b 100644
--- a/check/mode-lowmem.c
+++ b/check/mode-lowmem.c
@@ -4597,22 +4597,38 @@ static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
 	return err;
 }
 
+/*
+ * Walk up throuh the path. Make path point to next slot to be checked.
+ * walk_down_tree() should be called after this function.
+ *
+ * @root:	root of the tree
+ * @path:	will point to next slot to check for walk_down_tree()
+ * @level:	returns with level of next node to be checked
+ * @is_checked:	means is the current node checked or not
+ *		if false, the slot is unchecked, do not increase the slot
+ *		if true, means increase the slot of the current node
+ *
+ * Returns 0 means success.
+ * Returns >0 means the whole loop of walk up/down should be broken.
+ */
 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
-			int *level)
+			int *level, bool is_checked)
 {
 	int i;
 	struct extent_buffer *leaf;
+	int skip_cur = is_checked ? 1 : 0;
 
 	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]++;
+		if (path->slots[i] + skip_cur < btrfs_header_nritems(leaf)) {
+			path->slots[i] += skip_cur;
 			*level = i;
 			return 0;
 		}
 		free_extent_buffer(path->nodes[*level]);
 		path->nodes[*level] = NULL;
 		*level = i + 1;
+		skip_cur = 1;
 	}
 	return 1;
 }
@@ -4815,7 +4831,20 @@ static int check_btrfs_root(struct btrfs_root *root, int check_all)
 			break;
 		}
 
-		ret = walk_up_tree(root, &path, &level);
+		/*
+		 * The logical of walk trees are shared between backrefs
+		 * check and fs trees check.
+		 * In checking backrefs(check_all is true), after
+		 * check_leaf_items() returns, path points to
+		 * last checked item.
+		 * In checking fs roots(check_all is false), after
+		 * process_one_leaf() returns, path points to unchecked item.
+		 *
+		 * walk_up_tree() is reponsible to make path point to next
+		 * slot to be checked, above case is handled in
+		 * walk_up_tree().
+		 */
+		ret = walk_up_tree(root, &path, &level, check_all);
 		if (ret != 0) {
 			/* Normal exit, reset ret to err */
 			ret = err;
-- 
2.17.1

[PATCH v3 6/7] btrfs-progs: lowmem: optimization and repair for check_inode_extref()

[Su Yue]

inode_extref is much similar with inode_ref, most codes are reused in
check_inode_extref().
Exceptions:
There is no need to check root directory, so remove it.
Make check_inode_extref() verify hash value with key offset now.

And lowmem check can detect errors about inode_extref and try to
repair errors.

Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
---
 check/mode-lowmem.c | 125 +++++++++++++++++++++++++++++++++++---------
 1 file changed, 99 insertions(+), 26 deletions(-)

diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
index 612e5e28e45b..53e4fdccd740 100644
--- a/check/mode-lowmem.c
+++ b/check/mode-lowmem.c
@@ -1182,37 +1182,86 @@ out:
  *
  * 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)
+static int check_inode_extref(struct btrfs_root *root, struct btrfs_key *ref_key,
+			      struct btrfs_path *path, char *name_ret,
+			      u32 *namelen_ret, u64 *refs_ret, int mode)
 {
 	struct btrfs_key key;
 	struct btrfs_key location;
 	struct btrfs_inode_extref *extref;
+	struct extent_buffer *node;
 	char namebuf[BTRFS_NAME_LEN] = {0};
 	u32 total;
-	u32 cur = 0;
+	u32 cur;
 	u32 len;
 	u32 name_len;
 	u64 index;
 	u64 parent;
+	int err;
+	int tmp_err;
 	int ret;
-	int err = 0;
+	int slot;
+	u64 refs;
+	bool search_again = false;
 
 	location.objectid = ref_key->objectid;
 	location.type = BTRFS_INODE_ITEM_KEY;
 	location.offset = 0;
+begin:
+	cur = 0;
+	err = 0;
+	refs = *refs_ret;
+	*namelen_ret = 0;
+
+	/* since after repair, path and the dir item may be changed */
+	if (search_again) {
+		search_again = false;
+		btrfs_release_path(path);
+		ret = btrfs_search_slot(NULL, root, ref_key, path, 0, 0);
+		/*
+		 * The item was deleted, let the path point to the last checked
+		 * item.
+		 */
+		if (ret > 0) {
+			if (path->slots[0] == 0) {
+				ret = btrfs_prev_leaf(root, path);
+				/*
+				 * we are checking the inode item, there must
+				 * be some items before, the case shall never
+				 * happen.
+				 */
+				if (ret > 0)
+					ret = -EIO;
+				if (ret)
+					error(
+		"failed to get item before INODE_REF[%llu, %llu] root %llu: %s",
+					      ref_key->objectid, ref_key->offset,
+					      root->objectid, strerror(-ret));
+			} else {
+				path->slots[0]--;
+				ret = 0;
+			}
+			goto out;
+		} else if (ret < 0) {
+			err |= FATAL_ERROR;
+			goto out;
+		}
+	}
+
+	node = path->nodes[0];
+	slot = path->slots[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);
+loop:
+	/* Update inode ref count */
+	refs++;
+	tmp_err = 0;
 	parent = btrfs_inode_extref_parent(node, extref);
+	index = btrfs_inode_extref_index(node, extref);
+	name_len = btrfs_inode_extref_name_len(node, extref);
+
 	if (name_len <= BTRFS_NAME_LEN) {
 		len = name_len;
 	} else {
@@ -1220,37 +1269,61 @@ next:
 		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",
+	/* verify hash value */
+	if (ref_key->offset != btrfs_extref_hash(parent, namebuf, len)) {
+		err |= FATAL_ERROR;
+		error("root %llu INODE_EXTREF[%llu %llu] name %s namelen %u mode %d mismatch with its hash, wanted %llu have %llu",
 		      root->objectid, ref_key->objectid, ref_key->offset,
-		      namebuf);
-		err |= ROOT_DIR_ERROR;
+		      namebuf, len, mode, ref_key->offset,
+		      btrfs_extref_hash(parent, namebuf, len));
+		goto out;
+	}
+
+	/* copy the first name found to name_ret */
+	if (refs == 1 && name_ret) {
+		memcpy(name_ret, namebuf, len);
+		*namelen_ret = len;
 	}
 
-	/* find related dir_index */
+	/* Find related DIR_INDEX */
 	key.objectid = parent;
 	key.type = BTRFS_DIR_INDEX_KEY;
 	key.offset = index;
-	ret = find_dir_item(root, &key, &location, namebuf, len, mode);
-	err |= ret;
+	tmp_err |= find_dir_item(root, &key, &location, namebuf, len,
+			    imode_to_type(mode));
 
-	/* find related dir_item */
+	/* 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, &key, &location, namebuf, len, mode);
-	err |= ret;
+	tmp_err |= find_dir_item(root, &key, &location, namebuf, len,
+			    imode_to_type(mode));
+
+	if (tmp_err && repair) {
+		ret = repair_ternary_lowmem(root, parent, ref_key->objectid,
+			    index, namebuf, name_len, imode_to_type(mode),
+			    tmp_err);
+		if (!ret) {
+			search_again = true;
+			goto begin;
+		}
+	}
 
+	print_inode_ref_err(root, ref_key, index, namebuf, name_len,
+			    imode_to_type(mode), tmp_err);
+
+	err |= tmp_err;
 	len = sizeof(*extref) + name_len;
 	extref = (struct btrfs_inode_extref *)((char *)extref + len);
 	cur += len;
 
 	if (cur < total)
-		goto next;
-
+		goto loop;
+out:
+	*refs_ret = refs;
 	return err;
 }
 
@@ -2426,8 +2499,8 @@ static int check_inode_item(struct btrfs_root *root, struct btrfs_path *path)
 				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);
+			ret = check_inode_extref(root, &key, path, namebuf,
+						 &name_len, &refs, mode);
 			err |= ret;
 			break;
 		}
-- 
2.17.1

[PATCH v3 7/7] btrfs-progs: fsck-tests: add test case inode_extref without dir_item and dir_index

[Su Yue]

Inode 257 is only with inode_extref without inode_ref.
And This case contains an inode_extref:
==========================================
...
   item 1 key (257 INODE_EXTREF 3460996356) itemoff 3947 itemsize 24
                index 257 parent 256 namelen 6 name: foo255
...
==========================================
The related dir_item and dir_index are missing.

Add the case to ensure both original and lowmem mode check can handle
the case of inode_extref.

Lowmem part is supported since patch named
'btrfs-progs: lowmem: optimization and repair for check_inode_extref()'.

Rename default_case.img to inode_ref_without_dir_item_and_index.img.

Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
---
 .../inode_extref_without_dir_item_and_index.img  | Bin 0 -> 4096 bytes
 ... => inode_ref_without_dir_item_and_index.img} | Bin
 2 files changed, 0 insertions(+), 0 deletions(-)
 create mode 100644 tests/fsck-tests/009-no-dir-item-or-index/inode_extref_without_dir_item_and_index.img
 rename tests/fsck-tests/009-no-dir-item-or-index/{default_case.img => inode_ref_without_dir_item_and_index.img} (100%)

diff --git a/tests/fsck-tests/009-no-dir-item-or-index/inode_extref_without_dir_item_and_index.img b/tests/fsck-tests/009-no-dir-item-or-index/inode_extref_without_dir_item_and_index.img
new file mode 100644
index 0000000000000000000000000000000000000000..769dabe9bdeff9b9582a49b6de9a7ff14be9b389
GIT binary patch
literal 4096
zcmeHJeKgeBAO4OpjF(}&#0)d7VKBADZ0yK17=|%Q8B2-Kcpp@RG?l?%nb9C`8B}DJ
zyro1NiA>(MvKp;QDlA3VijWBNV_(kso&B|c|MrjWx#zjhz31F}?(^Jpp3glUm>V&o
z@7WCe*<{v6(C>YX%&afM;p+%IU59x3Is(<}z;Iqiz({%xivQphQfnL!U)v7=7uVrS
z`{KYC2mZ|tum%bn2b!}%$_;S$Taiz+<I0k|C#eesI3*bw>ecOBf6xfaFr&DBn03%w
zkPPF%J;*=`PgWr6lY(ZzHs6D0Ymhs5<W%hxhjcy-wS5N}-syh_4>x|j_XzRhLdGv2
z^fe#EOw^`7O`e#~gt2;GtH>5lOv>qQHP<OMNs>3%5}dDM&a;^p8g5T^#>-PhI0Qt<
zP*)`4K@aO+ah{Bv2|*2#VB~Bk@~AO+)J!^llLl(HA2sWMLHX`*Z_l@+cmpf?TgUkN
zK67z_-BlwH1$2{?^dNm&Q!n+T=UY?858db24|H40q{}2MYv9@9*GmNO#&FCv)_9HC
zsv|7_QQF&Yol%NXQjDWiuBos$*GXGB|3q%ha@mb%?^kc@J*Ts~=>;1czG;IY+Omo`
z7&(VAIWV}rKQBg65mc_qFluvj<iQxphGj{BU@=>>?6^8V;lI@UF#(~02IJ18djSmV
zUriED#qnuqyZv9)xHV1;4_WPbmgh;DE$t!(YJ(|KV8Sdyu0VETi)!dbp9RP;{sE}!
zM0g7zC0x{8Ba47FB3teSY8iN8JGV*#oPPFLUK6(BtF_~E!eF3(5VnQRX2H<wet+(|
zUYuUym}AzGM2$NoiIXUU9C4LCWvgR;jQ#Q0J7B+C<KUxzz1QFNW26O$xjDg62l?U%
zWM+RD`tFU{zDtA5@A`r4a!Y^Kz?*z`rkXXP%k1u;{RVYs=c(^gnZX4FgZ{jIt~l1O
zUe=Qw`qm%!v7JS!!-c-qn|(XLY`Xf~-6@CKR6DzRwu`HJ1xwSJK2Y#9Kdo-a^gImq
zcqGPnF=%yY_1aKR?T*6hm#>ePT8_+2zIhTBvtRv4`CxO{>V=(Nl^!EMrd&mD4w<?Y
zvBSG|c6lM8@UG^I<A);7*;uw6smVLv`Pe5l53QRnOe>^MR?5UBKvi^Yxp0h4(x0T{
zt4zmqi^4~%w~d-sB+>_ev|q_JbhuQm@l35~_NNO)F$W1_(<e3Obpjkq(moX~Owv4Q
zNVVY6!P*bzG!zY)9qiZF_^^?7D9Jv?)45KH7r~6#YE=v3&4}qWq-sjZGZ1zB^1Cz|
zDY27Zvn-@}Mz*?dX!#T+!_yOg?5k<Ca8Y&^UaG#8+V0D|71y`~Q#C<{Uw)s0v^s;o
z*t>M(qZ5{R$f~k3B}#qLX{oxBbW~o;NB09+&&F1N8J5qLHdWW9k}3Klg%HIwuAx}W
zYfywGaw%dwubh)?XA3bsq+8~(T6N$R97EB|;JO(QY{Fx6^8I7~v_W!|nYD1P|M*Wi
zmQ5M+O%ze=mFu&^S__T1XyRg&$idCbJtE=ArR(6Z;kZ4nnf3EilR`U!nSRJo7x|yN
zH(e{tGG!s<&gXrzYc!yJuQ!!<=RWT231ltQScvPs&)xQ5p9hhWYf~5!dV1#wC?Xa7
zvi)PT8be(gv1_^N!8;MkD-Us7bCKQtE@)NoD&vMub9a#i$e?1uV#@|~Tk^i_Af@>$
z+vo1g)$+YEyThZu)|3x>wK=q6kGP=cg!hYE_^OpSO7tg5a8}>_p--PuXb))vXPjI~
zHogj`Er-x6C|;@f<JBp)tZE%k#J@KB5=}w0_-z+#dyf-#?(ns*Jmxx?jZ8nRM77hI
ztVwiM;of}7P&e6uO31=gc6H*AC4&Qq4#nvc1nMSut_}`T@?I|0-Rgq}qSU63pdfVR
zdIb2W*NHv#4!FTej0A{MYgZx9xf>-3VdN+|UxD!-Vk#fC;sUjt3~}I+PIwN;StY^u
z@f?gu&4*w2?82#)>^#QzJ)0f~6K)CQmhmw;GeO)CM8|Xc0ayMtOr>21PP@dY645aj
z2EE5AH-ZRJ+>=5^4p(CKoA*Z1i)ruZO{%d<J!h0NgkfBZOHYRsK4Obz3<M5A)onA6
zRM7Ru`df(dk$Y3-ZcI%-rn*ObRUPR{6{CH7?%^l4sWxubI~Rcb7CmDNKVPeuXyo^p
z46BUIyZB2$dnBPt5*@~jLh6IByUsT$<{AlE;<FdU0qrt}k=wjF<6m_3hBoLB{g5g*
z`LAz#Q%{}}#JX?}HnH9e+Bgl2PNX&7ZpN|`RzHjkfn>%)SOcdp$0{y-rbZ=0IRB7r
zBszP`T4X=HT159!>{wP*)PlModhmE?JhF!@2X^HFcnZSB7c7_&C{t{J?m@-e-|Nob
za%?Tb!@+?F@Z&2<A2w&&O;-&8rE0C%lU7I<Ho%*N6xW0I&9^T_ib9*cu=5hL;dheR
z67y^YTfDXTR=i6Qkb5}Dmap2XA9X@U^{NkeBLPQ|!C|<j7l0?3_aMEZ<c*g0=A0Hk
zGOaajKrUz4It$tu#f&rNegnZ>l>gyr@0*7EO0|h<UN&hk-I*0D=~n&s?mDXLi7iD0
zQ#}LffFsAk&=cd98d0*2Q1V_K^10jMH0?A(fmC#qECP!E4u1GIVJ~&)xeOR4Y=kvp
zAct=*+waMD+*A?FD>c{0s~E^wSOj_+^x`f!u_x0EzTf?QRDZmdQXho$T8Rd=-OC{F
zB>E>IkL&GPITV;ZngJ<vbE;bDkK{0ehJifxcw*w5-LkI2%i&V?g#7Nv#AcER+6v+1
z<QS6Lejp)#>+L*k6dqr~97P-SjuGegDm$!5!0q!AAFo);m#r3n_GRW+5aSGRnu6VT
zr+SyvPMj_*1r?u`!V*Q1L&F-Bb_>$wn5rne9Mil>RU`YsVzDZOQ%+15VYS5Avv;r>
z#SZnYSVFM_whgOP?66&gEgq$WD~HTjTR_oFBB0=p5lGiJ%9%~-8F!cePhDR7a!iYW
z==#B7nLTrZ1Xq0pB{lK*^WLUBZ2@!>*^DFW1yaC3s$Jb$6KViL9Nz^LbFCP3szGEL
zAq@5JR2jxY0QK|ZcUc2dJ!)=#tzaWtjd#!IJBunXbvJvP4N?<D<aiZq4>U8-^yd5E
zQH;rzhq*&@(FX=4$CJ>N8EQLCOmwP}^Op)UI6j~(s4{=%f^xeLqam|2mQZ(hrt95b
zmj7x_Pe}CnT(w>k!D>zI4DuEK;@4TaAIQDWZI7LzwP^48{Y_!O#I~)D|K^|Qm%IHx
G9QY4={DzYN

literal 0
HcmV?d00001

diff --git a/tests/fsck-tests/009-no-dir-item-or-index/default_case.img b/tests/fsck-tests/009-no-dir-item-or-index/inode_ref_without_dir_item_and_index.img
similarity index 100%
rename from tests/fsck-tests/009-no-dir-item-or-index/default_case.img
rename to tests/fsck-tests/009-no-dir-item-or-index/inode_ref_without_dir_item_and_index.img
-- 
2.17.1

Re: [PATCH v3 3/7] btrfs-progs: lowmem check: find dir_item by di_key in check_dir_item()

[Qu Wenruo]

On 2018/9/17 下午3:28, Su Yue wrote:
> In check_dir_item, we are going to search corresponding
> dir_item/index.
> 
> Commit 564901eac7a4 ("btrfs-progs: check: introduce
> print_dir_item_err()") Changed argument name from key to di_key but
> forgot to change the key name for dir_item search.
> So @key shouldn't be used here. It should be @di_key.
> Change comment about parameters too.
> 
> To keep compactness, move declarations into while loop in
> check_dir_item().
> 
> Fixes: 564901eac7a4 ("btrfs-progs: check: introduce print_dir_item_err()")
> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
> ---
>  check/mode-lowmem.c | 22 +++++++++++-----------
>  1 file changed, 11 insertions(+), 11 deletions(-)
> 
> diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
> index 1bce44f5658a..4db12cc7f9fe 100644
> --- a/check/mode-lowmem.c
> +++ b/check/mode-lowmem.c
> @@ -1529,7 +1529,7 @@ static void print_dir_item_err(struct btrfs_root *root, struct btrfs_key *key,
>   * 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
> + * @di_key:	the key of the dir_item/dir_index
>   * @path:       the path
>   * @size:	the st_size of the INODE_ITEM
>   *
> @@ -1540,20 +1540,11 @@ static int check_dir_item(struct btrfs_root *root, struct btrfs_key *di_key,
>  			  struct btrfs_path *path, u64 *size)
>  {
>  	struct btrfs_dir_item *di;
> -	struct btrfs_inode_item *ii;
> -	struct btrfs_key key;
> -	struct btrfs_key location;
>  	struct extent_buffer *node;
>  	int slot;
>  	char namebuf[BTRFS_NAME_LEN] = {0};
>  	u32 total;
>  	u32 cur = 0;
> -	u32 len;
> -	u32 name_len;
> -	u32 data_len;
> -	u8 filetype;
> -	u32 mode = 0;
> -	u64 index;
>  	int ret;
>  	int err;
>  	int tmp_err;
> @@ -1588,6 +1579,15 @@ begin:
>  	memset(namebuf, 0, sizeof(namebuf) / sizeof(*namebuf));
>  
>  	while (cur < total) {
> +		struct btrfs_inode_item *ii;
> +		struct btrfs_key key;

If we have several keys, it's better to avoid generic name like @key.

In this case, the @key is only used for find_dir_item(), thus it could
be called @found_dir_key.

Thanks,
Qu

> +		struct btrfs_key location;
> +		u8 filetype;
> +		u32 data_len;
> +		u32 name_len;
> +		u32 len;
> +		u32 mode = 0;
> +		u64 index;
>  		/*
>  		 * For DIR_ITEM set index to (u64)-1, so that find_inode_ref
>  		 * ignore index check.
> @@ -1658,7 +1658,7 @@ begin:
>  
>  		/* check relative INDEX/ITEM */
>  		key.objectid = di_key->objectid;
> -		if (key.type == BTRFS_DIR_ITEM_KEY) {
> +		if (di_key->type == BTRFS_DIR_ITEM_KEY) {
>  			key.type = BTRFS_DIR_INDEX_KEY;
>  			key.offset = index;
>  		} else {
> 

Re: [PATCH v3 4/7] btrfs-progs: lowmem: search key of root again after check_fs_root() after repair

[Qu Wenruo]

On 2018/9/17 下午3:28, Su Yue wrote:
> In check_fs_roots_lowmem(), we do search and follow the resulted path
> to call check_fs_root(), then call btrfs_next_item() to check next
> root.
> However, if repair is enabled, the root tree can be cowed, the
> existed path can cause strange errors.
> 
> Solution:
>   If repair, save the key before calling check_fs_root,
>   search the saved key again before checking next root.
> 
> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>

The idea is pretty valid, however I'm not pretty sure about one practice
below.

> ---
>  check/mode-lowmem.c | 22 ++++++++++++++++++++++
>  1 file changed, 22 insertions(+)
> 
> diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
> index 4db12cc7f9fe..db44456fd85b 100644
> --- a/check/mode-lowmem.c
> +++ b/check/mode-lowmem.c
> @@ -4967,9 +4967,13 @@ int check_fs_roots_lowmem(struct btrfs_fs_info *fs_info)
>  	}
>  
>  	while (1) {
> +		struct btrfs_key saved_key;
> +
>  		node = path.nodes[0];
>  		slot = path.slots[0];
>  		btrfs_item_key_to_cpu(node, &key, slot);
> +		if (repair)
> +			saved_key = key;

Is this OK? Shouldn't it be something like memcpy(&saved_key, &key,
sizeof(key));

Or some new C standard make it work?

Although compiler doesn't give any warning on this.

Thanks,
Qu

>  		if (key.objectid > BTRFS_LAST_FREE_OBJECTID)
>  			goto out;
>  		if (key.type == BTRFS_ROOT_ITEM_KEY &&
> @@ -5000,6 +5004,24 @@ int check_fs_roots_lowmem(struct btrfs_fs_info *fs_info)
>  			err |= ret;
>  		}
>  next:
> +		/*
> +		 * Since root tree can be cowed during repair,
> +		 * here search the saved key again.
> +		 */
> +		if (repair) {
> +			btrfs_release_path(&path);
> +			ret = btrfs_search_slot(NULL, fs_info->tree_root,
> +						&saved_key, &path, 0, 0);
> +			/* Repair never deletes trees, search must succeed. */
> +			if (ret > 0)
> +				ret = -ENOENT;
> +			if (ret) {
> +				error(
> +			"search root key[%llu %u %llu] failed after repair: %s",
> +				      saved_key.objectid, saved_key.type,
> +				      saved_key.offset, strerror(-ret));
> +			}
> +		}
>  		ret = btrfs_next_item(tree_root, &path);
>  		if (ret > 0)
>  			goto out;
> 

Re: [PATCH v3 5/7] btrfs-progs: lowmem: do missing check of last item after check_inode_item()

[Qu Wenruo]

On 2018/9/17 下午3:28, Su Yue wrote:
> After call of check_inode_item(), path may point to the last unchecked
> slot of the leaf. The outer walk_up_tree() always treats the position
> as checked slot then skips to the next. The last item will never be
> checked.
> 
> While checking backrefs, path passed to walk_up_tree() always
> points to a checked slot.
> While checking fs trees, path passed to walk_up_tree() always
> points to an unchecked slot.

Can we unify this behavior?

E.g, always points to an unchecked slot.

It would make things easier and no need for the extra parameter.

Thanks,
Qu

> 
> Solution:
> Add an argument @is_checked to walk_up_tree() to decide whether
> to skip current slot.
> 
> Fixes: 5e2dc770471b ("btrfs-progs: check: skip shared node or leaf check for low_memory mode")
> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
> ---
>  check/mode-lowmem.c | 37 +++++++++++++++++++++++++++++++++----
>  1 file changed, 33 insertions(+), 4 deletions(-)
> 
> diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
> index db44456fd85b..612e5e28e45b 100644
> --- a/check/mode-lowmem.c
> +++ b/check/mode-lowmem.c
> @@ -4597,22 +4597,38 @@ static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
>  	return err;
>  }
>  
> +/*
> + * Walk up throuh the path. Make path point to next slot to be checked.
> + * walk_down_tree() should be called after this function.
> + *
> + * @root:	root of the tree
> + * @path:	will point to next slot to check for walk_down_tree()
> + * @level:	returns with level of next node to be checked
> + * @is_checked:	means is the current node checked or not
> + *		if false, the slot is unchecked, do not increase the slot
> + *		if true, means increase the slot of the current node
> + *
> + * Returns 0 means success.
> + * Returns >0 means the whole loop of walk up/down should be broken.
> + */
>  static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
> -			int *level)
> +			int *level, bool is_checked)
>  {
>  	int i;
>  	struct extent_buffer *leaf;
> +	int skip_cur = is_checked ? 1 : 0;
>  
>  	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]++;
> +		if (path->slots[i] + skip_cur < btrfs_header_nritems(leaf)) {
> +			path->slots[i] += skip_cur;
>  			*level = i;
>  			return 0;
>  		}
>  		free_extent_buffer(path->nodes[*level]);
>  		path->nodes[*level] = NULL;
>  		*level = i + 1;
> +		skip_cur = 1;
>  	}
>  	return 1;
>  }
> @@ -4815,7 +4831,20 @@ static int check_btrfs_root(struct btrfs_root *root, int check_all)
>  			break;
>  		}
>  
> -		ret = walk_up_tree(root, &path, &level);
> +		/*
> +		 * The logical of walk trees are shared between backrefs
> +		 * check and fs trees check.
> +		 * In checking backrefs(check_all is true), after
> +		 * check_leaf_items() returns, path points to
> +		 * last checked item.
> +		 * In checking fs roots(check_all is false), after
> +		 * process_one_leaf() returns, path points to unchecked item.
> +		 *
> +		 * walk_up_tree() is reponsible to make path point to next
> +		 * slot to be checked, above case is handled in
> +		 * walk_up_tree().
> +		 */
> +		ret = walk_up_tree(root, &path, &level, check_all);
>  		if (ret != 0) {
>  			/* Normal exit, reset ret to err */
>  			ret = err;
> 

Re: [PATCH v3 4/7] btrfs-progs: lowmem: search key of root again after check_fs_root() after repair

[Su Yue]

On 2018/9/17 8:51 PM, Qu Wenruo wrote:
> 
> 
> On 2018/9/17 下午3:28, Su Yue wrote:
>> In check_fs_roots_lowmem(), we do search and follow the resulted path
>> to call check_fs_root(), then call btrfs_next_item() to check next
>> root.
>> However, if repair is enabled, the root tree can be cowed, the
>> existed path can cause strange errors.
>>
>> Solution:
>>    If repair, save the key before calling check_fs_root,
>>    search the saved key again before checking next root.
>>
>> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
> 
> The idea is pretty valid, however I'm not pretty sure about one practice
> below.
> 
>> ---
>>   check/mode-lowmem.c | 22 ++++++++++++++++++++++
>>   1 file changed, 22 insertions(+)
>>
>> diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
>> index 4db12cc7f9fe..db44456fd85b 100644
>> --- a/check/mode-lowmem.c
>> +++ b/check/mode-lowmem.c
>> @@ -4967,9 +4967,13 @@ int check_fs_roots_lowmem(struct btrfs_fs_info *fs_info)
>>   	}
>>   
>>   	while (1) {
>> +		struct btrfs_key saved_key;
>> +
>>   		node = path.nodes[0];
>>   		slot = path.slots[0];
>>   		btrfs_item_key_to_cpu(node, &key, slot);
>> +		if (repair)
>> +			saved_key = key;
> 
> Is this OK? Shouldn't it be something like memcpy(&saved_key, &key,
> sizeof(key));
> 
> Or some new C standard make it work?
> 
I don't quite know how C89 standard defines this behavior.
It should work in C99...

Seems you are not familiar with this style, will use memcpy.

Thanks,
Su
> Although compiler doesn't give any warning on this.
> 
> Thanks,
> Qu
> 
>>   		if (key.objectid > BTRFS_LAST_FREE_OBJECTID)
>>   			goto out;
>>   		if (key.type == BTRFS_ROOT_ITEM_KEY &&
>> @@ -5000,6 +5004,24 @@ int check_fs_roots_lowmem(struct btrfs_fs_info *fs_info)
>>   			err |= ret;
>>   		}
>>   next:
>> +		/*
>> +		 * Since root tree can be cowed during repair,
>> +		 * here search the saved key again.
>> +		 */
>> +		if (repair) {
>> +			btrfs_release_path(&path);
>> +			ret = btrfs_search_slot(NULL, fs_info->tree_root,
>> +						&saved_key, &path, 0, 0);
>> +			/* Repair never deletes trees, search must succeed. */
>> +			if (ret > 0)
>> +				ret = -ENOENT;
>> +			if (ret) {
>> +				error(
>> +			"search root key[%llu %u %llu] failed after repair: %s",
>> +				      saved_key.objectid, saved_key.type,
>> +				      saved_key.offset, strerror(-ret));
>> +			}
>> +		}
>>   		ret = btrfs_next_item(tree_root, &path);
>>   		if (ret > 0)
>>   			goto out;
>>

Re: [PATCH v3 6/7] btrfs-progs: lowmem: optimization and repair for check_inode_extref()

[Qu Wenruo]

On 2018/9/17 下午3:28, Su Yue wrote:
> inode_extref is much similar with inode_ref, most codes are reused in
> check_inode_extref().
> Exceptions:
> There is no need to check root directory, so remove it.

As root directory should only have one INODE_REF "..", so it shouldn't
have any extref at all.

This part is pretty valid.

> Make check_inode_extref() verify hash value with key offset now.
> 
> And lowmem check can detect errors about inode_extref and try to
> repair errors.
> 
> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>

Looks OK to me.

Reviewed-by: Qu Wenruo <wqu@suse.com>

Thanks,
Qu

> ---
>  check/mode-lowmem.c | 125 +++++++++++++++++++++++++++++++++++---------
>  1 file changed, 99 insertions(+), 26 deletions(-)
> 
> diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
> index 612e5e28e45b..53e4fdccd740 100644
> --- a/check/mode-lowmem.c
> +++ b/check/mode-lowmem.c
> @@ -1182,37 +1182,86 @@ out:
>   *
>   * 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)
> +static int check_inode_extref(struct btrfs_root *root, struct btrfs_key *ref_key,
> +			      struct btrfs_path *path, char *name_ret,
> +			      u32 *namelen_ret, u64 *refs_ret, int mode)
>  {
>  	struct btrfs_key key;
>  	struct btrfs_key location;
>  	struct btrfs_inode_extref *extref;
> +	struct extent_buffer *node;
>  	char namebuf[BTRFS_NAME_LEN] = {0};
>  	u32 total;
> -	u32 cur = 0;
> +	u32 cur;
>  	u32 len;
>  	u32 name_len;
>  	u64 index;
>  	u64 parent;
> +	int err;
> +	int tmp_err;
>  	int ret;
> -	int err = 0;
> +	int slot;
> +	u64 refs;
> +	bool search_again = false;
>  
>  	location.objectid = ref_key->objectid;
>  	location.type = BTRFS_INODE_ITEM_KEY;
>  	location.offset = 0;
> +begin:
> +	cur = 0;
> +	err = 0;
> +	refs = *refs_ret;
> +	*namelen_ret = 0;
> +
> +	/* since after repair, path and the dir item may be changed */
> +	if (search_again) {
> +		search_again = false;
> +		btrfs_release_path(path);
> +		ret = btrfs_search_slot(NULL, root, ref_key, path, 0, 0);
> +		/*
> +		 * The item was deleted, let the path point to the last checked
> +		 * item.
> +		 */
> +		if (ret > 0) {
> +			if (path->slots[0] == 0) {
> +				ret = btrfs_prev_leaf(root, path);
> +				/*
> +				 * we are checking the inode item, there must
> +				 * be some items before, the case shall never
> +				 * happen.
> +				 */
> +				if (ret > 0)
> +					ret = -EIO;
> +				if (ret)
> +					error(
> +		"failed to get item before INODE_REF[%llu, %llu] root %llu: %s",
> +					      ref_key->objectid, ref_key->offset,
> +					      root->objectid, strerror(-ret));
> +			} else {
> +				path->slots[0]--;
> +				ret = 0;
> +			}
> +			goto out;
> +		} else if (ret < 0) {
> +			err |= FATAL_ERROR;
> +			goto out;
> +		}
> +	}
> +
> +	node = path->nodes[0];
> +	slot = path->slots[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);
> +loop:
> +	/* Update inode ref count */
> +	refs++;
> +	tmp_err = 0;
>  	parent = btrfs_inode_extref_parent(node, extref);
> +	index = btrfs_inode_extref_index(node, extref);
> +	name_len = btrfs_inode_extref_name_len(node, extref);
> +
>  	if (name_len <= BTRFS_NAME_LEN) {
>  		len = name_len;
>  	} else {
> @@ -1220,37 +1269,61 @@ next:
>  		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",
> +	/* verify hash value */
> +	if (ref_key->offset != btrfs_extref_hash(parent, namebuf, len)) {
> +		err |= FATAL_ERROR;
> +		error("root %llu INODE_EXTREF[%llu %llu] name %s namelen %u mode %d mismatch with its hash, wanted %llu have %llu",
>  		      root->objectid, ref_key->objectid, ref_key->offset,
> -		      namebuf);
> -		err |= ROOT_DIR_ERROR;
> +		      namebuf, len, mode, ref_key->offset,
> +		      btrfs_extref_hash(parent, namebuf, len));
> +		goto out;
> +	}
> +
> +	/* copy the first name found to name_ret */
> +	if (refs == 1 && name_ret) {
> +		memcpy(name_ret, namebuf, len);
> +		*namelen_ret = len;
>  	}
>  
> -	/* find related dir_index */
> +	/* Find related DIR_INDEX */
>  	key.objectid = parent;
>  	key.type = BTRFS_DIR_INDEX_KEY;
>  	key.offset = index;
> -	ret = find_dir_item(root, &key, &location, namebuf, len, mode);
> -	err |= ret;
> +	tmp_err |= find_dir_item(root, &key, &location, namebuf, len,
> +			    imode_to_type(mode));
>  
> -	/* find related dir_item */
> +	/* 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, &key, &location, namebuf, len, mode);
> -	err |= ret;
> +	tmp_err |= find_dir_item(root, &key, &location, namebuf, len,
> +			    imode_to_type(mode));
> +
> +	if (tmp_err && repair) {
> +		ret = repair_ternary_lowmem(root, parent, ref_key->objectid,
> +			    index, namebuf, name_len, imode_to_type(mode),
> +			    tmp_err);
> +		if (!ret) {
> +			search_again = true;
> +			goto begin;
> +		}
> +	}
>  
> +	print_inode_ref_err(root, ref_key, index, namebuf, name_len,
> +			    imode_to_type(mode), tmp_err);
> +
> +	err |= tmp_err;
>  	len = sizeof(*extref) + name_len;
>  	extref = (struct btrfs_inode_extref *)((char *)extref + len);
>  	cur += len;
>  
>  	if (cur < total)
> -		goto next;
> -
> +		goto loop;
> +out:
> +	*refs_ret = refs;
>  	return err;
>  }
>  
> @@ -2426,8 +2499,8 @@ static int check_inode_item(struct btrfs_root *root, struct btrfs_path *path)
>  				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);
> +			ret = check_inode_extref(root, &key, path, namebuf,
> +						 &name_len, &refs, mode);
>  			err |= ret;
>  			break;
>  		}
> 

Re: [PATCH v3 4/7] btrfs-progs: lowmem: search key of root again after check_fs_root() after repair

[Qu Wenruo]

On 2018/9/17 下午8:55, Su Yue wrote:
> 
> 
> On 2018/9/17 8:51 PM, Qu Wenruo wrote:
>>
>>
>> On 2018/9/17 下午3:28, Su Yue wrote:
>>> In check_fs_roots_lowmem(), we do search and follow the resulted path
>>> to call check_fs_root(), then call btrfs_next_item() to check next
>>> root.
>>> However, if repair is enabled, the root tree can be cowed, the
>>> existed path can cause strange errors.
>>>
>>> Solution:
>>>    If repair, save the key before calling check_fs_root,
>>>    search the saved key again before checking next root.
>>>
>>> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
>>
>> The idea is pretty valid, however I'm not pretty sure about one practice
>> below.
>>
>>> ---
>>>   check/mode-lowmem.c | 22 ++++++++++++++++++++++
>>>   1 file changed, 22 insertions(+)
>>>
>>> diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
>>> index 4db12cc7f9fe..db44456fd85b 100644
>>> --- a/check/mode-lowmem.c
>>> +++ b/check/mode-lowmem.c
>>> @@ -4967,9 +4967,13 @@ int check_fs_roots_lowmem(struct btrfs_fs_info
>>> *fs_info)
>>>       }
>>>         while (1) {
>>> +        struct btrfs_key saved_key;
>>> +
>>>           node =ath.nodes[0];
>>>           slot =ath.slots[0];
>>>           btrfs_item_key_to_cpu(node, &key, slot);
>>> +        if (repair)
>>> +            saved_key =ey;
>>
>> Is this OK? Shouldn't it be something like memcpy(&saved_key, &key,
>> sizeof(key));
>>
>> Or some new C standard make it work?
>>
> I don't quite know how C89 standard defines this behavior.
> It should work in C99...
> 
> Seems you are not familiar with this style, will use memcpy.

I just want to make sure what's the preferred way, I'm not saying it's
wrong, just wondering if it's OK for btrfs-progs coding style.
(As it indeed saves some chars)

It could completely turn out that I'm just too stubborn to learn new tricks.

Maybe David could answer this better?

Thanks,
Qu

> 
> Thanks,
> Su
>> Although compiler doesn't give any warning on this.
>>
>> Thanks,
>> Qu
>>
>>>           if (key.objectid > BTRFS_LAST_FREE_OBJECTID)
>>>               goto out;
>>>           if (key.type =BTRFS_ROOT_ITEM_KEY &&
>>> @@ -5000,6 +5004,24 @@ int check_fs_roots_lowmem(struct btrfs_fs_info
>>> *fs_info)
>>>               err |=et;
>>>           }
>>>   next:
>>> +        /*
>>> +         * Since root tree can be cowed during repair,
>>> +         * here search the saved key again.
>>> +         */
>>> +        if (repair) {
>>> +            btrfs_release_path(&path);
>>> +            ret =trfs_search_slot(NULL, fs_info->tree_root,
>>> +                        &saved_key, &path, 0, 0);
>>> +            /* Repair never deletes trees, search must succeed. */
>>> +            if (ret > 0)
>>> +                ret =ENOENT;
>>> +            if (ret) {
>>> +                error(
>>> +            "search root key[%llu %u %llu] failed after repair: %s",
>>> +                      saved_key.objectid, saved_key.type,
>>> +                      saved_key.offset, strerror(-ret));
>>> +            }
>>> +        }
>>>           ret =trfs_next_item(tree_root, &path);
>>>           if (ret > 0)
>>>               goto out;
>>>

Re: [PATCH v3 4/7] btrfs-progs: lowmem: search key of root again after check_fs_root() after repair

[Nikolay Borisov]

On 17.09.2018 15:51, Qu Wenruo wrote:
> 
> 
> On 2018/9/17 下午3:28, Su Yue wrote:
>> In check_fs_roots_lowmem(), we do search and follow the resulted path
>> to call check_fs_root(), then call btrfs_next_item() to check next
>> root.
>> However, if repair is enabled, the root tree can be cowed, the
>> existed path can cause strange errors.
>>
>> Solution:
>>   If repair, save the key before calling check_fs_root,
>>   search the saved key again before checking next root.
>>
>> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
> 
> The idea is pretty valid, however I'm not pretty sure about one practice
> below.
> 
>> ---
>>  check/mode-lowmem.c | 22 ++++++++++++++++++++++
>>  1 file changed, 22 insertions(+)
>>
>> diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
>> index 4db12cc7f9fe..db44456fd85b 100644
>> --- a/check/mode-lowmem.c
>> +++ b/check/mode-lowmem.c
>> @@ -4967,9 +4967,13 @@ int check_fs_roots_lowmem(struct btrfs_fs_info *fs_info)
>>  	}
>>  
>>  	while (1) {
>> +		struct btrfs_key saved_key;
>> +
>>  		node = path.nodes[0];
>>  		slot = path.slots[0];
>>  		btrfs_item_key_to_cpu(node, &key, slot);
>> +		if (repair)
>> +			saved_key = key;
> 
> Is this OK? Shouldn't it be something like memcpy(&saved_key, &key,
> sizeof(key));
> 
> Or some new C standard make it work?
It's not new, basically assigning one struct to another i.e a value
assign, pretty much results in memory copy. One has to be careful when
the structs contains pointer member because in this case both structures
will point to the same memory.

In this particular case since btrfs_key consists of primitive types
doing a direct assign is fine.
> 
> Although compiler doesn't give any warning on this.
> 
> Thanks,
> Qu
> 
>>  		if (key.objectid > BTRFS_LAST_FREE_OBJECTID)
>>  			goto out;
>>  		if (key.type == BTRFS_ROOT_ITEM_KEY &&
>> @@ -5000,6 +5004,24 @@ int check_fs_roots_lowmem(struct btrfs_fs_info *fs_info)
>>  			err |= ret;
>>  		}
>>  next:
>> +		/*
>> +		 * Since root tree can be cowed during repair,
>> +		 * here search the saved key again.
>> +		 */
>> +		if (repair) {
>> +			btrfs_release_path(&path);
>> +			ret = btrfs_search_slot(NULL, fs_info->tree_root,
>> +						&saved_key, &path, 0, 0);
>> +			/* Repair never deletes trees, search must succeed. */
>> +			if (ret > 0)
>> +				ret = -ENOENT;
>> +			if (ret) {
>> +				error(
>> +			"search root key[%llu %u %llu] failed after repair: %s",
>> +				      saved_key.objectid, saved_key.type,
>> +				      saved_key.offset, strerror(-ret));
>> +			}
>> +		}
>>  		ret = btrfs_next_item(tree_root, &path);
>>  		if (ret > 0)
>>  			goto out;
>>
> 

Re: [PATCH v3 5/7] btrfs-progs: lowmem: do missing check of last item after check_inode_item()

[Su Yue]

On 2018/9/17 8:53 PM, Qu Wenruo wrote:
> 
> 
> On 2018/9/17 下午3:28, Su Yue wrote:
>> After call of check_inode_item(), path may point to the last unchecked
>> slot of the leaf. The outer walk_up_tree() always treats the position
>> as checked slot then skips to the next. The last item will never be
>> checked.
>>
>> While checking backrefs, path passed to walk_up_tree() always
>> points to a checked slot.
>> While checking fs trees, path passed to walk_up_tree() always
>> points to an unchecked slot.
> 
> Can we unify this behavior?
> I has considered in three ways:
1) Change logical of the process_one_leaf. After it returns, path
points to the next slot checked.
To unify it, we can use saved key but will cost one search_slot time 
during serval nodes(>=1). Or call btrfs_previous_item() after every time 
check_inode_items() returns.

But why? why should we cost some time to swing the path. So I abandoned 1).

2) Change logical of the check_leaf_items(). What does the function
is just traverse all items then returns, which seems quite natural.
So I abandoned it.


3) It's what the patch does. The extra argument may seems strange,
I preferred to this way.

Maybe we can do something after check_leaf_items() returns, is it 
acceptable? I have no idea.

Thanks,
Su

> E.g, always points to an unchecked slot.
> 
> It would make things easier and no need for the extra parameter.
> 
> Thanks,
> Qu
> 
>>
>> Solution:
>> Add an argument @is_checked to walk_up_tree() to decide whether
>> to skip current slot.
>>
>> Fixes: 5e2dc770471b ("btrfs-progs: check: skip shared node or leaf check for low_memory mode")
>> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
>> ---
>>   check/mode-lowmem.c | 37 +++++++++++++++++++++++++++++++++----
>>   1 file changed, 33 insertions(+), 4 deletions(-)
>>
>> diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
>> index db44456fd85b..612e5e28e45b 100644
>> --- a/check/mode-lowmem.c
>> +++ b/check/mode-lowmem.c
>> @@ -4597,22 +4597,38 @@ static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
>>   	return err;
>>   }
>>   
>> +/*
>> + * Walk up throuh the path. Make path point to next slot to be checked.
>> + * walk_down_tree() should be called after this function.
>> + *
>> + * @root:	root of the tree
>> + * @path:	will point to next slot to check for walk_down_tree()
>> + * @level:	returns with level of next node to be checked
>> + * @is_checked:	means is the current node checked or not
>> + *		if false, the slot is unchecked, do not increase the slot
>> + *		if true, means increase the slot of the current node
>> + *
>> + * Returns 0 means success.
>> + * Returns >0 means the whole loop of walk up/down should be broken.
>> + */
>>   static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
>> -			int *level)
>> +			int *level, bool is_checked)
>>   {
>>   	int i;
>>   	struct extent_buffer *leaf;
>> +	int skip_cur =s_checked ? 1 : 0;
>>   
>>   	for (i =level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
>>   		leaf =ath->nodes[i];
>> -		if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
>> -			path->slots[i]++;
>> +		if (path->slots[i] + skip_cur < btrfs_header_nritems(leaf)) {
>> +			path->slots[i] +=kip_cur;
>>   			*level =;
>>   			return 0;
>>   		}
>>   		free_extent_buffer(path->nodes[*level]);
>>   		path->nodes[*level] =ULL;
>>   		*level = + 1;
>> +		skip_cur =;
>>   	}
>>   	return 1;
>>   }
>> @@ -4815,7 +4831,20 @@ static int check_btrfs_root(struct btrfs_root *root, int check_all)
>>   			break;
>>   		}
>>   
>> -		ret =alk_up_tree(root, &path, &level);
>> +		/*
>> +		 * The logical of walk trees are shared between backrefs
>> +		 * check and fs trees check.
>> +		 * In checking backrefs(check_all is true), after
>> +		 * check_leaf_items() returns, path points to
>> +		 * last checked item.
>> +		 * In checking fs roots(check_all is false), after
>> +		 * process_one_leaf() returns, path points to unchecked item.
>> +		 *
>> +		 * walk_up_tree() is reponsible to make path point to next
>> +		 * slot to be checked, above case is handled in
>> +		 * walk_up_tree().
>> +		 */
>> +		ret =alk_up_tree(root, &path, &level, check_all);
>>   		if (ret !=) {
>>   			/* Normal exit, reset ret to err */
>>   			ret =rr;
>>

Re: [PATCH v3 6/7] btrfs-progs: lowmem: optimization and repair for check_inode_extref()

[Nikolay Borisov]

On 17.09.2018 10:28, Su Yue wrote:
> inode_extref is much similar with inode_ref, most codes are reused in
> check_inode_extref().
> Exceptions:
> There is no need to check root directory, so remove it.
> Make check_inode_extref() verify hash value with key offset now.
> 
> And lowmem check can detect errors about inode_extref and try to
> repair errors.
> 
> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
> ---
>  check/mode-lowmem.c | 125 +++++++++++++++++++++++++++++++++++---------
>  1 file changed, 99 insertions(+), 26 deletions(-)
> 
> diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
> index 612e5e28e45b..53e4fdccd740 100644
> --- a/check/mode-lowmem.c
> +++ b/check/mode-lowmem.c
> @@ -1182,37 +1182,86 @@ out:
>   *
>   * 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)
> +static int check_inode_extref(struct btrfs_root *root, struct btrfs_key *ref_key,
> +			      struct btrfs_path *path, char *name_ret,
> +			      u32 *namelen_ret, u64 *refs_ret, int mode)
>  {
>  	struct btrfs_key key;
>  	struct btrfs_key location;
>  	struct btrfs_inode_extref *extref;
> +	struct extent_buffer *node;
>  	char namebuf[BTRFS_NAME_LEN] = {0};
>  	u32 total;
> -	u32 cur = 0;
> +	u32 cur;
>  	u32 len;
>  	u32 name_len;
>  	u64 index;
>  	u64 parent;
> +	int err;
> +	int tmp_err;
>  	int ret;
> -	int err = 0;
> +	int slot;
> +	u64 refs;
> +	bool search_again = false;
>  
>  	location.objectid = ref_key->objectid;
>  	location.type = BTRFS_INODE_ITEM_KEY;
>  	location.offset = 0;
> +begin:

Please don't implement loops with labels, instead use the appropriate
loop construct. Otherwise just factor out the repetitive code in a
function and call that in a loop. Labels should ideally be used only for
error cases to terminate the current function.

> +	cur = 0;
> +	err = 0;
> +	refs = *refs_ret;
> +	*namelen_ret = 0;
> +
> +	/* since after repair, path and the dir item may be changed */
> +	if (search_again) {
> +		search_again = false;
> +		btrfs_release_path(path);
> +		ret = btrfs_search_slot(NULL, root, ref_key, path, 0, 0);
> +		/*
> +		 * The item was deleted, let the path point to the last checked
> +		 * item.
> +		 */
> +		if (ret > 0) {
> +			if (path->slots[0] == 0) {
> +				ret = btrfs_prev_leaf(root, path);
> +				/*
> +				 * we are checking the inode item, there must
> +				 * be some items before, the case shall never
> +				 * happen.
> +				 */
> +				if (ret > 0)
> +					ret = -EIO;
> +				if (ret)
> +					error(
> +		"failed to get item before INODE_REF[%llu, %llu] root %llu: %s",
> +					      ref_key->objectid, ref_key->offset,
> +					      root->objectid, strerror(-ret));
> +			} else {
> +				path->slots[0]--;
> +				ret = 0;
> +			}
> +			goto out;
> +		} else if (ret < 0) {
> +			err |= FATAL_ERROR;
> +			goto out;
> +		}
> +	}
> +
> +	node = path->nodes[0];
> +	slot = path->slots[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);
> +loop:
> +	/* Update inode ref count */
> +	refs++;
> +	tmp_err = 0;
>  	parent = btrfs_inode_extref_parent(node, extref);
> +	index = btrfs_inode_extref_index(node, extref);
> +	name_len = btrfs_inode_extref_name_len(node, extref);
> +
>  	if (name_len <= BTRFS_NAME_LEN) {
>  		len = name_len;
>  	} else {
> @@ -1220,37 +1269,61 @@ next:
>  		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",
> +	/* verify hash value */
> +	if (ref_key->offset != btrfs_extref_hash(parent, namebuf, len)) {
> +		err |= FATAL_ERROR;
> +		error("root %llu INODE_EXTREF[%llu %llu] name %s namelen %u mode %d mismatch with its hash, wanted %llu have %llu",
>  		      root->objectid, ref_key->objectid, ref_key->offset,
> -		      namebuf);
> -		err |= ROOT_DIR_ERROR;
> +		      namebuf, len, mode, ref_key->offset,
> +		      btrfs_extref_hash(parent, namebuf, len));
> +		goto out;
> +	}
> +
> +	/* copy the first name found to name_ret */
> +	if (refs == 1 && name_ret) {
> +		memcpy(name_ret, namebuf, len);
> +		*namelen_ret = len;
>  	}
>  
> -	/* find related dir_index */
> +	/* Find related DIR_INDEX */
>  	key.objectid = parent;
>  	key.type = BTRFS_DIR_INDEX_KEY;
>  	key.offset = index;
> -	ret = find_dir_item(root, &key, &location, namebuf, len, mode);
> -	err |= ret;
> +	tmp_err |= find_dir_item(root, &key, &location, namebuf, len,
> +			    imode_to_type(mode));
>  
> -	/* find related dir_item */
> +	/* 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, &key, &location, namebuf, len, mode);
> -	err |= ret;
> +	tmp_err |= find_dir_item(root, &key, &location, namebuf, len,
> +			    imode_to_type(mode));
> +
> +	if (tmp_err && repair) {
> +		ret = repair_ternary_lowmem(root, parent, ref_key->objectid,
> +			    index, namebuf, name_len, imode_to_type(mode),
> +			    tmp_err);
> +		if (!ret) {
> +			search_again = true;
> +			goto begin;
> +		}
> +	}
>  
> +	print_inode_ref_err(root, ref_key, index, namebuf, name_len,
> +			    imode_to_type(mode), tmp_err);
> +
> +	err |= tmp_err;
>  	len = sizeof(*extref) + name_len;
>  	extref = (struct btrfs_inode_extref *)((char *)extref + len);
>  	cur += len;
>  
>  	if (cur < total)
> -		goto next;
> -
> +		goto loop;
> +out:
> +	*refs_ret = refs;
>  	return err;
>  }
>  
> @@ -2426,8 +2499,8 @@ static int check_inode_item(struct btrfs_root *root, struct btrfs_path *path)
>  				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);
> +			ret = check_inode_extref(root, &key, path, namebuf,
> +						 &name_len, &refs, mode);
>  			err |= ret;
>  			break;
>  		}
> 

Re: [PATCH v3 5/7] btrfs-progs: lowmem: do missing check of last item after check_inode_item()

[Qu Wenruo]

On 2018/9/17 下午9:24, Su Yue wrote:
> 
> 
> On 2018/9/17 8:53 PM, Qu Wenruo wrote:
>>
>>
>> On 2018/9/17 下午3:28, Su Yue wrote:
>>> After call of check_inode_item(), path may point to the last unchecked
>>> slot of the leaf. The outer walk_up_tree() always treats the position
>>> as checked slot then skips to the next. The last item will never be
>>> checked.
>>>
>>> While checking backrefs, path passed to walk_up_tree() always
>>> points to a checked slot.
>>> While checking fs trees, path passed to walk_up_tree() always
>>> points to an unchecked slot.
>>
>> Can we unify this behavior?
>> I has considered in three ways:
> 1) Change logical of the process_one_leaf. After it returns, path
> points to the next slot checked.
> To unify it, we can use saved key but will cost one search_slot time
> during serval nodes(>=1). Or call btrfs_previous_item() after every time
> check_inode_items() returns.
> 
> But why? why should we cost some time to swing the path. So I abandoned 1).
> 
> 2) Change logical of the check_leaf_items(). What does the function
> is just traverse all items then returns, which seems quite natural.
> So I abandoned it.

Well, this can also be interpreted as "it's a pretty good place to
change the behavior".

IMHO, since check_leaf_items() are just really simple hub functions, it
will just need a btrfs_next_item() in its out: tag.

By that we can unify the behavior of them to all points to the next
*unchecked* slot.
And no need for the extra parameter.

Thanks,
Qu

> 
> 
> 3) It's what the patch does. The extra argument may seems strange,
> I preferred to this way.
> 
> Maybe we can do something after check_leaf_items() returns, is it
> acceptable? I have no idea.
> 
> Thanks,
> Su
> 
>> E.g, always points to an unchecked slot.
>>
>> It would make things easier and no need for the extra parameter.
>>
>> Thanks,
>> Qu
>>
>>>
>>> Solution:
>>> Add an argument @is_checked to walk_up_tree() to decide whether
>>> to skip current slot.
>>>
>>> Fixes: 5e2dc770471b ("btrfs-progs: check: skip shared node or leaf
>>> check for low_memory mode")
>>> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
>>> ---
>>>   check/mode-lowmem.c | 37 +++++++++++++++++++++++++++++++++----
>>>   1 file changed, 33 insertions(+), 4 deletions(-)
>>>
>>> diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
>>> index db44456fd85b..612e5e28e45b 100644
>>> --- a/check/mode-lowmem.c
>>> +++ b/check/mode-lowmem.c
>>> @@ -4597,22 +4597,38 @@ static int walk_down_tree(struct btrfs_root
>>> *root, struct btrfs_path *path,
>>>       return err;
>>>   }
>>>   +/*
>>> + * Walk up throuh the path. Make path point to next slot to be checked.
>>> + * walk_down_tree() should be called after this function.
>>> + *
>>> + * @root:    root of the tree
>>> + * @path:    will point to next slot to check for walk_down_tree()
>>> + * @level:    returns with level of next node to be checked
>>> + * @is_checked:    means is the current node checked or not
>>> + *        if false, the slot is unchecked, do not increase the slot
>>> + *        if true, means increase the slot of the current node
>>> + *
>>> + * Returns 0 means success.
>>> + * Returns >0 means the whole loop of walk up/down should be broken.
>>> + */
>>>   static int walk_up_tree(struct btrfs_root *root, struct btrfs_path
>>> *path,
>>> -            int *level)
>>> +            int *level, bool is_checked)
>>>   {
>>>       int i;
>>>       struct extent_buffer *leaf;
>>> +    int skip_cur =s_checked ? 1 : 0;
>>>         for (i =level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
>>>           leaf =ath->nodes[i];
>>> -        if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
>>> -            path->slots[i]++;
>>> +        if (path->slots[i] + skip_cur < btrfs_header_nritems(leaf)) {
>>> +            path->slots[i] +=kip_cur;
>>>               *level =;
>>>               return 0;
>>>           }
>>>           free_extent_buffer(path->nodes[*level]);
>>>           path->nodes[*level] =ULL;
>>>           *level = + 1;
>>> +        skip_cur =;
>>>       }
>>>       return 1;
>>>   }
>>> @@ -4815,7 +4831,20 @@ static int check_btrfs_root(struct btrfs_root
>>> *root, int check_all)
>>>               break;
>>>           }
>>>   -        ret =alk_up_tree(root, &path, &level);
>>> +        /*
>>> +         * The logical of walk trees are shared between backrefs
>>> +         * check and fs trees check.
>>> +         * In checking backrefs(check_all is true), after
>>> +         * check_leaf_items() returns, path points to
>>> +         * last checked item.
>>> +         * In checking fs roots(check_all is false), after
>>> +         * process_one_leaf() returns, path points to unchecked item.
>>> +         *
>>> +         * walk_up_tree() is reponsible to make path point to next
>>> +         * slot to be checked, above case is handled in
>>> +         * walk_up_tree().
>>> +         */
>>> +        ret =alk_up_tree(root, &path, &level, check_all);
>>>           if (ret !=) {
>>>               /* Normal exit, reset ret to err */
>>>               ret =rr;
>>>

Re: [PATCH v3 5/7] btrfs-progs: lowmem: do missing check of last item after check_inode_item()

[Su Yue]

On 9/18/18 1:32 PM, Qu Wenruo wrote:
> 
> 
> On 2018/9/17 下午9:24, Su Yue wrote:
>>
>>
>> On 2018/9/17 8:53 PM, Qu Wenruo wrote:
>>>
>>>
>>> On 2018/9/17 下午3:28, Su Yue wrote:
>>>> After call of check_inode_item(), path may point to the last unchecked
>>>> slot of the leaf. The outer walk_up_tree() always treats the position
>>>> as checked slot then skips to the next. The last item will never be
>>>> checked.
>>>>
>>>> While checking backrefs, path passed to walk_up_tree() always
>>>> points to a checked slot.
>>>> While checking fs trees, path passed to walk_up_tree() always
>>>> points to an unchecked slot.
>>>
>>> Can we unify this behavior?
>>> I has considered in three ways:
>> 1) Change logical of the process_one_leaf. After it returns, path
>> points to the next slot checked.
>> To unify it, we can use saved key but will cost one search_slot time
>> during serval nodes(>=1). Or call btrfs_previous_item() after every time
>> check_inode_items() returns.
>>
>> But why? why should we cost some time to swing the path. So I abandoned 1).
>>
>> 2) Change logical of the check_leaf_items(). What does the function
>> is just traverse all items then returns, which seems quite natural.
>> So I abandoned it.
> 
> Well, this can also be interpreted as "it's a pretty good place to
> change the behavior".
> 
> IMHO, since check_leaf_items() are just really simple hub functions, it
> will just need a btrfs_next_item() in its out: tag.
> 
After sometime thinking, sorry, the idea should not work as expected.
In fact, backrefs check and fs check walk a little differently.

Backrefs check always do walk nodes one by one, never skip any nodes.
Fs check will try to skip shared nodes to speed up.

While checking backrefs with your idea,
If the tree has many levels.
Assume before calling btrfs_next_item:
path->slots[0] points to the one past of the last item.
path->slots[1] points to the last slot of nodes[1].
path->slots[2] points to the last slot of nodes[2].
path->slots[3] points to the one *before* last slot of nodes[3].

After btrfs_next_item():
path->slots[0] points to the first item of another leaf.
path->slots[1] points to the first item of another node.
path->slots[2] points to the first item of another node.
path->slots[3] points to the a slot of *old* nodes[3].

Then walk_up_tree() is in, it thinks the slot is unchecked then
returns with *level=0. Then walk_down_tree() just walk from level
to leaf.
Backrefs of new nodes[1,2] will never be checked, the most
obvious negative effect is inaccurate account info.
Although we can do check is slot the first in walk_up_tree(),
it's a magic and worse than this patch.

Thanks,
Su

> By that we can unify the behavior of them to all points to the next
> *unchecked* slot.
> And no need for the extra parameter.
> 
> Thanks,
> Qu
> 
>>
>>
>> 3) It's what the patch does. The extra argument may seems strange,
>> I preferred to this way.
>>
>> Maybe we can do something after check_leaf_items() returns, is it
>> acceptable? I have no idea.
>>
>> Thanks,
>> Su
>>
>>> E.g, always points to an unchecked slot.
>>>
>>> It would make things easier and no need for the extra parameter.
>>>
>>> Thanks,
>>> Qu
>>>
>>>>
>>>> Solution:
>>>> Add an argument @is_checked to walk_up_tree() to decide whether
>>>> to skip current slot.
>>>>
>>>> Fixes: 5e2dc770471b ("btrfs-progs: check: skip shared node or leaf
>>>> check for low_memory mode")
>>>> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
>>>> ---
>>>>    check/mode-lowmem.c | 37 +++++++++++++++++++++++++++++++++----
>>>>    1 file changed, 33 insertions(+), 4 deletions(-)
>>>>
>>>> diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
>>>> index db44456fd85b..612e5e28e45b 100644
>>>> --- a/check/mode-lowmem.c
>>>> +++ b/check/mode-lowmem.c
>>>> @@ -4597,22 +4597,38 @@ static int walk_down_tree(struct btrfs_root
>>>> *root, struct btrfs_path *path,
>>>>        return err;
>>>>    }
>>>>    +/*
>>>> + * Walk up throuh the path. Make path point to next slot to be checked.
>>>> + * walk_down_tree() should be called after this function.
>>>> + *
>>>> + * @root:    root of the tree
>>>> + * @path:    will point to next slot to check for walk_down_tree()
>>>> + * @level:    returns with level of next node to be checked
>>>> + * @is_checked:    means is the current node checked or not
>>>> + *        if false, the slot is unchecked, do not increase the slot
>>>> + *        if true, means increase the slot of the current node
>>>> + *
>>>> + * Returns 0 means success.
>>>> + * Returns >0 means the whole loop of walk up/down should be broken.
>>>> + */
>>>>    static int walk_up_tree(struct btrfs_root *root, struct btrfs_path
>>>> *path,
>>>> -            int *level)
>>>> +            int *level, bool is_checked)
>>>>    {
>>>>        int i;
>>>>        struct extent_buffer *leaf;
>>>> +    int skip_cur =s_checked ? 1 : 0;
>>>>          for (i =level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
>>>>            leaf =ath->nodes[i];
>>>> -        if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
>>>> -            path->slots[i]++;
>>>> +        if (path->slots[i] + skip_cur < btrfs_header_nritems(leaf)) {
>>>> +            path->slots[i] +=kip_cur;
>>>>                *level =;
>>>>                return 0;
>>>>            }
>>>>            free_extent_buffer(path->nodes[*level]);
>>>>            path->nodes[*level] =ULL;
>>>>            *level = + 1;
>>>> +        skip_cur =;
>>>>        }
>>>>        return 1;
>>>>    }
>>>> @@ -4815,7 +4831,20 @@ static int check_btrfs_root(struct btrfs_root
>>>> *root, int check_all)
>>>>                break;
>>>>            }
>>>>    -        ret =alk_up_tree(root, &path, &level);
>>>> +        /*
>>>> +         * The logical of walk trees are shared between backrefs
>>>> +         * check and fs trees check.
>>>> +         * In checking backrefs(check_all is true), after
>>>> +         * check_leaf_items() returns, path points to
>>>> +         * last checked item.
>>>> +         * In checking fs roots(check_all is false), after
>>>> +         * process_one_leaf() returns, path points to unchecked item.
>>>> +         *
>>>> +         * walk_up_tree() is reponsible to make path point to next
>>>> +         * slot to be checked, above case is handled in
>>>> +         * walk_up_tree().
>>>> +         */
>>>> +        ret =alk_up_tree(root, &path, &level, check_all);
>>>>            if (ret !=) {
>>>>                /* Normal exit, reset ret to err */
>>>>                ret =rr;
>>>>
> 
> 

Re: [PATCH v3 5/7] btrfs-progs: lowmem: do missing check of last item after check_inode_item()

[Qu Wenruo]

On 2018/9/18 下午4:01, Su Yue wrote:
> 
> 
> On 9/18/18 1:32 PM, Qu Wenruo wrote:
>>
>>
>> On 2018/9/17 下午9:24, Su Yue wrote:
>>>
>>>
>>> On 2018/9/17 8:53 PM, Qu Wenruo wrote:
>>>>
>>>>
>>>> On 2018/9/17 下午3:28, Su Yue wrote:
>>>>> After call of check_inode_item(), path may point to the last unchecked
>>>>> slot of the leaf. The outer walk_up_tree() always treats the position
>>>>> as checked slot then skips to the next. The last item will never be
>>>>> checked.
>>>>>
>>>>> While checking backrefs, path passed to walk_up_tree() always
>>>>> points to a checked slot.
>>>>> While checking fs trees, path passed to walk_up_tree() always
>>>>> points to an unchecked slot.
>>>>
>>>> Can we unify this behavior?
>>>> I has considered in three ways:
>>> 1) Change logical of the process_one_leaf. After it returns, path
>>> points to the next slot checked.
>>> To unify it, we can use saved key but will cost one search_slot time
>>> during serval nodes(>=1). Or call btrfs_previous_item() after every time
>>> check_inode_items() returns.
>>>
>>> But why? why should we cost some time to swing the path. So I
>>> abandoned 1).
>>>
>>> 2) Change logical of the check_leaf_items(). What does the function
>>> is just traverse all items then returns, which seems quite natural.
>>> So I abandoned it.
>>
>> Well, this can also be interpreted as "it's a pretty good place to
>> change the behavior".
>>
>> IMHO, since check_leaf_items() are just really simple hub functions, it
>> will just need a btrfs_next_item() in its out: tag.
>>
> After sometime thinking, sorry, the idea should not work as expected.
> In fact, backrefs check and fs check walk a little differently.

Just as discussed offline, unfortunately that's the case.

> 
> Backrefs check always do walk nodes one by one, never skip any nodes.
> Fs check will try to skip shared nodes to speed up
Exactly.

> 
> While checking backrefs with your idea,
> If the tree has many levels.
> Assume before calling btrfs_next_item:
> path->slots[0] points to the one past of the last item.
> path->slots[1] points to the last slot of nodes[1].
> path->slots[2] points to the last slot of nodes[2].
> path->slots[3] points to the one *before* last slot of nodes[3].
> 
> After btrfs_next_item():
> path->slots[0] points to the first item of another leaf.
> path->slots[1] points to the first item of another node.
> path->slots[2] points to the first item of another node.
> path->slots[3] points to the a slot of *old* nodes[3].

These info is pretty useful, please consider include them in next version.

It's not that obvious from the code.

And now your patch makes sense.

Thanks,
Qu

> 
> Then walk_up_tree() is in, it thinks the slot is unchecked then
> returns with *level=0. Then walk_down_tree() just walk from level
> to leaf.
> Backrefs of new nodes[1,2] will never be checked, the most
> obvious negative effect is inaccurate account info.
> Although we can do check is slot the first in walk_up_tree(),
> it's a magic and worse than this patch.
> 
> Thanks,
> Su
> 
>> By that we can unify the behavior of them to all points to the next
>> *unchecked* slot.
>> And no need for the extra parameter.
>>
>> Thanks,
>> Qu
>>
>>>
>>>
>>> 3) It's what the patch does. The extra argument may seems strange,
>>> I preferred to this way.
>>>
>>> Maybe we can do something after check_leaf_items() returns, is it
>>> acceptable? I have no idea.
>>>
>>> Thanks,
>>> Su
>>>
>>>> E.g, always points to an unchecked slot.
>>>>
>>>> It would make things easier and no need for the extra parameter.
>>>>
>>>> Thanks,
>>>> Qu
>>>>
>>>>>
>>>>> Solution:
>>>>> Add an argument @is_checked to walk_up_tree() to decide whether
>>>>> to skip current slot.
>>>>>
>>>>> Fixes: 5e2dc770471b ("btrfs-progs: check: skip shared node or leaf
>>>>> check for low_memory mode")
>>>>> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
>>>>> ---
>>>>>    check/mode-lowmem.c | 37 +++++++++++++++++++++++++++++++++----
>>>>>    1 file changed, 33 insertions(+), 4 deletions(-)
>>>>>
>>>>> diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
>>>>> index db44456fd85b..612e5e28e45b 100644
>>>>> --- a/check/mode-lowmem.c
>>>>> +++ b/check/mode-lowmem.c
>>>>> @@ -4597,22 +4597,38 @@ static int walk_down_tree(struct btrfs_root
>>>>> *root, struct btrfs_path *path,
>>>>>        return err;
>>>>>    }
>>>>>    +/*
>>>>> + * Walk up throuh the path. Make path point to next slot to be
>>>>> checked.
>>>>> + * walk_down_tree() should be called after this function.
>>>>> + *
>>>>> + * @root:    root of the tree
>>>>> + * @path:    will point to next slot to check for walk_down_tree()
>>>>> + * @level:    returns with level of next node to be checked
>>>>> + * @is_checked:    means is the current node checked or not
>>>>> + *        if false, the slot is unchecked, do not increase the slot
>>>>> + *        if true, means increase the slot of the current node
>>>>> + *
>>>>> + * Returns 0 means success.
>>>>> + * Returns >0 means the whole loop of walk up/down should be broken.
>>>>> + */
>>>>>    static int walk_up_tree(struct btrfs_root *root, struct btrfs_path
>>>>> *path,
>>>>> -            int *level)
>>>>> +            int *level, bool is_checked)
>>>>>    {
>>>>>        int i;
>>>>>        struct extent_buffer *leaf;
>>>>> +    int skip_cur =s_checked ? 1 : 0;
>>>>>          for (i =level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i];
>>>>> i++) {
>>>>>            leaf =ath->nodes[i];
>>>>> -        if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
>>>>> -            path->slots[i]++;
>>>>> +        if (path->slots[i] + skip_cur < btrfs_header_nritems(leaf)) {
>>>>> +            path->slots[i] +=kip_cur;
>>>>>                *level =;
>>>>>                return 0;
>>>>>            }
>>>>>            free_extent_buffer(path->nodes[*level]);
>>>>>            path->nodes[*level] =ULL;
>>>>>            *level = + 1;
>>>>> +        skip_cur =;
>>>>>        }
>>>>>        return 1;
>>>>>    }
>>>>> @@ -4815,7 +4831,20 @@ static int check_btrfs_root(struct btrfs_root
>>>>> *root, int check_all)
>>>>>                break;
>>>>>            }
>>>>>    -        ret =alk_up_tree(root, &path, &level);
>>>>> +        /*
>>>>> +         * The logical of walk trees are shared between backrefs
>>>>> +         * check and fs trees check.
>>>>> +         * In checking backrefs(check_all is true), after
>>>>> +         * check_leaf_items() returns, path points to
>>>>> +         * last checked item.
>>>>> +         * In checking fs roots(check_all is false), after
>>>>> +         * process_one_leaf() returns, path points to unchecked item.
>>>>> +         *
>>>>> +         * walk_up_tree() is reponsible to make path point to next
>>>>> +         * slot to be checked, above case is handled in
>>>>> +         * walk_up_tree().
>>>>> +         */
>>>>> +        ret =alk_up_tree(root, &path, &level, check_all);
>>>>>            if (ret !=) {
>>>>>                /* Normal exit, reset ret to err */
>>>>>                ret =rr;
>>>>>
>>
>>
> 
>