[PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and

[PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and

[Qu Wenruo]

The patchset introduce two new repair function and some helpers to
archive a huge goal:
  Repair btrfs whose fs tree's non-root leaf/node is corrupted when no
  duplication is valid.

The two new repair functions are:
  repair_inode_nlinks():
    Repair any inode nlink related problem.
    From fixing the nlink number and related
    inode_ref/dir_index/dir_item to recovering file name and file type
    and salvage them into the lost+found dir.
    This does not only fix a case that some users reported but also
    cooperate with repair_inode_no_item() function to salvaged heavily
    damaged inode to lost+found dir.

  repair_inode_no_item():
    Repair case for inode_item missing case, which is quite common when
    fs tree leaf/node is missing.
    This only does the inode item rebuild. Later recovery like move it
    to lost+found dir is done by repair_inode_nlinks().

The main helper is the repair_btree() function, which will drops the
corrupted non-root leaf/node and rebalance the tree to keep the
correctness of the btree.

With this patchset, even a non-root leaf/node is corrupted and no
duplication survived, btrfsck can still repair it to a mountable status.
(And normal rw should also be OK,)

The remaining unfixable problems will be inode nbytes error with file
extent discounts error, which may be fixed in next patchset.

Cc David:
Sorry for the huge change in the patchset and merge the old inode nlink
repair with new inode item rebuild patchset.

Since when developing inode item rebuild patchset, I found the old nlink
cooperated very bad with item rebuild and there is some duplicated codes
between the two patchset, no to mention the math lib introduced by nlink
repair patch.
So I decided to somewhat rebase the nlink repair patchset to provide
better generality.

Sorry again for taking your extra time rebasing the patch.

Qu Wenruo (13):
  btrfs-progs: print root dir verbose error in fsck
  btrfs-progs: Import btrfs_insert/del/lookup_extref() functions.
  btrfs-progs: Import lookup/del_inode_ref() function.
  btrfs-progs: Add last_cache_extent() for extent-cache.
  btrfs-progs: Record highest inode number before repair.
  btrfs-progs: Add btrfs_unlink() and btrfs_add_link() functions.
  btrfs-progs: Add btrfs_mkdir() function for the incoming 'lost+found' 
       fsck mechanism.
  btrfs-progs: Add count_digit() function to help calculate filename
    len.
  btrfs-progs: Add helper function find_file_name/type for nlink and    
    inode_item repair.
  btrfs-progs: Add fixing function for inodes whose nlink dismatch
  btrfs-progs: record and report leaf/node corruption in fs/subvol tree
  btrfs-progs: Recover btree by dropping corrupted leaf/node.
  btrfs-progs: Add inode item rebuild function.

 Makefile       |   2 +-
 cmds-check.c   | 579 ++++++++++++++++++++++++++++++++++++++++++++++++++++++---
 ctree.c        |   6 +
 ctree.h        |  44 +++++
 extent-cache.c |   9 +
 extent-cache.h |   1 +
 inode-item.c   | 318 +++++++++++++++++++++++++++++++
 inode.c        | 540 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 utils.h        |  18 ++
 9 files changed, 1493 insertions(+), 24 deletions(-)
 create mode 100644 inode.c

-- 
2.1.3

[PATCH v4 01/13] btrfs-progs: print root dir verbose error in fsck

[Qu Wenruo]

Before this patch, when btrfsck found an error in root dir, it will only
output the following message "root %llu root dir %llu error" without any
detailed error.

Just add print_inode_error() to print out the whole error.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
Changelog:
v2~v4:
   No change.
---
 cmds-check.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/cmds-check.c b/cmds-check.c
index 389674f..9fc1410 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -1984,6 +1984,7 @@ static int check_inode_recs(struct btrfs_root *root,
 			fprintf(stderr, "root %llu root dir %llu error\n",
 				(unsigned long long)root->root_key.objectid,
 				(unsigned long long)root_dirid);
+			print_inode_error(root, rec);
 			error++;
 		}
 	} else {
-- 
2.1.3

[PATCH v4 02/13] btrfs-progs: Import btrfs_insert/del/lookup_extref() functions.

[Qu Wenruo]

Import btrfs_insert/del/lookup_extref() functions form kernel for the
incoming btrfs_add_link() and btrfs_unlink() functions.

As the base of incoming btrfs 'lost+found' recovery mechanism.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
Changelog:
v2~v4:
   No change.
---
 ctree.h      |  14 ++++
 inode-item.c | 206 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 220 insertions(+)

diff --git a/ctree.h b/ctree.h
index 89036de..e185e7a 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2389,6 +2389,20 @@ 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);
+int btrfs_del_inode_extref(struct btrfs_trans_handle *trans,
+			   struct btrfs_root *root,
+			   const char *name, int name_len,
+			   u64 inode_objectid, u64 ref_objectid,
+			   u64 *index);
+int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans,
+			      struct btrfs_root *root,
+			      const char *name, int name_len,
+			      u64 inode_objectid, u64 ref_objectid, u64 index);
 
 /* file-item.c */
 int btrfs_del_csums(struct btrfs_trans_handle *trans,
diff --git a/inode-item.c b/inode-item.c
index 8cc98c6..7337ac9 100644
--- a/inode-item.c
+++ b/inode-item.c
@@ -19,6 +19,7 @@
 #include "ctree.h"
 #include "disk-io.h"
 #include "transaction.h"
+#include "crc32c.h"
 
 static int find_name_in_backref(struct btrfs_path *path, const char * name,
 			 int name_len, struct btrfs_inode_ref **ref_ret)
@@ -145,3 +146,208 @@ int btrfs_insert_inode(struct btrfs_trans_handle *trans, struct btrfs_root
 				sizeof(*inode_item));
 	return ret;
 }
+
+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)
+{
+	struct extent_buffer *node;
+	struct btrfs_inode_extref *extref;
+	unsigned long ptr;
+	unsigned long name_ptr;
+	u32 item_size;
+	u32 cur_offset = 0;
+	int ref_name_len;
+	int slot;
+
+	node = path->nodes[0];
+	slot = path->slots[0];
+	item_size = btrfs_item_size_nr(node, slot);
+	ptr = btrfs_item_ptr_offset(node, slot);
+
+	/*
+	 * Search all extended backrefs in this item. We're only
+	 * looking through any collisions so most of the time this is
+	 * just going to compare against one buffer. If all is well,
+	 * we'll return success and the inode ref object.
+	 */
+	while (cur_offset < item_size) {
+		extref = (struct btrfs_inode_extref *) (ptr + cur_offset);
+		name_ptr = (unsigned long)(&extref->name);
+		ref_name_len = btrfs_inode_extref_name_len(node, extref);
+
+		if (ref_name_len == namelen &&
+		    btrfs_inode_extref_parent(node, extref) == parent_ino &&
+		    (memcmp_extent_buffer(node, name, name_ptr,
+					  namelen) == 0)) {
+			if (extref_ret)
+				*extref_ret = extref;
+			return 1;
+		}
+
+		cur_offset += ref_name_len + sizeof(*extref);
+	}
+	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_key key;
+	struct btrfs_inode_extref *extref;
+	int ret = 0;
+
+	key.objectid = ino;
+	key.type = BTRFS_INODE_EXTREF_KEY;
+	key.offset = btrfs_extref_hash(parent_ino, name, namelen);
+
+	ret = btrfs_search_slot(trans, root, &key, path, ins_len,
+				ins_len ? 1 : 0);
+	if (ret < 0)
+		return ERR_PTR(ret);
+	if (ret > 0)
+		return NULL;
+	if (!btrfs_find_name_in_ext_backref(path, parent_ino, name,
+					    namelen, &extref))
+		return NULL;
+	return extref;
+}
+
+int btrfs_del_inode_extref(struct btrfs_trans_handle *trans,
+			   struct btrfs_root *root,
+			   const char *name, int name_len,
+			   u64 inode_objectid, u64 ref_objectid,
+			   u64 *index)
+{
+	struct btrfs_path *path;
+	struct btrfs_key key;
+	struct btrfs_inode_extref *extref;
+	struct extent_buffer *leaf;
+	int ret;
+	int del_len = name_len + sizeof(*extref);
+	unsigned long ptr;
+	unsigned long item_start;
+	u32 item_size;
+
+	key.objectid = inode_objectid;
+	key.type = BTRFS_INODE_EXTREF_KEY;
+	key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
+	if (ret > 0)
+		ret = -ENOENT;
+	if (ret < 0)
+		goto out;
+
+	/*
+	 * Sanity check - did we find the right item for this name?
+	 * This should always succeed so error here will make the FS
+	 * readonly.
+	 */
+	if (!btrfs_find_name_in_ext_backref(path, ref_objectid,
+					    name, name_len, &extref)) {
+		ret = -ENOENT;
+		goto out;
+	}
+
+	leaf = path->nodes[0];
+	item_size = btrfs_item_size_nr(leaf, path->slots[0]);
+	if (index)
+		*index = btrfs_inode_extref_index(leaf, extref);
+
+	if (del_len == item_size) {
+		/*
+		 * Common case only one ref in the item, remove the
+		 * whole item.
+		 */
+		ret = btrfs_del_item(trans, root, path);
+		goto out;
+	}
+
+	ptr = (unsigned long)extref;
+	item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
+
+	memmove_extent_buffer(leaf, ptr, ptr + del_len,
+			      item_size - (ptr + del_len - item_start));
+
+	btrfs_truncate_item(trans, root, path, item_size - del_len, 1);
+
+out:
+	btrfs_free_path(path);
+
+	return ret;
+}
+
+/*
+ * btrfs_insert_inode_extref() - Inserts an extended inode ref into a tree.
+ *
+ * The caller must have checked against BTRFS_LINK_MAX already.
+ */
+int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans,
+			      struct btrfs_root *root,
+			      const char *name, int name_len,
+			      u64 inode_objectid, u64 ref_objectid, u64 index)
+{
+	struct btrfs_inode_extref *extref;
+	int ret;
+	int ins_len = name_len + sizeof(*extref);
+	unsigned long ptr;
+	struct btrfs_path *path;
+	struct btrfs_key key;
+	struct extent_buffer *leaf;
+	struct btrfs_item *item;
+
+	key.objectid = inode_objectid;
+	key.type = BTRFS_INODE_EXTREF_KEY;
+	key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	ret = btrfs_insert_empty_item(trans, root, path, &key,
+				      ins_len);
+	if (ret == -EEXIST) {
+		if (btrfs_find_name_in_ext_backref(path, ref_objectid,
+						   name, name_len, NULL))
+			goto out;
+
+		btrfs_extend_item(trans, root, path, ins_len);
+		ret = 0;
+	}
+	if (ret < 0)
+		goto out;
+
+	leaf = path->nodes[0];
+	item = btrfs_item_nr(path->slots[0]);
+	ptr = (unsigned long)btrfs_item_ptr(leaf, path->slots[0], char);
+	ptr += btrfs_item_size(leaf, item) - ins_len;
+	extref = (struct btrfs_inode_extref *)ptr;
+
+	btrfs_set_inode_extref_name_len(path->nodes[0], extref, name_len);
+	btrfs_set_inode_extref_index(path->nodes[0], extref, index);
+	btrfs_set_inode_extref_parent(path->nodes[0], extref, ref_objectid);
+
+	ptr = (unsigned long)&extref->name;
+	write_extent_buffer(path->nodes[0], name, ptr, name_len);
+	btrfs_mark_buffer_dirty(path->nodes[0]);
+
+out:
+	btrfs_free_path(path);
+	return ret;
+}
-- 
2.1.3

[PATCH v4 03/13] btrfs-progs: Import lookup/del_inode_ref() function.

[Qu Wenruo]

Import lookup/del_inode_ref() function in inode-item.c, as base functions
for the incoming btrfs_add_link() and btrfs_unlink() functions.

Also modify btrfs_insert_inode_ref() and split_leaf() making them able
to deal with EXTENT_IREF incompat flag.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
Changelog:
v2~v4:
   No Change.
---
 ctree.c      |   6 ++++
 ctree.h      |  10 ++++++
 inode-item.c | 112 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 128 insertions(+)

diff --git a/ctree.c b/ctree.c
index 23399e2..bd6cb12 100644
--- a/ctree.c
+++ b/ctree.c
@@ -2015,6 +2015,12 @@ static noinline int split_leaf(struct btrfs_trans_handle *trans,
 	int split;
 	int num_doubles = 0;
 
+	l = path->nodes[0];
+	slot = path->slots[0];
+	if (extend && data_size + btrfs_item_size_nr(l, slot) +
+	    sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(root))
+		return -EOVERFLOW;
+
 	/* first try to make some room by pushing left and right */
 	if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) {
 		wret = push_leaf_right(trans, root, path, data_size, 0);
diff --git a/ctree.h b/ctree.h
index e185e7a..32b1286 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2403,6 +2403,16 @@ int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans,
 			      struct btrfs_root *root,
 			      const char *name, int name_len,
 			      u64 inode_objectid, u64 ref_objectid, u64 index);
+struct btrfs_inode_ref
+*btrfs_lookup_inode_ref(struct btrfs_trans_handle *trans,
+			struct btrfs_root *root,
+			struct btrfs_path *path,
+			const char *name, int namelen,
+			u64 ino, u64 parent_ino, u64 index, int ins_len);
+int btrfs_del_inode_ref(struct btrfs_trans_handle *trans,
+			struct btrfs_root *root,
+			const char *name, int name_len,
+			u64 ino, u64 parent_ino, u64 *index);
 
 /* file-item.c */
 int btrfs_del_csums(struct btrfs_trans_handle *trans,
diff --git a/inode-item.c b/inode-item.c
index 7337ac9..5a9b675 100644
--- a/inode-item.c
+++ b/inode-item.c
@@ -89,6 +89,8 @@ int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans,
 		ptr = (unsigned long)(ref + 1);
 		ret = 0;
 	} else if (ret < 0) {
+		if (ret == EOVERFLOW)
+			ret = -EMLINK;
 		goto out;
 	} else {
 		ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
@@ -102,6 +104,15 @@ int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans,
 
 out:
 	btrfs_free_path(path);
+
+	if (ret == -EMLINK) {
+		if (btrfs_fs_incompat(root->fs_info,
+				      BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF))
+			ret = btrfs_insert_inode_extref(trans, root, name,
+							name_len,
+							inode_objectid,
+							ref_objectid, index);
+	}
 	return ret;
 }
 
@@ -147,6 +158,34 @@ int btrfs_insert_inode(struct btrfs_trans_handle *trans, struct btrfs_root
 	return ret;
 }
 
+struct btrfs_inode_ref
+*btrfs_lookup_inode_ref(struct btrfs_trans_handle *trans,
+			struct btrfs_root *root,
+			struct btrfs_path *path,
+			const char *name, int namelen,
+			u64 ino, u64 parent_ino, u64 index, int ins_len)
+{
+	struct btrfs_key key;
+	struct btrfs_inode_ref *ret_inode_ref = NULL;
+	int ret = 0;
+
+	key.objectid = ino;
+	key.type = BTRFS_INODE_REF_KEY;
+	key.offset = parent_ino;
+
+	ret = btrfs_search_slot(trans, root, &key, path, ins_len,
+				ins_len ? 1 : 0);
+	if (ret)
+		goto out;
+
+	find_name_in_backref(path, name, namelen, &ret_inode_ref);
+out:
+	if (ret < 0)
+		return ERR_PTR(ret);
+	else
+		return ret_inode_ref;
+}
+
 static inline u64 btrfs_extref_hash(u64 parent_ino, const char *name,
 				    int namelen)
 {
@@ -351,3 +390,76 @@ out:
 	btrfs_free_path(path);
 	return ret;
 }
+
+int btrfs_del_inode_ref(struct btrfs_trans_handle *trans,
+			struct btrfs_root *root,
+			const char *name, int name_len,
+			u64 ino, u64 parent_ino, u64 *index)
+{
+	struct btrfs_path *path;
+	struct btrfs_key key;
+	struct btrfs_inode_ref *ref;
+	struct extent_buffer *leaf;
+	unsigned long ptr;
+	unsigned long item_start;
+	u32 item_size;
+	u32 sub_item_len;
+	int ret;
+	int search_ext_refs = 0;
+	int del_len = name_len + sizeof(*ref);
+
+	key.objectid = ino;
+	key.offset = parent_ino;
+	key.type = BTRFS_INODE_REF_KEY;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
+	if (ret > 0) {
+		ret = -ENOENT;
+		search_ext_refs = 1;
+		goto out;
+	} else if (ret < 0) {
+		goto out;
+	}
+	if (!find_name_in_backref(path, name, name_len, &ref)) {
+		ret = -ENOENT;
+		search_ext_refs = 1;
+		goto out;
+	}
+	leaf = path->nodes[0];
+	item_size = btrfs_item_size_nr(leaf, path->slots[0]);
+
+	if (index)
+		*index = btrfs_inode_ref_index(leaf, ref);
+
+	if (del_len == item_size) {
+		ret = btrfs_del_item(trans, root, path);
+		goto out;
+	}
+	ptr = (unsigned long)ref;
+	sub_item_len = name_len + sizeof(*ref);
+	item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
+	memmove_extent_buffer(leaf, ptr, ptr + sub_item_len,
+			      item_size - (ptr + sub_item_len - item_start));
+	btrfs_truncate_item(trans, root, path, item_size - sub_item_len, 1);
+	btrfs_mark_buffer_dirty(path->nodes[0]);
+out:
+	btrfs_free_path(path);
+
+	if (search_ext_refs &&
+	    btrfs_fs_incompat(root->fs_info,
+		    BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF)) {
+		/*
+		 * No refs were found, or we could not find the
+		 * name in our ref array. Find and remove the extended
+		 * inode ref then.
+		 */
+		return btrfs_del_inode_extref(trans, root, name, name_len,
+					      ino, parent_ino, index);
+	}
+
+	return ret;
+}
-- 
2.1.3

[PATCH v4 04/13] btrfs-progs: Add last_cache_extent() for extent-cache.

[Qu Wenruo]

Allow direct search for the last cache extent.
Provide the basis for finding the last ino in inode_cache.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
Changelog:
v4:
   Newly introduced.
---
 extent-cache.c | 9 +++++++++
 extent-cache.h | 1 +
 2 files changed, 10 insertions(+)

diff --git a/extent-cache.c b/extent-cache.c
index 7656ab2..d80aead 100644
--- a/extent-cache.c
+++ b/extent-cache.c
@@ -230,6 +230,15 @@ struct cache_extent *first_cache_extent(struct cache_tree *tree)
 	return rb_entry(node, struct cache_extent, rb_node);
 }
 
+struct cache_extent *last_cache_extent(struct cache_tree *tree)
+{
+	struct rb_node *node = rb_last(&tree->root);
+
+	if (!node)
+		return NULL;
+	return rb_entry(node, struct cache_extent, rb_node);
+}
+
 struct cache_extent *prev_cache_extent(struct cache_extent *pe)
 {
 	struct rb_node *node = rb_prev(&pe->rb_node);
diff --git a/extent-cache.h b/extent-cache.h
index cba83d1..a9d07e1 100644
--- a/extent-cache.h
+++ b/extent-cache.h
@@ -41,6 +41,7 @@ struct cache_extent {
 void cache_tree_init(struct cache_tree *tree);
 
 struct cache_extent *first_cache_extent(struct cache_tree *tree);
+struct cache_extent *last_cache_extent(struct cache_tree *tree);
 struct cache_extent *prev_cache_extent(struct cache_extent *pe);
 struct cache_extent *next_cache_extent(struct cache_extent *pe);
 
-- 
2.1.3

[PATCH v4 05/13] btrfs-progs: Record highest inode number before repair.

[Qu Wenruo]

Record highest inode number before inode repair.

This is especially important for corrupted leaf case.
Under that case, if use btrfs_find_free_objectid, it may find a ino
existing in corrupted leaf but dropped by btree_recover.
If that happens, created dir will be referenced incorrectly since there
may be inode_ref or dir_index/item refers to it.

So we must record the highest inode number according to the inode_cache.
Inode_cache is OK since when a inode_ref or dir_index/item is found even
the referenced source is not found, it will be created.
If we record the highest inode number of inode_cache, and use
highest_inode + 1 as 'lost+found' dir, it will ensure the newly created
dir not conflicting with any possible inode.

This provides the basis for nlink or inode rebuild for repairing btrfs
with leaf/node corruption.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
Changelog:
v4:
   Newly introduced.
---
 cmds-check.c | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 9fc1410..1f35cc2 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -1927,6 +1927,21 @@ static int check_inode_recs(struct btrfs_root *root,
 	}
 
 	/*
+	 * We need to record the highest inode number for later 'lost+found'
+	 * dir creation.
+	 * We must select a ino not used/refered by any existing inode, or
+	 * 'lost+found' ino may be a missing ino in a corrupted leaf,
+	 * this may cause 'lost+found' dir has wrong nlinks.
+	 */
+	cache = last_cache_extent(inode_cache);
+	if (cache) {
+		node = container_of(cache, struct ptr_node, cache);
+		rec = node->data;
+		if (rec->ino > root->highest_inode)
+			root->highest_inode = rec->ino;
+	}
+
+	/*
 	 * We need to repair backrefs first because we could change some of the
 	 * errors in the inode recs.
 	 *
-- 
2.1.3

[PATCH v4 06/13] btrfs-progs: Add btrfs_unlink() and btrfs_add_link() functions.

[Qu Wenruo]

Add btrfs_unlink() and btrfs_add_link() functions in inode.c,
for the incoming btrfs_mkdir() and later inode operations functions.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
Changlog:
v2:
   Do dir name conflicting check before adding inode_backref or
   dir_item/index.
v3:
   Allow btrfs_add_link() to add dir_index with given index, iff the
   index doesn't conflict with existing one.
v4:
   No change
---
 Makefile     |   2 +-
 cmds-check.c |   7 +-
 ctree.h      |  15 ++
 inode.c      | 438 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 455 insertions(+), 7 deletions(-)
 create mode 100644 inode.c

diff --git a/Makefile b/Makefile
index 4cae30c..d7a5cbe 100644
--- a/Makefile
+++ b/Makefile
@@ -10,7 +10,7 @@ objects = ctree.o disk-io.o radix-tree.o extent-tree.o print-tree.o \
 	  root-tree.o dir-item.o file-item.o inode-item.o inode-map.o \
 	  extent-cache.o extent_io.o volumes.o utils.o repair.o \
 	  qgroup.o raid6.o free-space-cache.o list_sort.o props.o \
-	  ulist.o qgroup-verify.o backref.o
+	  ulist.o qgroup-verify.o backref.o inode.o
 cmds_objects = cmds-subvolume.o cmds-filesystem.o cmds-device.o cmds-scrub.o \
 	       cmds-inspect.o cmds-balance.o cmds-send.o cmds-receive.o \
 	       cmds-quota.o cmds-qgroup.o cmds-replace.o cmds-check.o \
diff --git a/cmds-check.c b/cmds-check.c
index 1f35cc2..53557b6 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -1599,14 +1599,9 @@ static int repair_inode_orphan_item(struct btrfs_trans_handle *trans,
 				    struct btrfs_path *path,
 				    struct inode_record *rec)
 {
-	struct btrfs_key key;
 	int ret;
 
-	key.objectid = BTRFS_ORPHAN_OBJECTID;
-	key.type = BTRFS_ORPHAN_ITEM_KEY;
-	key.offset = rec->ino;
-
-	ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
+	ret = btrfs_add_orphan_item(trans, root, path, rec->ino);
 	btrfs_release_path(path);
 	if (!ret)
 		rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
diff --git a/ctree.h b/ctree.h
index 32b1286..21bafd2 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2444,4 +2444,19 @@ static inline int is_fstree(u64 rootid)
 		return 1;
 	return 0;
 }
+
+/* inode.c */
+int check_dir_conflict(struct btrfs_root *root,
+		       char *name, int namelen,
+		       u64 dir, u64 index);
+int btrfs_add_link(struct btrfs_trans_handle *trans, struct btrfs_root *root,
+		   u64 ino, u64 parent_ino, char *name, int namelen,
+		   u8 type, u64 *index, int add_backref);
+int btrfs_unlink(struct btrfs_trans_handle *trans, struct btrfs_root *root,
+		 u64 ino, u64 parent_ino, u64 index, const char *name,
+		 int namelen, int add_orphan);
+int btrfs_add_orphan_item(struct btrfs_trans_handle *trans,
+			  struct btrfs_root *root,
+			  struct btrfs_path *path,
+			  u64 ino);
 #endif
diff --git a/inode.c b/inode.c
new file mode 100644
index 0000000..aeb0a5c
--- /dev/null
+++ b/inode.c
@@ -0,0 +1,438 @@
+/*
+ * Copyright (C) 2014 Fujitsu.  All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public
+ * License v2 as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public
+ * License along with this program; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 021110-1307, USA.
+ */
+
+/*
+ * Unlike inode.c in kernel, which can use most of the kernel infrastructure
+ * like inode/dentry things, in user-land, we can only use inode number to
+ * do directly operation on extent buffer, which may cause extra searching,
+ * but should not be a huge problem since progs is less performence sensitive.
+ */
+#include <sys/stat.h>
+#include "ctree.h"
+#include "transaction.h"
+#include "disk-io.h"
+#include "time.h"
+
+/*
+ * Find a free inode index for later btrfs_add_link().
+ * Currently just search from the largest dir_index and +1.
+ */
+static int btrfs_find_free_dir_index(struct btrfs_root *root, u64 dir_ino,
+				     u64 *ret_ino)
+{
+	struct btrfs_path *path;
+	struct btrfs_key key;
+	struct btrfs_key found_key;
+	u64 ret_val = 2;
+	int ret = 0;
+
+	if (!ret_ino)
+		return 0;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	key.objectid = dir_ino;
+	key.type = BTRFS_DIR_INDEX_KEY;
+	key.offset = (u64)-1;
+
+	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
+	if (ret < 0)
+		goto out;
+	ret = 0;
+	if (path->slots[0] == 0) {
+		ret = btrfs_prev_leaf(root, path);
+		if (ret < 0)
+			goto out;
+		if (ret > 0) {
+			/*
+			 * This shouldn't happen since there must be a leaf
+			 * containing the DIR_ITEM.
+			 * Can only happen when the previous leaf is corrupted.
+			 */
+			ret = -EIO;
+			goto out;
+		}
+	} else {
+		path->slots[0]--;
+	}
+	btrfs_item_key_to_cpu(path->nodes[0], &found_key, path->slots[0]);
+	if (found_key.objectid != dir_ino ||
+	    found_key.type != BTRFS_DIR_INDEX_KEY)
+		goto out;
+	ret_val = found_key.offset + 1;
+out:
+	btrfs_free_path(path);
+	if (ret == 0)
+		*ret_ino = ret_val;
+	return ret;
+}
+
+/* Check the dir_item/index conflicts before insert */
+int check_dir_conflict(struct btrfs_root *root,
+		       char *name, int namelen,
+		       u64 dir, u64 index)
+{
+	struct btrfs_path *path;
+	struct btrfs_key key;
+	struct btrfs_inode_item *inode_item;
+	struct btrfs_dir_item *dir_item;
+	int ret = 0;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	/* Given dir exists? */
+	key.objectid = dir;
+	key.type = BTRFS_INODE_ITEM_KEY;
+	key.offset = 0;
+	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
+	if (ret < 0)
+		goto out;
+	if (ret > 0) {
+		ret = -ENOENT;
+		goto out;
+	}
+
+	/* Is it a dir? */
+	inode_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
+				    struct btrfs_inode_item);
+	if (!(btrfs_inode_mode(path->nodes[0], inode_item) &
+	      S_IFDIR)) {
+		ret = -ENOTDIR;
+		goto out;
+	}
+	btrfs_release_path(path);
+
+	/* Name conflicting? */
+	dir_item = btrfs_lookup_dir_item(NULL, root, path, dir, name,
+					 namelen, 0);
+	if (IS_ERR(dir_item)) {
+		ret = PTR_ERR(dir_item);
+		goto out;
+	}
+	if (dir_item) {
+		ret = -EEXIST;
+		goto out;
+	}
+	btrfs_release_path(path);
+
+	/* Index conflicting? */
+	dir_item = btrfs_lookup_dir_index(NULL, root, path, dir, name,
+					  namelen, index, 0);
+	if (IS_ERR(dir_item) && PTR_ERR(dir_item) == -ENOENT)
+		dir_item = NULL;
+	if (IS_ERR(dir_item)) {
+		ret = PTR_ERR(dir_item);
+		goto out;
+	}
+	if (dir_item) {
+		ret = -EEXIST;
+		goto out;
+	}
+
+out:
+	btrfs_free_path(path);
+	return ret;
+}
+
+/*
+ * Add dir_item/index for 'parent_ino'
+ * if add_backref is true, also insert a backref from the ino to parent dir
+ * and update the nlink(Kernel version does not do this thing)
+ *
+ * Currently only supports adding link from an inode to another inode.
+ */
+
+int btrfs_add_link(struct btrfs_trans_handle *trans, struct btrfs_root *root,
+		   u64 ino, u64 parent_ino, char *name, int namelen,
+		   u8 type, u64 *index, int add_backref)
+{
+	struct btrfs_path *path;
+	struct btrfs_key key;
+	struct btrfs_inode_item *inode_item;
+	u32 nlink;
+	u64 inode_size;
+	u64 ret_index = 0;
+	int ret = 0;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	if (index && *index) {
+		ret_index = *index;
+	} else {
+		ret = btrfs_find_free_dir_index(root, parent_ino, &ret_index);
+		if (ret < 0)
+			goto out;
+	}
+
+	ret = check_dir_conflict(root, name, namelen, parent_ino, ret_index);
+	if (ret < 0)
+		goto out;
+
+	/* Add inode ref */
+	if (add_backref) {
+		ret = btrfs_insert_inode_ref(trans, root, name, namelen,
+					     ino, parent_ino, ret_index);
+		if (ret < 0)
+			goto out;
+
+		/* Update nlinks for the inode */
+		key.objectid = ino;
+		key.type = BTRFS_INODE_ITEM_KEY;
+		key.offset = 0;
+		ret = btrfs_search_slot(trans, root, &key, path, 1, 1);
+		if (ret) {
+			if (ret > 0)
+				ret = -ENOENT;
+			goto out;
+		}
+		inode_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
+				    struct btrfs_inode_item);
+		nlink = btrfs_inode_nlink(path->nodes[0], inode_item);
+		nlink++;
+		btrfs_set_inode_nlink(path->nodes[0], inode_item, nlink);
+		btrfs_mark_buffer_dirty(path->nodes[0]);
+		btrfs_release_path(path);
+	}
+
+	/* Add dir_item and dir_index */
+	key.objectid = ino;
+	key.type = BTRFS_INODE_ITEM_KEY;
+	key.offset = 0;
+	ret = btrfs_insert_dir_item(trans, root, name, namelen, parent_ino,
+				    &key, type, ret_index);
+	if (ret < 0)
+		goto out;
+
+	/* Update inode size of the parent inode */
+	key.objectid = parent_ino;
+	key.type = BTRFS_INODE_ITEM_KEY;
+	key.offset = 0;
+	ret = btrfs_search_slot(trans, root, &key, path, 1, 1);
+	if (ret)
+		goto out;
+	inode_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
+				    struct btrfs_inode_item);
+	inode_size = btrfs_inode_size(path->nodes[0], inode_item);
+	inode_size += namelen * 2;
+	btrfs_set_inode_size(path->nodes[0], inode_item, inode_size);
+	btrfs_mark_buffer_dirty(path->nodes[0]);
+	btrfs_release_path(path);
+
+out:
+	btrfs_free_path(path);
+	if (ret == 0 && index)
+		*index = ret_index;
+	return ret;
+}
+
+int btrfs_add_orphan_item(struct btrfs_trans_handle *trans,
+			  struct btrfs_root *root,
+			  struct btrfs_path *path,
+			  u64 ino)
+{
+	struct btrfs_key key;
+	int ret = 0;
+
+	key.objectid = BTRFS_ORPHAN_OBJECTID;
+	key.type = BTRFS_ORPHAN_ITEM_KEY;
+	key.offset = ino;
+
+	ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
+	return ret;
+}
+
+/*
+ * Unlink an inode, which will remove its backref and corresponding dir_index/
+ * dir_item if any of them exists.
+ *
+ * If an inode's nlink is reduced to 0 and 'add_orphan' is true, it will be
+ * added to orphan inode and wairing to be deleted by next kernel mount.
+ */
+int btrfs_unlink(struct btrfs_trans_handle *trans, struct btrfs_root *root,
+		 u64 ino, u64 parent_ino, u64 index, const char *name,
+		 int namelen, int add_orphan)
+{
+	struct btrfs_path *path;
+	struct btrfs_key key;
+	struct btrfs_inode_item *inode_item;
+	struct btrfs_inode_ref *inode_ref;
+	struct btrfs_dir_item *dir_item;
+	u64 inode_size;
+	u32 nlinks;
+	int del_inode_ref = 0;
+	int del_dir_item = 0;
+	int del_dir_index = 0;
+	int ret = 0;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	/* check the ref and backref exists */
+	inode_ref = btrfs_lookup_inode_ref(trans, root, path, name, namelen,
+					   ino, parent_ino, index, 0);
+	if (IS_ERR(inode_ref)) {
+		ret = PTR_ERR(inode_ref);
+		goto out;
+	}
+	if (inode_ref)
+		del_inode_ref = 1;
+	btrfs_release_path(path);
+
+	dir_item = btrfs_lookup_dir_item(NULL, root, path, parent_ino,
+					 name, namelen, 0);
+	if (IS_ERR(dir_item)) {
+		ret = PTR_ERR(dir_item);
+		goto out;
+	}
+	if (dir_item)
+		del_dir_item = 1;
+	btrfs_release_path(path);
+
+	dir_item = btrfs_lookup_dir_index(NULL, root, path, parent_ino,
+					  name, namelen, index, 0);
+	/*
+	 * Since lookup_dir_index() will return -ENOENT when not found,
+	 * we need to do extra check.
+	 */
+	if (IS_ERR(dir_item) && PTR_ERR(dir_item) == -ENOENT)
+		dir_item = NULL;
+	if (IS_ERR(dir_item)) {
+		ret = PTR_ERR(dir_item);
+		goto out;
+	}
+	if (dir_item)
+		del_dir_index = 1;
+	btrfs_release_path(path);
+
+	if (!del_inode_ref && !del_dir_item && !del_dir_index) {
+		/* All not found, shouldn't happen */
+		ret = -ENOENT;
+		goto out;
+	}
+
+	if (del_inode_ref) {
+		/* Only decrease nlink when deleting inode_ref */
+		key.objectid = ino;
+		key.type = BTRFS_INODE_ITEM_KEY;
+		key.offset = 0;
+		ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
+		if (ret) {
+			if (ret > 0)
+				ret = -ENOENT;
+			goto out;
+		}
+		inode_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
+					    struct btrfs_inode_item);
+		nlinks = btrfs_inode_nlink(path->nodes[0], inode_item);
+		if (nlinks > 0)
+			nlinks--;
+		btrfs_set_inode_nlink(path->nodes[0], inode_item, nlinks);
+		btrfs_mark_buffer_dirty(path->nodes[0]);
+		btrfs_release_path(path);
+
+		/* For nlinks == 0, add it to orphan list if needed */
+		if (nlinks == 0 && add_orphan) {
+			ret = btrfs_add_orphan_item(trans, root, path, ino);
+			btrfs_mark_buffer_dirty(path->nodes[0]);
+			btrfs_release_path(path);
+		}
+
+		ret = btrfs_del_inode_ref(trans, root, name, namelen, ino,
+					  parent_ino, &index);
+		if (ret < 0)
+			goto out;
+	}
+
+	if (del_dir_index) {
+		dir_item = btrfs_lookup_dir_index(trans, root, path,
+						  parent_ino, name, namelen,
+						  index, -1);
+		if (IS_ERR(dir_item)) {
+			ret = PTR_ERR(dir_item);
+			goto out;
+		}
+		if (!dir_item) {
+			ret = -ENOENT;
+			goto out;
+		}
+		ret = btrfs_delete_one_dir_name(trans, root, path, dir_item);
+		if (ret)
+			goto out;
+		btrfs_release_path(path);
+
+		/* Update inode size of the parent inode */
+		key.objectid = parent_ino;
+		key.type = BTRFS_INODE_ITEM_KEY;
+		key.offset = 0;
+		ret = btrfs_search_slot(trans, root, &key, path, 1, 1);
+		if (ret)
+			goto out;
+		inode_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
+					    struct btrfs_inode_item);
+		inode_size = btrfs_inode_size(path->nodes[0], inode_item);
+		if (inode_size >= namelen)
+			inode_size -= namelen;
+		btrfs_set_inode_size(path->nodes[0], inode_item, inode_size);
+		btrfs_mark_buffer_dirty(path->nodes[0]);
+		btrfs_release_path(path);
+	}
+
+	if (del_dir_item) {
+		dir_item = btrfs_lookup_dir_item(trans, root, path, parent_ino,
+						 name, namelen, -1);
+		if (IS_ERR(dir_item)) {
+			ret = PTR_ERR(dir_item);
+			goto out;
+		}
+		if (!dir_item) {
+			ret = -ENOENT;
+			goto out;
+		}
+		ret = btrfs_delete_one_dir_name(trans, root, path, dir_item);
+		if (ret < 0)
+			goto out;
+		btrfs_release_path(path);
+
+		/* Update inode size of the parent inode */
+		key.objectid = parent_ino;
+		key.type = BTRFS_INODE_ITEM_KEY;
+		key.offset = 0;
+		ret = btrfs_search_slot(trans, root, &key, path, 1, 1);
+		if (ret)
+			goto out;
+		inode_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
+					    struct btrfs_inode_item);
+		inode_size = btrfs_inode_size(path->nodes[0], inode_item);
+		if (inode_size >= namelen)
+			inode_size -= namelen;
+		btrfs_set_inode_size(path->nodes[0], inode_item, inode_size);
+		btrfs_mark_buffer_dirty(path->nodes[0]);
+		btrfs_release_path(path);
+	}
+
+out:
+	btrfs_free_path(path);
+	return ret;
+}
-- 
2.1.3

[PATCH v4 07/13] btrfs-progs: Add btrfs_mkdir() function for the incoming 'lost+found' fsck mechanism.

[Qu Wenruo]

With the previous btrfs inode operations patches, now we can use
btrfs_mkdir() to create the 'lost+found' dir to do some data salvage in
btrfsck.

This patch along with previous ones will make data salvage easier.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
Changlog:
v2:
   Fix a bug that returns the parent ino other than the existing dir
   ino.
v3:
   No change.
v4:
   Allow mkdir() to be called using a given inode number.
   This is especially important for corrupted leaf recovery.
---
 ctree.h |   2 ++
 inode.c | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 104 insertions(+)

diff --git a/ctree.h b/ctree.h
index 21bafd2..682255c 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2459,4 +2459,6 @@ int btrfs_add_orphan_item(struct btrfs_trans_handle *trans,
 			  struct btrfs_root *root,
 			  struct btrfs_path *path,
 			  u64 ino);
+int btrfs_mkdir(struct btrfs_trans_handle *trans, struct btrfs_root *root,
+		char *name, int namelen, u64 parent_ino, u64 *ino, int mode);
 #endif
diff --git a/inode.c b/inode.c
index aeb0a5c..de35bd1 100644
--- a/inode.c
+++ b/inode.c
@@ -436,3 +436,105 @@ out:
 	btrfs_free_path(path);
 	return ret;
 }
+
+/* Fill inode item with 'mode'. Uid/gid to root/root */
+static void fill_inode_item(struct btrfs_trans_handle *trans,
+			    struct btrfs_inode_item *inode_item,
+			    u32 mode, u32 nlink)
+{
+	time_t now = time(NULL);
+
+	btrfs_set_stack_inode_generation(inode_item, trans->transid);
+	btrfs_set_stack_inode_uid(inode_item, 0);
+	btrfs_set_stack_inode_gid(inode_item, 0);
+	btrfs_set_stack_inode_size(inode_item, 0);
+	btrfs_set_stack_inode_mode(inode_item, mode);
+	btrfs_set_stack_inode_nlink(inode_item, nlink);
+	btrfs_set_stack_timespec_sec(&inode_item->atime, now);
+	btrfs_set_stack_timespec_nsec(&inode_item->atime, 0);
+	btrfs_set_stack_timespec_sec(&inode_item->mtime, now);
+	btrfs_set_stack_timespec_nsec(&inode_item->mtime, 0);
+	btrfs_set_stack_timespec_sec(&inode_item->ctime, now);
+	btrfs_set_stack_timespec_nsec(&inode_item->ctime, 0);
+}
+
+/*
+ * Unlike kernel btrfs_new_inode(), we only create the INODE_ITEM, without
+ * its backref.
+ * The backref is added by btrfs_add_link().
+ */
+static int btrfs_new_inode(struct btrfs_trans_handle *trans,
+			   struct btrfs_root *root,
+			   u64 ino, u32 mode)
+{
+	struct btrfs_inode_item inode_item = {0};
+	int ret = 0;
+
+	fill_inode_item(trans, &inode_item, mode, 0);
+	ret = btrfs_insert_inode(trans, root, ino, &inode_item);
+	return ret;
+}
+
+/*
+ * Make a dir under the parent inode 'parent_ino' with 'name'
+ * and 'mode', The owner will be root/root.
+ */
+int btrfs_mkdir(struct btrfs_trans_handle *trans, struct btrfs_root *root,
+		char *name, int namelen, u64 parent_ino, u64 *ino, int mode)
+{
+	struct btrfs_dir_item *dir_item;
+	struct btrfs_path *path;
+	u64 ret_ino = 0;
+	int ret = 0;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	if (ino && *ino)
+		ret_ino = *ino;
+
+	dir_item = btrfs_lookup_dir_item(NULL, root, path, parent_ino,
+					 name, namelen, 0);
+	if (IS_ERR(dir_item)) {
+		ret = PTR_ERR(dir_item);
+		goto out;
+	}
+
+	if (dir_item) {
+		struct btrfs_key found_key;
+
+		/*
+		 * Already have conflicting name, check if it is a dir.
+		 * Either way, no need to continue.
+		 */
+		btrfs_dir_item_key_to_cpu(path->nodes[0], dir_item, &found_key);
+		ret_ino = found_key.objectid;
+		if (btrfs_dir_type(path->nodes[0], dir_item) != BTRFS_FT_DIR)
+			ret = -EEXIST;
+		goto out;
+	}
+
+	if (!ret_ino)
+		/*
+		 * This is *UNSAFE* if some leaf is corrupted,
+		 * only used as a fallback method. Caller should either
+		 * ensure the fs is OK or pass ino with unused inode number.
+		 */
+		ret = btrfs_find_free_objectid(NULL, root, parent_ino,
+					       &ret_ino);
+	if (ret)
+		goto out;
+	ret = btrfs_new_inode(trans, root, ret_ino, mode | S_IFDIR);
+	if (ret)
+		goto out;
+	ret = btrfs_add_link(trans, root, ret_ino, parent_ino, name, namelen,
+			     BTRFS_FT_DIR, NULL, 1);
+	if (ret)
+		goto out;
+out:
+	btrfs_free_path(path);
+	if (ret == 0 && ino)
+		*ino = ret_ino;
+	return ret;
+}
-- 
2.1.3

[PATCH v4 08/13] btrfs-progs: Add count_digit() function to help calculate filename len.

[Qu Wenruo]

Add count_digit() function in utils.h to help calculate filename with
ino suffix.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
Changelog:
v4:
   Newly introduced.
---
 utils.h | 18 ++++++++++++++++++
 1 file changed, 18 insertions(+)

diff --git a/utils.h b/utils.h
index 289e86b..f68d6d8 100644
--- a/utils.h
+++ b/utils.h
@@ -161,4 +161,22 @@ static inline u64 btrfs_min_dev_size(u32 leafsize)
 
 int find_next_key(struct btrfs_path *path, struct btrfs_key *key);
 
+/*
+ * Get the length of the string converted from a u64 number.
+ *
+ * Result is equal to log10(num) + 1, but without the use of math library.
+ */
+static inline int count_digit(u64 num)
+{
+	int ret = 0;
+
+	if (num == 0)
+		return 1;
+	while (num > 0) {
+		ret++;
+		num /= 10;
+	}
+	return ret;
+}
+
 #endif
-- 
2.1.3

[PATCH v4 09/13] btrfs-progs: Add helper function find_file_name/type for nlink and inode_item repair.

[Qu Wenruo]

Add find_file_name() and find_file_type() function for later nlink and
inode_item repair.

Later nlink repair will use both function and and inode_item repair will
use find_file_type().

They are done by searching the backref list, dir_item/index for type
search and dir_item/index or inode_ref for name search.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
Changelog:
v4:
   Newly introduced to replace the old find_file_name_type(),
   which doesn't make full use of the backref list and does a poor job
   in case of leaf corruption.
---
 cmds-check.c | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 53557b6..3ec619f 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -1874,6 +1874,47 @@ static int repair_inode_backrefs(struct btrfs_root *root,
 	return ret ? ret : repaired;
 }
 
+/*
+ * To determine the file type for nlink/inode_item repair
+ *
+ * Return 0 if file type is found and BTRFS_FT_* is stored into type.
+ * Return -ENOENT if file type is not found.
+ */
+static int find_file_type(struct inode_record *rec, u8 *type)
+{
+	struct inode_backref *backref;
+
+	list_for_each_entry(backref, &rec->backrefs, list) {
+		if (backref->found_dir_index || backref->found_dir_item) {
+			*type = backref->filetype;
+			return 0;
+		}
+	}
+	return -ENOENT;
+}
+
+/*
+ * To determine the file name for nlink repair
+ *
+ * Return 0 if file name is found, set name and namelen.
+ * Return -ENOENT if file name is not found.
+ */
+static int find_file_name(struct inode_record *rec,
+			  char *name, int *namelen)
+{
+	struct inode_backref *backref;
+
+	list_for_each_entry(backref, &rec->backrefs, list) {
+		if (backref->found_dir_index || backref->found_dir_item ||
+		    backref->found_inode_ref) {
+			memcpy(name, backref->name, backref->namelen);
+			*namelen = backref->namelen;
+			return 0;
+		}
+	}
+	return -ENOENT;
+}
+
 static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec)
 {
 	struct btrfs_trans_handle *trans;
-- 
2.1.3

[PATCH v4 10/13] btrfs-progs: Add fixing function for inodes whose nlink dismatch

[Qu Wenruo]

[BUG]
At least two users have already hit a bug in btrfs causing file
missing(Chromium config file).
The missing file's nlink is still 1 but its backref points to non-exist
parent inode.

This should be a kernel bug, but btrfsck fix is needed anyway.

[FIX]
For such nlink mismatch inode, we will reset all the inode_ref with its
dir_index/item (including valid one), and re-add the valids.
If there is no valid backref for it, create 'lost+found' under the root
of the subvolume and add link to the directory.

Reported-by: Mike Gavrilov <mikhail.v.gavrilov@gmail.com>
Reported-by: Ed Tomlinson <edt@aei.ca>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>

---
changelog:
v2:
   1.Use the a more generic fucntion, reset_nlink(), to repair the inode
     nlink.
     It will remove all, including valid, backref(along with
     dir_item/index) and set nlink to 0, and add valid ones back.
     This reset_nlink() method can handle more nlink error, not only
     invalid inode_ref but also pure nlinks mismatch(2 valid inode_ref but
     nlink is 1)

   2.Fix a small bug in check_dir_conflict() which may cause false
     conflict report.
v3:
   No change.

v4:
   1.Use the highed ino + 1 as the lost+found dir inode number.
     This cooperates with later leaf-dropping recover things.
   2.Get rid of math lib
   3.Add fallback file name and file type in nlink_repair, it is quite
     important to cooperate with inode item rebuild function.
---
 cmds-check.c | 194 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 190 insertions(+), 4 deletions(-)

diff --git a/cmds-check.c b/cmds-check.c
index 3ec619f..69142ef 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -1837,6 +1837,18 @@ static int repair_inode_backrefs(struct btrfs_root *root,
 			struct btrfs_trans_handle *trans;
 			struct btrfs_key location;
 
+			ret = check_dir_conflict(root, backref->name,
+						 backref->namelen,
+						 backref->dir,
+						 backref->index);
+			if (ret) {
+				/*
+				 * let nlink fixing routine to handle it,
+				 * which can do it better.
+				 */
+				ret = 0;
+				break;
+			}
 			location.objectid = rec->ino;
 			location.type = BTRFS_INODE_ITEM_KEY;
 			location.offset = 0;
@@ -1915,20 +1927,192 @@ static int find_file_name(struct inode_record *rec,
 	return -ENOENT;
 }
 
+/* Reset the nlink of the inode to the correct one */
+static int reset_nlink(struct btrfs_trans_handle *trans,
+		       struct btrfs_root *root,
+		       struct btrfs_path *path,
+		       struct inode_record *rec)
+{
+	struct inode_backref *backref;
+	struct inode_backref *tmp;
+	struct btrfs_key key;
+	struct btrfs_inode_item *inode_item;
+	int ret = 0;
+
+	/* Remove all backref including the valid ones */
+	list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
+		ret = btrfs_unlink(trans, root, rec->ino, backref->dir,
+				   backref->index, backref->name,
+				   backref->namelen, 0);
+		if (ret < 0)
+			goto out;
+
+		/* remove invalid backref, so it won't be added back */
+		if (!(backref->found_dir_index &&
+		      backref->found_dir_item &&
+		      backref->found_inode_ref)) {
+			list_del(&backref->list);
+			free(backref);
+		}
+	}
+
+	/* Set nlink to 0 */
+	key.objectid = rec->ino;
+	key.type = BTRFS_INODE_ITEM_KEY;
+	key.offset = 0;
+	ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
+	if (ret < 0)
+		goto out;
+	if (ret > 0) {
+		ret = -ENOENT;
+		goto out;
+	}
+	inode_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
+				    struct btrfs_inode_item);
+	btrfs_set_inode_nlink(path->nodes[0], inode_item, 0);
+	btrfs_mark_buffer_dirty(path->nodes[0]);
+	btrfs_release_path(path);
+
+	/*
+	 * Add back valid inode_ref/dir_item/dir_index,
+	 * add_link() will handle the nlink inc, so new nlink must be correct
+	 */
+	list_for_each_entry(backref, &rec->backrefs, list) {
+		ret = btrfs_add_link(trans, root, rec->ino, backref->dir,
+				     backref->name, backref->namelen,
+				     backref->ref_type, &backref->index, 1);
+		if (ret < 0)
+			goto out;
+	}
+out:
+	btrfs_release_path(path);
+	return ret;
+}
+
+static int repair_inode_nlinks(struct btrfs_trans_handle *trans,
+			       struct btrfs_root *root,
+			       struct btrfs_path *path,
+			       struct inode_record *rec)
+{
+	char *dir_name = "lost+found";
+	char namebuf[BTRFS_NAME_LEN] = {0};
+	u64 lost_found_ino;
+	u32 mode = 0700;
+	u8 type = 0;
+	int namelen = 0;
+	int name_recovered = 0;
+	int type_recovered = 0;
+	int ret = 0;
+
+	/*
+	 * Get file name and type first before these invalid inode ref
+	 * are deleted by remove_all_invalid_backref()
+	 */
+	name_recovered = !find_file_name(rec, namebuf, &namelen);
+	type_recovered = !find_file_type(rec, &type);
+
+	if (!name_recovered) {
+		printf("Can't get file name for inode %llu, use '%llu' as fallback\n",
+		       rec->ino, rec->ino);
+		namelen = count_digit(rec->ino);
+		sprintf(namebuf, "%llu", rec->ino);
+		name_recovered = 1;
+	}
+	if (!type_recovered) {
+		printf("Can't get file type for inode %llu, use FILE as fallback\n",
+		       rec->ino);
+		type = BTRFS_FT_REG_FILE;
+		type_recovered = 1;
+	}
+
+	ret = reset_nlink(trans, root, path, rec);
+	if (ret < 0) {
+		fprintf(stderr,
+			"Fail to reset nlink for inode %llu: %s\n",
+			rec->ino, strerror(-ret));
+		goto out;
+	}
+
+	if (rec->found_link == 0) {
+		lost_found_ino = root->highest_inode;
+		if (lost_found_ino >= BTRFS_LAST_FREE_OBJECTID) {
+			ret = -EOVERFLOW;
+			goto out;
+		}
+		lost_found_ino++;
+		ret = btrfs_mkdir(trans, root, dir_name, strlen(dir_name),
+				  BTRFS_FIRST_FREE_OBJECTID, &lost_found_ino,
+				  mode);
+		if (ret < 0) {
+			fprintf(stderr, "Failed to create '%s' dir: %s",
+				dir_name, strerror(-ret));
+			goto out;
+		}
+		ret = btrfs_add_link(trans, root, rec->ino, lost_found_ino,
+				     namebuf, namelen, type, NULL, 1);
+		if (ret == -EEXIST) {
+			/*
+			 * Conflicting file name, add ".INO" as suffix
+			 * +1 for '.'
+			 */
+			if (namelen + count_digit(rec->ino) + 1 >
+			    BTRFS_NAME_LEN) {
+				ret = -EFBIG;
+				goto out;
+			}
+			snprintf(namebuf + namelen, BTRFS_NAME_LEN - namelen,
+				 ".%llu", rec->ino);
+			namelen += count_digit(rec->ino) + 1;
+			ret = btrfs_add_link(trans, root, rec->ino,
+					     lost_found_ino, namebuf,
+					     namelen, type, NULL, 1);
+		}
+		if (ret < 0) {
+			fprintf(stderr,
+				"Fail to link the inode %llu to %s dir: %s",
+				rec->ino, dir_name, strerror(-ret));
+			goto out;
+		}
+		/*
+		 * Just increase the found_link, don't actually add the
+		 * backref. This will make things easiler and this inode
+		 * record will be freed after the repair is done.
+		 * So fsck will not report problem about this inode.
+		 */
+		rec->found_link++;
+		printf("Moving file '%.*s' to '%s' dir since it has no valid backref\n",
+		       namelen, namebuf, dir_name);
+	}
+	rec->errors &= ~I_ERR_LINK_COUNT_WRONG;
+	printf("Fixed the nlink of inode %llu\n", rec->ino);
+out:
+	btrfs_release_path(path);
+	return ret;
+}
+
 static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec)
 {
 	struct btrfs_trans_handle *trans;
 	struct btrfs_path *path;
 	int ret = 0;
 
-	if (!(rec->errors & (I_ERR_DIR_ISIZE_WRONG | I_ERR_NO_ORPHAN_ITEM)))
+	if (!(rec->errors & (I_ERR_DIR_ISIZE_WRONG |
+			     I_ERR_NO_ORPHAN_ITEM |
+			     I_ERR_LINK_COUNT_WRONG)))
 		return rec->errors;
 
 	path = btrfs_alloc_path();
 	if (!path)
 		return -ENOMEM;
 
-	trans = btrfs_start_transaction(root, 1);
+	/*
+	 * For nlink repair, it may create a dir and add link, so
+	 * 2 for parent(256)'s dir_index and dir_item
+	 * 2 for lost+found dir's inode_item and inode_ref
+	 * 1 for the new inode_ref of the file
+	 * 2 for lost+found dir's dir_index and dir_item for the file
+	 */
+	trans = btrfs_start_transaction(root, 7);
 	if (IS_ERR(trans)) {
 		btrfs_free_path(path);
 		return PTR_ERR(trans);
@@ -1938,6 +2122,8 @@ static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec)
 		ret = repair_inode_isize(trans, root, path, rec);
 	if (!ret && rec->errors & I_ERR_NO_ORPHAN_ITEM)
 		ret = repair_inode_orphan_item(trans, root, path, rec);
+	if (!ret && rec->errors & I_ERR_LINK_COUNT_WRONG)
+		ret = repair_inode_nlinks(trans, root, path, rec);
 	btrfs_commit_transaction(trans, root);
 	btrfs_free_path(path);
 	return ret;
@@ -2088,6 +2274,8 @@ static int check_inode_recs(struct btrfs_root *root,
 			}
 		}
 
+		if (rec->found_link != rec->nlink)
+			rec->errors |= I_ERR_LINK_COUNT_WRONG;
 		if (repair) {
 			ret = try_repair_inode(root, rec);
 			if (ret == 0 && can_free_inode_rec(rec)) {
@@ -2100,8 +2288,6 @@ static int check_inode_recs(struct btrfs_root *root,
 		error++;
 		if (!rec->found_inode_item)
 			rec->errors |= I_ERR_NO_INODE_ITEM;
-		if (rec->found_link != rec->nlink)
-			rec->errors |= I_ERR_LINK_COUNT_WRONG;
 		print_inode_error(root, rec);
 		list_for_each_entry(backref, &rec->backrefs, list) {
 			if (!backref->found_dir_item)
-- 
2.1.3

[PATCH v4 11/13] btrfs-progs: record and report leaf/node corruption in fs/subvol tree

[Qu Wenruo]

When leaf/node is corrupted in fs/subvolume root, btrfsck can ignore it
without much pain except some stderr messages complaining about it.
But this works fine doing read-only works, if we want to do deeper
recovery like rebuild missing inodes in the b+tree, it will cause
problem.

At least, info user that there is something wrong in the btree,
and this patch provides the base for later btree repair.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
v2:
   Newly introduced.
v3~v4:
   No change.
---
 cmds-check.c | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 50 insertions(+), 10 deletions(-)

diff --git a/cmds-check.c b/cmds-check.c
index 69142ef..2245cea 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -1474,6 +1474,15 @@ static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
 			next = read_tree_block(root, bytenr, blocksize,
 					       ptr_gen);
 			if (!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->leafsize, *level);
 				err = -EIO;
 				goto out;
 			}
@@ -2628,6 +2637,16 @@ static int process_root_ref(struct extent_buffer *eb, int slot,
 	return 0;
 }
 
+static void free_corrupt_block(struct cache_extent *cache)
+{
+	struct btrfs_corrupt_block *corrupt;
+
+	corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
+	free(corrupt);
+}
+
+FREE_EXTENT_CACHE_BASED_TREE(corrupt_blocks, free_corrupt_block);
+
 static int check_fs_root(struct btrfs_root *root,
 			 struct cache_tree *root_cache,
 			 struct walk_control *wc)
@@ -2640,8 +2659,17 @@ static int check_fs_root(struct btrfs_root *root,
 	struct shared_node root_node;
 	struct root_record *rec;
 	struct btrfs_root_item *root_item = &root->root_item;
+	struct cache_tree corrupt_blocks;
 	enum btrfs_tree_block_status status;
 
+	/*
+	 * Reuse the corrupt_block cache tree to record corrupted tree block
+	 *
+	 * Unlike the usage in extent tree check, here we do it in a per
+	 * fs/subvol tree base.
+	 */
+	cache_tree_init(&corrupt_blocks);
+	root->fs_info->corrupt_blocks = &corrupt_blocks;
 	if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
 		rec = get_root_rec(root_cache, root->root_key.objectid);
 		if (btrfs_root_refs(root_item) > 0)
@@ -2704,6 +2732,25 @@ static int check_fs_root(struct btrfs_root *root,
 skip_walking:
 	btrfs_release_path(&path);
 
+	if (!cache_tree_empty(&corrupt_blocks)) {
+		struct cache_extent *cache;
+		struct btrfs_corrupt_block *corrupt;
+
+		printf("The following tree block(s) is corrupted in tree %llu:\n",
+		       root->root_key.objectid);
+		cache = first_cache_extent(&corrupt_blocks);
+		while (cache) {
+			corrupt = container_of(cache,
+					       struct btrfs_corrupt_block,
+					       cache);
+			printf("\ttree block bytenr: %llu, level: %d, node key: (%llu, %u, %llu)\n",
+			       cache->start, corrupt->level,
+			       corrupt->key.objectid, corrupt->key.type,
+			       corrupt->key.offset);
+			cache = next_cache_extent(cache);
+		}
+	}
+
 	err = merge_root_recs(root, &root_node.root_cache, root_cache);
 	if (err < 0)
 		ret = err;
@@ -2717,6 +2764,9 @@ skip_walking:
 	err = check_inode_recs(root, &root_node.inode_cache);
 	if (!ret)
 		ret = err;
+
+	free_corrupt_blocks_tree(&corrupt_blocks);
+	root->fs_info->corrupt_blocks = NULL;
 	return ret;
 }
 
@@ -6288,16 +6338,6 @@ static int prune_corrupt_blocks(struct btrfs_trans_handle *trans,
 	return 0;
 }
 
-static void free_corrupt_block(struct cache_extent *cache)
-{
-	struct btrfs_corrupt_block *corrupt;
-
-	corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
-	free(corrupt);
-}
-
-FREE_EXTENT_CACHE_BASED_TREE(corrupt_blocks, free_corrupt_block);
-
 static void reset_cached_block_groups(struct btrfs_fs_info *fs_info)
 {
 	struct btrfs_block_group_cache *cache;
-- 
2.1.3

[PATCH v4 12/13] btrfs-progs: Recover btree by dropping corrupted leaf/node.

[Qu Wenruo]

Current btrfsck can skip corrupted leaf and even repair some corrupted
one if their bytenr or key order is wrong.

However when it comes to csum error leaf, btrfsck can only skip them,
which is OK for read-only iteration, but is bad for write.

This patch introduce the new repair_btree() function to recover the
btree, deleting all the corrupted leaf/node including corresponding
extent, allowing later write into the btree.

This patch provides the basis for later recovery with corrupted leaves.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
Changelog:
v2:
   Newly introduced.
v3:
   Fix a wrong arguement passed to btrfs_start_transaction().
---
 cmds-check.c | 102 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 102 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 2245cea..e68966b 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -2647,6 +2647,97 @@ static void free_corrupt_block(struct cache_extent *cache)
 
 FREE_EXTENT_CACHE_BASED_TREE(corrupt_blocks, free_corrupt_block);
 
+/*
+ * Repair the btree of the given root.
+ *
+ * The fix is to remove the node key in corrupt_blocks cache_tree.
+ * and rebalance the tree.
+ * After the fix, the btree should be writeable.
+ */
+static int repair_btree(struct btrfs_root *root,
+			struct cache_tree *corrupt_blocks)
+{
+	struct btrfs_trans_handle *trans;
+	struct btrfs_path *path;
+	struct btrfs_corrupt_block *corrupt;
+	struct cache_extent *cache;
+	struct btrfs_key key;
+	u64 offset;
+	int level;
+	int ret = 0;
+
+	if (cache_tree_empty(corrupt_blocks))
+		return 0;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	trans = btrfs_start_transaction(root, 1);
+	if (IS_ERR(trans)) {
+		ret = PTR_ERR(trans);
+		fprintf(stderr, "Error starting transaction: %s\n",
+			strerror(-ret));
+		return ret;
+	}
+	cache = first_cache_extent(corrupt_blocks);
+	while (cache) {
+		corrupt = container_of(cache, struct btrfs_corrupt_block,
+				       cache);
+		level = corrupt->level;
+		path->lowest_level = level;
+		key.objectid = corrupt->key.objectid;
+		key.type = corrupt->key.type;
+		key.offset = corrupt->key.offset;
+
+		/*
+		 * Here we don't want to do any tree balance, since it may
+		 * cause a balance with corrupted brother leaf/node,
+		 * so ins_len set to 0 here.
+		 * Balance will be done after all corrupt node/leaf is deleted.
+		 */
+		ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
+		if (ret < 0)
+			goto out;
+		offset = btrfs_node_blockptr(path->nodes[level],
+					     path->slots[level]);
+
+		/* Remove the ptr */
+		ret = btrfs_del_ptr(trans, root, path, level,
+				    path->slots[level]);
+		if (ret < 0)
+			goto out;
+		/*
+		 * Remove the corresponding extent
+		 * return value is not concerned.
+		 */
+		btrfs_release_path(path);
+		ret = btrfs_free_extent(trans, root, offset, root->nodesize,
+					0, root->root_key.objectid,
+					level - 1, 0);
+		cache = next_cache_extent(cache);
+	}
+
+	/* Balance the btree using btrfs_search_slot() */
+	cache = first_cache_extent(corrupt_blocks);
+	while (cache) {
+		corrupt = container_of(cache, struct btrfs_corrupt_block,
+				       cache);
+		memcpy(&key, &corrupt->key, sizeof(key));
+		ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
+		if (ret < 0)
+			goto out;
+		/* return will always >0 since it won't find the item */
+		ret = 0;
+		btrfs_release_path(path);
+		cache = next_cache_extent(cache);
+	}
+out:
+	btrfs_free_path(path);
+	btrfs_commit_transaction(trans, root);
+	return ret;
+}
+
 static int check_fs_root(struct btrfs_root *root,
 			 struct cache_tree *root_cache,
 			 struct walk_control *wc)
@@ -2749,6 +2840,17 @@ skip_walking:
 			       corrupt->key.offset);
 			cache = next_cache_extent(cache);
 		}
+		if (repair) {
+			printf("Try to repair the btree for root %llu\n",
+			       root->root_key.objectid);
+			ret = repair_btree(root, &corrupt_blocks);
+			if (ret < 0)
+				fprintf(stderr, "Failed to repair btree: %s\n",
+					strerror(-ret));
+			if (!ret)
+				printf("Btree for root %llu is fixed\n",
+				       root->root_key.objectid);
+		}
 	}
 
 	err = merge_root_recs(root, &root_node.root_cache, root_cache);
-- 
2.1.3

[PATCH v4 13/13] btrfs-progs: Add inode item rebuild function.

[Qu Wenruo]

Add a basic inode item rebuild function for I_ERR_NO_INODE_ITEM.
The main use case is to repair btrfs which fs root has corrupted leaf,
but it is already working for case if the corrupteed fs root leaf/node
contains no inode extent_data.

The repair needs 3 elements for inode rebuild:
1. inode number
   This is quite easy, existing inode_record codes will detect it quite
   well.

2. inode type
   This is the trick part. The only reliable method is to recovery it from
   parent's dir_index/item.
   The remaining method will search for regular file extent for FILE
   type or child's backref for DIR(todo).
   Fallback will be FILE.

Inode name(inode_ref) will be recoverd by nlink repair function.

This is just a fundamental implement, some advanced recovery can be
improved later with btrfs-progs infrastructure change.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
Changelog:
v2:
   Newly introduced.
v3:
   Get rid of math lib.
v4:
   Don't do the mkdir() or add_link() things in this patch. Just pass it
   to nlink repair function.
---
 cmds-check.c | 161 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 ctree.h      |   3 ++
 inode.c      |   6 +--
 3 files changed, 163 insertions(+), 7 deletions(-)

diff --git a/cmds-check.c b/cmds-check.c
index e68966b..691ce5c 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -1905,6 +1905,12 @@ static int find_file_type(struct inode_record *rec, u8 *type)
 {
 	struct inode_backref *backref;
 
+	/* For inode item recovered case */
+	if (rec->found_inode_item) {
+		*type = imode_to_type(rec->imode);
+		return 0;
+	}
+
 	list_for_each_entry(backref, &rec->backrefs, list) {
 		if (backref->found_dir_index || backref->found_dir_item) {
 			*type = backref->filetype;
@@ -2099,6 +2105,150 @@ out:
 	return ret;
 }
 
+/*
+ * Check if there is any normal(reg or prealloc) file extent for given
+ * ino.
+ * This is used to determine the file type when neither its dir_index/item or
+ * inode_item exists.
+ *
+ * This will *NOT* report error, if any error happens, just consider it does
+ * not have any normal file extent.
+ */
+static int find_normal_file_extent(struct btrfs_root *root,
+				   u64 ino)
+{
+	struct btrfs_path *path;
+	struct btrfs_key key;
+	struct btrfs_key found_key;
+	struct btrfs_file_extent_item *fi;
+	u8 type;
+	int ret = 0;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		goto out;
+	key.objectid = ino;
+	key.type = BTRFS_EXTENT_DATA_KEY;
+	key.offset = 0;
+
+	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
+	if (ret < 0) {
+		ret = 0;
+		goto out;
+	}
+	if (ret && path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
+		ret = btrfs_next_leaf(root, path);
+		if (ret) {
+			ret = 0;
+			goto out;
+		}
+	}
+	while (1) {
+		btrfs_item_key_to_cpu(path->nodes[0], &found_key,
+				      path->slots[0]);
+		if (found_key.objectid != ino ||
+		    found_key.type != BTRFS_EXTENT_DATA_KEY)
+			break;
+		fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
+				    struct btrfs_file_extent_item);
+		type = btrfs_file_extent_type(path->nodes[0], fi);
+		if (type != BTRFS_FILE_EXTENT_INLINE)
+			ret = 1;
+			goto out;
+	}
+out:
+	btrfs_free_path(path);
+	return ret;
+}
+
+static u32 btrfs_type_to_imode(u8 type)
+{
+	static u32 imode_by_btrfs_type[] = {
+		[BTRFS_FT_REG_FILE]	= S_IFREG,
+		[BTRFS_FT_DIR]		= S_IFDIR,
+		[BTRFS_FT_CHRDEV]	= S_IFCHR,
+		[BTRFS_FT_BLKDEV]	= S_IFBLK,
+		[BTRFS_FT_FIFO]		= S_IFIFO,
+		[BTRFS_FT_SOCK]		= S_IFSOCK,
+		[BTRFS_FT_SYMLINK]	= S_IFLNK,
+	};
+
+	return imode_by_btrfs_type[(type)];
+}
+
+static int repair_inode_no_item(struct btrfs_trans_handle *trans,
+				struct btrfs_root *root,
+				struct btrfs_path *path,
+				struct inode_record *rec)
+{
+	u8 filetype;
+	u32 mode = 0700;
+	int type_recovered = 0;
+	int ret = 0;
+
+	/*
+	 * TODO:
+	 * 1. salvage data from existing file extent and
+	 *    punch hole to keep fi ext consistent.
+	 * 2. salvage data from extent tree
+	 */
+	printf("Trying to rebuild inode:%llu\n", rec->ino);
+
+	type_recovered = !find_file_type(rec, &filetype);
+
+	/*
+	 * Try to determine inode type if type not found.
+	 *
+	 * For found regular file extent, it must be FILE.
+	 * For found dir_item/index, it must be DIR.
+	 *
+	 * For undetermined one, use FILE as fallback.
+	 *
+	 * TODO:
+	 * 1. If found extent belong to it in extent tree, it must be FILE
+	 *    Need extra hook in extent tree scan.
+	 * 2. If found backref(inode_index/item is already handled) to it,
+	 *    it must be DIR.
+	 *    Need new inode-inode ref structure to allow search for that.
+	 */
+	if (!type_recovered) {
+		if (rec->found_file_extent &&
+		    find_normal_file_extent(root, rec->ino)) {
+			type_recovered = 1;
+			filetype = BTRFS_FT_REG_FILE;
+		} else if (rec->found_dir_item) {
+			type_recovered = 1;
+			filetype = BTRFS_FT_DIR;
+		} else {
+			printf("Can't determint the filetype for inode %llu, assume it is a normal file\n",
+			       rec->ino);
+			type_recovered = 1;
+			filetype = BTRFS_FT_REG_FILE;
+		}
+	}
+
+	ret = btrfs_new_inode(trans, root, rec->ino,
+			      mode | btrfs_type_to_imode(filetype));
+	if (ret < 0)
+		goto out;
+
+	/*
+	 * Here inode rebuild is done, we only rebuild the inode item,
+	 * don't repair the nlink(like move to lost+found).
+	 * That is the job of nlink repair.
+	 *
+	 * We just fill the record and return
+	 */
+	rec->found_dir_item = 1;
+	rec->imode = mode | btrfs_type_to_imode(filetype);
+	rec->nlink = 0;
+	rec->errors &= ~I_ERR_NO_INODE_ITEM;
+	/* Ensure the inode_nlinks repair function will be called */
+	rec->errors |= I_ERR_LINK_COUNT_WRONG;
+out:
+	return ret;
+}
+
 static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec)
 {
 	struct btrfs_trans_handle *trans;
@@ -2107,7 +2257,8 @@ static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec)
 
 	if (!(rec->errors & (I_ERR_DIR_ISIZE_WRONG |
 			     I_ERR_NO_ORPHAN_ITEM |
-			     I_ERR_LINK_COUNT_WRONG)))
+			     I_ERR_LINK_COUNT_WRONG |
+			     I_ERR_NO_INODE_ITEM)))
 		return rec->errors;
 
 	path = btrfs_alloc_path();
@@ -2127,7 +2278,9 @@ static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec)
 		return PTR_ERR(trans);
 	}
 
-	if (rec->errors & I_ERR_DIR_ISIZE_WRONG)
+	if (rec->errors & I_ERR_NO_INODE_ITEM)
+		ret = repair_inode_no_item(trans, root, path, rec);
+	if (!ret && rec->errors & I_ERR_DIR_ISIZE_WRONG)
 		ret = repair_inode_isize(trans, root, path, rec);
 	if (!ret && rec->errors & I_ERR_NO_ORPHAN_ITEM)
 		ret = repair_inode_orphan_item(trans, root, path, rec);
@@ -2283,6 +2436,8 @@ static int check_inode_recs(struct btrfs_root *root,
 			}
 		}
 
+		if (!rec->found_inode_item)
+			rec->errors |= I_ERR_NO_INODE_ITEM;
 		if (rec->found_link != rec->nlink)
 			rec->errors |= I_ERR_LINK_COUNT_WRONG;
 		if (repair) {
@@ -2295,8 +2450,6 @@ static int check_inode_recs(struct btrfs_root *root,
 		}
 
 		error++;
-		if (!rec->found_inode_item)
-			rec->errors |= I_ERR_NO_INODE_ITEM;
 		print_inode_error(root, rec);
 		list_for_each_entry(backref, &rec->backrefs, list) {
 			if (!backref->found_dir_item)
diff --git a/ctree.h b/ctree.h
index 682255c..dbe9b39 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2449,6 +2449,9 @@ static inline int is_fstree(u64 rootid)
 int check_dir_conflict(struct btrfs_root *root,
 		       char *name, int namelen,
 		       u64 dir, u64 index);
+int btrfs_new_inode(struct btrfs_trans_handle *trans,
+		    struct btrfs_root *root,
+		    u64 ino, u32 mode);
 int btrfs_add_link(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 		   u64 ino, u64 parent_ino, char *name, int namelen,
 		   u8 type, u64 *index, int add_backref);
diff --git a/inode.c b/inode.c
index de35bd1..c99fe38 100644
--- a/inode.c
+++ b/inode.c
@@ -463,9 +463,9 @@ static void fill_inode_item(struct btrfs_trans_handle *trans,
  * its backref.
  * The backref is added by btrfs_add_link().
  */
-static int btrfs_new_inode(struct btrfs_trans_handle *trans,
-			   struct btrfs_root *root,
-			   u64 ino, u32 mode)
+int btrfs_new_inode(struct btrfs_trans_handle *trans,
+		    struct btrfs_root *root,
+		    u64 ino, u32 mode)
 {
 	struct btrfs_inode_item inode_item = {0};
 	int ret = 0;
-- 
2.1.3

Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and

[David Sterba]

On Tue, Dec 09, 2014 at 04:27:19PM +0800, Qu Wenruo wrote:
> The patchset introduce two new repair function and some helpers to
> archive a huge goal:
>   Repair btrfs whose fs tree's non-root leaf/node is corrupted when no
>   duplication is valid.
> 
> The two new repair functions are:
>   repair_inode_nlinks():
>     Repair any inode nlink related problem.
>     From fixing the nlink number and related
>     inode_ref/dir_index/dir_item to recovering file name and file type
>     and salvage them into the lost+found dir.
>     This does not only fix a case that some users reported but also
>     cooperate with repair_inode_no_item() function to salvaged heavily
>     damaged inode to lost+found dir.
> 
>   repair_inode_no_item():
>     Repair case for inode_item missing case, which is quite common when
>     fs tree leaf/node is missing.
>     This only does the inode item rebuild. Later recovery like move it
>     to lost+found dir is done by repair_inode_nlinks().
> 
> The main helper is the repair_btree() function, which will drops the
> corrupted non-root leaf/node and rebalance the tree to keep the
> correctness of the btree.

Sounds a bit intrusive, but under the circumstances I don't see anything
better to do.

> With this patchset, even a non-root leaf/node is corrupted and no
> duplication survived, btrfsck can still repair it to a mountable status.
> (And normal rw should also be OK,)
> 
> The remaining unfixable problems will be inode nbytes error with file
> extent discounts error, which may be fixed in next patchset.
> 
> Cc David:
> Sorry for the huge change in the patchset and merge the old inode nlink
> repair with new inode item rebuild patchset.

No problem, the incremental changelogs helped a lot.

> Since when developing inode item rebuild patchset, I found the old nlink
> cooperated very bad with item rebuild and there is some duplicated codes
> between the two patchset, no to mention the math lib introduced by nlink
> repair patch.
> So I decided to somewhat rebase the nlink repair patchset to provide
> better generality.

Great, the patchset looks good for merge, I'm adding it to 3.18. From
now on please send only incremental changes and not the whole patchset.
Thanks.

Re: [PATCH v4 08/13] btrfs-progs: Add count_digit() function to help calculate filename len.

[David Sterba]

On Tue, Dec 09, 2014 at 04:27:27PM +0800, Qu Wenruo wrote:
> +static inline int count_digit(u64 num)

FYI, I've renamed it to count_digits, and updated all callers.

Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and

[Qu Wenruo]

-------- Original Message --------
Subject: Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and
From: David Sterba <dsterba@suse.cz>
To: Qu Wenruo <quwenruo@cn.fujitsu.com>
Date: 2014年12月10日 20:37
> On Tue, Dec 09, 2014 at 04:27:19PM +0800, Qu Wenruo wrote:
>> The patchset introduce two new repair function and some helpers to
>> archive a huge goal:
>>    Repair btrfs whose fs tree's non-root leaf/node is corrupted when no
>>    duplication is valid.
>>
>> The two new repair functions are:
>>    repair_inode_nlinks():
>>      Repair any inode nlink related problem.
>>      From fixing the nlink number and related
>>      inode_ref/dir_index/dir_item to recovering file name and file type
>>      and salvage them into the lost+found dir.
>>      This does not only fix a case that some users reported but also
>>      cooperate with repair_inode_no_item() function to salvaged heavily
>>      damaged inode to lost+found dir.
>>
>>    repair_inode_no_item():
>>      Repair case for inode_item missing case, which is quite common when
>>      fs tree leaf/node is missing.
>>      This only does the inode item rebuild. Later recovery like move it
>>      to lost+found dir is done by repair_inode_nlinks().
>>
>> The main helper is the repair_btree() function, which will drops the
>> corrupted non-root leaf/node and rebalance the tree to keep the
>> correctness of the btree.
> Sounds a bit intrusive, but under the circumstances I don't see anything
> better to do.
Better non-destructive but less generic method may be introduced later.
My dream is to inspect each key and its item to rebuild each member, but 
it would takes a long long time
to implement.
>
>> With this patchset, even a non-root leaf/node is corrupted and no
>> duplication survived, btrfsck can still repair it to a mountable status.
>> (And normal rw should also be OK,)
>>
>> The remaining unfixable problems will be inode nbytes error with file
>> extent discounts error, which may be fixed in next patchset.
>>
>> Cc David:
>> Sorry for the huge change in the patchset and merge the old inode nlink
>> repair with new inode item rebuild patchset.
> No problem, the incremental changelogs helped a lot.
>
>> Since when developing inode item rebuild patchset, I found the old nlink
>> cooperated very bad with item rebuild and there is some duplicated codes
>> between the two patchset, no to mention the math lib introduced by nlink
>> repair patch.
>> So I decided to somewhat rebase the nlink repair patchset to provide
>> better generality.
> Great, the patchset looks good for merge, I'm adding it to 3.18. From
> now on please send only incremental changes and not the whole patchset.
> Thanks.
Thanks, this should be the last large update patchset.
Later work will focus on file extent recovery and should not interfere 
with this patch.

Thanks.
Qu

Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and

[Filipe David Manana]

On Thu, Dec 11, 2014 at 12:50 AM, Qu Wenruo <quwenruo@cn.fujitsu.com> wrote:
>
> -------- Original Message --------
> Subject: Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and
> From: David Sterba <dsterba@suse.cz>
> To: Qu Wenruo <quwenruo@cn.fujitsu.com>
> Date: 2014年12月10日 20:37
>>
>> On Tue, Dec 09, 2014 at 04:27:19PM +0800, Qu Wenruo wrote:
>>>
>>> The patchset introduce two new repair function and some helpers to
>>> archive a huge goal:
>>>    Repair btrfs whose fs tree's non-root leaf/node is corrupted when no
>>>    duplication is valid.
>>>
>>> The two new repair functions are:
>>>    repair_inode_nlinks():
>>>      Repair any inode nlink related problem.
>>>      From fixing the nlink number and related
>>>      inode_ref/dir_index/dir_item to recovering file name and file type
>>>      and salvage them into the lost+found dir.
>>>      This does not only fix a case that some users reported but also
>>>      cooperate with repair_inode_no_item() function to salvaged heavily
>>>      damaged inode to lost+found dir.
>>>
>>>    repair_inode_no_item():
>>>      Repair case for inode_item missing case, which is quite common when
>>>      fs tree leaf/node is missing.
>>>      This only does the inode item rebuild. Later recovery like move it
>>>      to lost+found dir is done by repair_inode_nlinks().
>>>
>>> The main helper is the repair_btree() function, which will drops the
>>> corrupted non-root leaf/node and rebalance the tree to keep the
>>> correctness of the btree.
>>
>> Sounds a bit intrusive, but under the circumstances I don't see anything
>> better to do.
>
> Better non-destructive but less generic method may be introduced later.
> My dream is to inspect each key and its item to rebuild each member, but it
> would takes a long long time
> to implement.
>>
>>
>>> With this patchset, even a non-root leaf/node is corrupted and no
>>> duplication survived, btrfsck can still repair it to a mountable status.
>>> (And normal rw should also be OK,)
>>>
>>> The remaining unfixable problems will be inode nbytes error with file
>>> extent discounts error, which may be fixed in next patchset.
>>>
>>> Cc David:
>>> Sorry for the huge change in the patchset and merge the old inode nlink
>>> repair with new inode item rebuild patchset.
>>
>> No problem, the incremental changelogs helped a lot.
>>
>>> Since when developing inode item rebuild patchset, I found the old nlink
>>> cooperated very bad with item rebuild and there is some duplicated codes
>>> between the two patchset, no to mention the math lib introduced by nlink
>>> repair patch.
>>> So I decided to somewhat rebase the nlink repair patchset to provide
>>> better generality.
>>
>> Great, the patchset looks good for merge, I'm adding it to 3.18. From
>> now on please send only incremental changes and not the whole patchset.
>> Thanks.
>
> Thanks, this should be the last large update patchset.
> Later work will focus on file extent recovery and should not interfere with
> this patch.
>
> Thanks.
> Qu

Can we please get some tests too?
Add some broken fs images, document what is broken and the expected
result after running the repair code (besides verifying the repair
worked for every single inode of course)...

thanks

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



-- 
Filipe David Manana,

"Reasonable men adapt themselves to the world.
 Unreasonable men adapt the world to themselves.
 That's why all progress depends on unreasonable men."

Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and

[Qu Wenruo]

-------- Original Message --------
Subject: Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and
From: Filipe David Manana <fdmanana@gmail.com>
To: Qu Wenruo <quwenruo@cn.fujitsu.com>
Date: 2014年12月11日 19:07
> On Thu, Dec 11, 2014 at 12:50 AM, Qu Wenruo <quwenruo@cn.fujitsu.com> wrote:
>> -------- Original Message --------
>> Subject: Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and
>> From: David Sterba <dsterba@suse.cz>
>> To: Qu Wenruo <quwenruo@cn.fujitsu.com>
>> Date: 2014年12月10日 20:37
>>> On Tue, Dec 09, 2014 at 04:27:19PM +0800, Qu Wenruo wrote:
>>>> The patchset introduce two new repair function and some helpers to
>>>> archive a huge goal:
>>>>     Repair btrfs whose fs tree's non-root leaf/node is corrupted when no
>>>>     duplication is valid.
>>>>
>>>> The two new repair functions are:
>>>>     repair_inode_nlinks():
>>>>       Repair any inode nlink related problem.
>>>>       From fixing the nlink number and related
>>>>       inode_ref/dir_index/dir_item to recovering file name and file type
>>>>       and salvage them into the lost+found dir.
>>>>       This does not only fix a case that some users reported but also
>>>>       cooperate with repair_inode_no_item() function to salvaged heavily
>>>>       damaged inode to lost+found dir.
>>>>
>>>>     repair_inode_no_item():
>>>>       Repair case for inode_item missing case, which is quite common when
>>>>       fs tree leaf/node is missing.
>>>>       This only does the inode item rebuild. Later recovery like move it
>>>>       to lost+found dir is done by repair_inode_nlinks().
>>>>
>>>> The main helper is the repair_btree() function, which will drops the
>>>> corrupted non-root leaf/node and rebalance the tree to keep the
>>>> correctness of the btree.
>>> Sounds a bit intrusive, but under the circumstances I don't see anything
>>> better to do.
>> Better non-destructive but less generic method may be introduced later.
>> My dream is to inspect each key and its item to rebuild each member, but it
>> would takes a long long time
>> to implement.
>>>
>>>> With this patchset, even a non-root leaf/node is corrupted and no
>>>> duplication survived, btrfsck can still repair it to a mountable status.
>>>> (And normal rw should also be OK,)
>>>>
>>>> The remaining unfixable problems will be inode nbytes error with file
>>>> extent discounts error, which may be fixed in next patchset.
>>>>
>>>> Cc David:
>>>> Sorry for the huge change in the patchset and merge the old inode nlink
>>>> repair with new inode item rebuild patchset.
>>> No problem, the incremental changelogs helped a lot.
>>>
>>>> Since when developing inode item rebuild patchset, I found the old nlink
>>>> cooperated very bad with item rebuild and there is some duplicated codes
>>>> between the two patchset, no to mention the math lib introduced by nlink
>>>> repair patch.
>>>> So I decided to somewhat rebase the nlink repair patchset to provide
>>>> better generality.
>>> Great, the patchset looks good for merge, I'm adding it to 3.18. From
>>> now on please send only incremental changes and not the whole patchset.
>>> Thanks.
>> Thanks, this should be the last large update patchset.
>> Later work will focus on file extent recovery and should not interfere with
>> this patch.
>>
>> Thanks.
>> Qu
> Can we please get some tests too?
> Add some broken fs images, document what is broken and the expected
> result after running the repair code (besides verifying the repair
> worked for every single inode of course)...
>
> thanks
Tests are definitely needed, I tested this by randomly corrupt a leaf of 
fstree, which contains contents of my /etc,
and run repair.

But the problem is that, we can't add tests like other btrfsck using 
btrfs-image dump, since it will fail to dump
a btree-broken btrfs.
And if we add test image directly, it may takes up several MB as a 
binary image dump.

Any good idea about how to add test case without btrfs-image support?

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

Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and

[Filipe David Manana]

On Fri, Dec 12, 2014 at 12:32 AM, Qu Wenruo <quwenruo@cn.fujitsu.com> wrote:
>
> -------- Original Message --------
> Subject: Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and
> From: Filipe David Manana <fdmanana@gmail.com>
> To: Qu Wenruo <quwenruo@cn.fujitsu.com>
> Date: 2014年12月11日 19:07
>>
>> On Thu, Dec 11, 2014 at 12:50 AM, Qu Wenruo <quwenruo@cn.fujitsu.com>
>> wrote:
>>>
>>> -------- Original Message --------
>>> Subject: Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch
>>> and
>>> From: David Sterba <dsterba@suse.cz>
>>> To: Qu Wenruo <quwenruo@cn.fujitsu.com>
>>> Date: 2014年12月10日 20:37
>>>>
>>>> On Tue, Dec 09, 2014 at 04:27:19PM +0800, Qu Wenruo wrote:
>>>>>
>>>>> The patchset introduce two new repair function and some helpers to
>>>>> archive a huge goal:
>>>>>     Repair btrfs whose fs tree's non-root leaf/node is corrupted when
>>>>> no
>>>>>     duplication is valid.
>>>>>
>>>>> The two new repair functions are:
>>>>>     repair_inode_nlinks():
>>>>>       Repair any inode nlink related problem.
>>>>>       From fixing the nlink number and related
>>>>>       inode_ref/dir_index/dir_item to recovering file name and file
>>>>> type
>>>>>       and salvage them into the lost+found dir.
>>>>>       This does not only fix a case that some users reported but also
>>>>>       cooperate with repair_inode_no_item() function to salvaged
>>>>> heavily
>>>>>       damaged inode to lost+found dir.
>>>>>
>>>>>     repair_inode_no_item():
>>>>>       Repair case for inode_item missing case, which is quite common
>>>>> when
>>>>>       fs tree leaf/node is missing.
>>>>>       This only does the inode item rebuild. Later recovery like move
>>>>> it
>>>>>       to lost+found dir is done by repair_inode_nlinks().
>>>>>
>>>>> The main helper is the repair_btree() function, which will drops the
>>>>> corrupted non-root leaf/node and rebalance the tree to keep the
>>>>> correctness of the btree.
>>>>
>>>> Sounds a bit intrusive, but under the circumstances I don't see anything
>>>> better to do.
>>>
>>> Better non-destructive but less generic method may be introduced later.
>>> My dream is to inspect each key and its item to rebuild each member, but
>>> it
>>> would takes a long long time
>>> to implement.
>>>>
>>>>
>>>>> With this patchset, even a non-root leaf/node is corrupted and no
>>>>> duplication survived, btrfsck can still repair it to a mountable
>>>>> status.
>>>>> (And normal rw should also be OK,)
>>>>>
>>>>> The remaining unfixable problems will be inode nbytes error with file
>>>>> extent discounts error, which may be fixed in next patchset.
>>>>>
>>>>> Cc David:
>>>>> Sorry for the huge change in the patchset and merge the old inode nlink
>>>>> repair with new inode item rebuild patchset.
>>>>
>>>> No problem, the incremental changelogs helped a lot.
>>>>
>>>>> Since when developing inode item rebuild patchset, I found the old
>>>>> nlink
>>>>> cooperated very bad with item rebuild and there is some duplicated
>>>>> codes
>>>>> between the two patchset, no to mention the math lib introduced by
>>>>> nlink
>>>>> repair patch.
>>>>> So I decided to somewhat rebase the nlink repair patchset to provide
>>>>> better generality.
>>>>
>>>> Great, the patchset looks good for merge, I'm adding it to 3.18. From
>>>> now on please send only incremental changes and not the whole patchset.
>>>> Thanks.
>>>
>>> Thanks, this should be the last large update patchset.
>>> Later work will focus on file extent recovery and should not interfere
>>> with
>>> this patch.
>>>
>>> Thanks.
>>> Qu
>>
>> Can we please get some tests too?
>> Add some broken fs images, document what is broken and the expected
>> result after running the repair code (besides verifying the repair
>> worked for every single inode of course)...
>>
>> thanks
>
> Tests are definitely needed, I tested this by randomly corrupt a leaf of
> fstree, which contains contents of my /etc,
> and run repair.
>
> But the problem is that, we can't add tests like other btrfsck using
> btrfs-image dump, since it will fail to dump
> a btree-broken btrfs.
> And if we add test image directly, it may takes up several MB as a binary
> image dump.
>
> Any good idea about how to add test case without btrfs-image support?

Very simple solution.

Do:

1) Create an empty file;
2) Use it as the backing file for a loop device;
3) Run mkfs.btrfs against the loop device;
4) Mount it;
5) Populate the fs;
6) Umount it;
7) Corrupt some nodes or leafs (by zeroing them out for e.g.);
8) Create a tarball from the backing file like this: ZX_OPT=-9 tar
cJSvf foobar.tar.xz run.sh backing_file
9) Add the tarball to the fsck-tests directory;
10) Make the test run fsck against the backing file extracted from the
tarball - fsck can operate against regular files, and not only against
devices.

I did that a couple months ago, see:

http://git.kernel.org/cgit/linux/kernel/git/kdave/btrfs-progs.git/tree/tests/fsck-tests.sh?h=v3.17.x#n30

Exactly because for some kinds of damage in a filesystem btrfs-image won't work.

Thanks.

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



-- 
Filipe David Manana,

"Reasonable men adapt themselves to the world.
 Unreasonable men adapt the world to themselves.
 That's why all progress depends on unreasonable men."

Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and

[Qu Wenruo]

-------- Original Message --------
Subject: Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and
From: Filipe David Manana <fdmanana@gmail.com>
To: Qu Wenruo <quwenruo@cn.fujitsu.com>
Date: 2014年12月12日 16:34
> On Fri, Dec 12, 2014 at 12:32 AM, Qu Wenruo <quwenruo@cn.fujitsu.com> wrote:
>> -------- Original Message --------
>> Subject: Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and
>> From: Filipe David Manana <fdmanana@gmail.com>
>> To: Qu Wenruo <quwenruo@cn.fujitsu.com>
>> Date: 2014年12月11日 19:07
>>> On Thu, Dec 11, 2014 at 12:50 AM, Qu Wenruo <quwenruo@cn.fujitsu.com>
>>> wrote:
>>>> -------- Original Message --------
>>>> Subject: Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch
>>>> and
>>>> From: David Sterba <dsterba@suse.cz>
>>>> To: Qu Wenruo <quwenruo@cn.fujitsu.com>
>>>> Date: 2014年12月10日 20:37
>>>>> On Tue, Dec 09, 2014 at 04:27:19PM +0800, Qu Wenruo wrote:
>>>>>> The patchset introduce two new repair function and some helpers to
>>>>>> archive a huge goal:
>>>>>>      Repair btrfs whose fs tree's non-root leaf/node is corrupted when
>>>>>> no
>>>>>>      duplication is valid.
>>>>>>
>>>>>> The two new repair functions are:
>>>>>>      repair_inode_nlinks():
>>>>>>        Repair any inode nlink related problem.
>>>>>>        From fixing the nlink number and related
>>>>>>        inode_ref/dir_index/dir_item to recovering file name and file
>>>>>> type
>>>>>>        and salvage them into the lost+found dir.
>>>>>>        This does not only fix a case that some users reported but also
>>>>>>        cooperate with repair_inode_no_item() function to salvaged
>>>>>> heavily
>>>>>>        damaged inode to lost+found dir.
>>>>>>
>>>>>>      repair_inode_no_item():
>>>>>>        Repair case for inode_item missing case, which is quite common
>>>>>> when
>>>>>>        fs tree leaf/node is missing.
>>>>>>        This only does the inode item rebuild. Later recovery like move
>>>>>> it
>>>>>>        to lost+found dir is done by repair_inode_nlinks().
>>>>>>
>>>>>> The main helper is the repair_btree() function, which will drops the
>>>>>> corrupted non-root leaf/node and rebalance the tree to keep the
>>>>>> correctness of the btree.
>>>>> Sounds a bit intrusive, but under the circumstances I don't see anything
>>>>> better to do.
>>>> Better non-destructive but less generic method may be introduced later.
>>>> My dream is to inspect each key and its item to rebuild each member, but
>>>> it
>>>> would takes a long long time
>>>> to implement.
>>>>>
>>>>>> With this patchset, even a non-root leaf/node is corrupted and no
>>>>>> duplication survived, btrfsck can still repair it to a mountable
>>>>>> status.
>>>>>> (And normal rw should also be OK,)
>>>>>>
>>>>>> The remaining unfixable problems will be inode nbytes error with file
>>>>>> extent discounts error, which may be fixed in next patchset.
>>>>>>
>>>>>> Cc David:
>>>>>> Sorry for the huge change in the patchset and merge the old inode nlink
>>>>>> repair with new inode item rebuild patchset.
>>>>> No problem, the incremental changelogs helped a lot.
>>>>>
>>>>>> Since when developing inode item rebuild patchset, I found the old
>>>>>> nlink
>>>>>> cooperated very bad with item rebuild and there is some duplicated
>>>>>> codes
>>>>>> between the two patchset, no to mention the math lib introduced by
>>>>>> nlink
>>>>>> repair patch.
>>>>>> So I decided to somewhat rebase the nlink repair patchset to provide
>>>>>> better generality.
>>>>> Great, the patchset looks good for merge, I'm adding it to 3.18. From
>>>>> now on please send only incremental changes and not the whole patchset.
>>>>> Thanks.
>>>> Thanks, this should be the last large update patchset.
>>>> Later work will focus on file extent recovery and should not interfere
>>>> with
>>>> this patch.
>>>>
>>>> Thanks.
>>>> Qu
>>> Can we please get some tests too?
>>> Add some broken fs images, document what is broken and the expected
>>> result after running the repair code (besides verifying the repair
>>> worked for every single inode of course)...
>>>
>>> thanks
>> Tests are definitely needed, I tested this by randomly corrupt a leaf of
>> fstree, which contains contents of my /etc,
>> and run repair.
>>
>> But the problem is that, we can't add tests like other btrfsck using
>> btrfs-image dump, since it will fail to dump
>> a btree-broken btrfs.
>> And if we add test image directly, it may takes up several MB as a binary
>> image dump.
>>
>> Any good idea about how to add test case without btrfs-image support?
> Very simple solution.
>
> Do:
>
> 1) Create an empty file;
> 2) Use it as the backing file for a loop device;
> 3) Run mkfs.btrfs against the loop device;
> 4) Mount it;
> 5) Populate the fs;
> 6) Umount it;
> 7) Corrupt some nodes or leafs (by zeroing them out for e.g.);
> 8) Create a tarball from the backing file like this: ZX_OPT=-9 tar
> cJSvf foobar.tar.xz run.sh backing_file
> 9) Add the tarball to the fsck-tests directory;
> 10) Make the test run fsck against the backing file extracted from the
> tarball - fsck can operate against regular files, and not only against
> devices.
>
> I did that a couple months ago, see:
>
> http://git.kernel.org/cgit/linux/kernel/git/kdave/btrfs-progs.git/tree/tests/fsck-tests.sh?h=v3.17.x#n30
>
> Exactly because for some kinds of damage in a filesystem btrfs-image won't work.
>
> Thanks.
Oh, thanks for pointing out the fact that btrfs-progs tests can handle 
raw dump image.

I'll try to pick some good size image for it.
(Currently I use 1G file for test, I must find a smaller one)

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

Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and

[David Sterba]

[-- Attachment #1: Type: text/plain, Size: 764 bytes --]

On Fri, Dec 12, 2014 at 08:34:09AM +0000, Filipe David Manana wrote:
> Very simple solution.
> 
> Do:
> 
> 1) Create an empty file;
> 2) Use it as the backing file for a loop device;
> 3) Run mkfs.btrfs against the loop device;
> 4) Mount it;
> 5) Populate the fs;
> 6) Umount it;
> 7) Corrupt some nodes or leafs (by zeroing them out for e.g.);
> 8) Create a tarball from the backing file like this: ZX_OPT=-9 tar
> cJSvf foobar.tar.xz run.sh backing_file
> 9) Add the tarball to the fsck-tests directory;
> 10) Make the test run fsck against the backing file extracted from the
> tarball - fsck can operate against regular files, and not only against
> devices.

I made a few scripts that help to automate most of the steps (no
populating or fuzzing), attached.

[-- Attachment #2: prep-image-1-mkfs-mount --]
[-- Type: text/plain, Size: 507 bytes --]

#!/bin/sh -x

SIZE=64m
MKFS_OPTIONS=
MOUNT_OPTIONS=

mkdir -p mnt
truncate -s0 test.img
truncate -s$SIZE test.img
chmod a+w test.img
LODEV=$(sudo losetup -f --show test.img)
if [ $? -ne 0 ]; then
	echo "Cannot create loop device"
	exit 1
fi

mkfs.btrfs -f $MKFS_OPTIONS $LODEV
sudo mount ${MOUNT_OPTIONS:+-o "$MOUNT_OPTIONS"} $LODEV mnt || { echo "Cannot mount image"; exit 1; }

sudo touch mnt/.btrfs-test-image

echo "Mounted test.img as $LODEV into mnt/"
echo "Populate the image and run the next phase"

[-- Attachment #3: prep-image-2-umount --]
[-- Type: text/plain, Size: 300 bytes --]

#!/bin/sh

LODEV=$(losetup -j test.img -O NAME | tail -n +2)
if [ $? -ne 0 ]; then
	echo "Cannot detect loop devices for test.img"
	exit 1
fi
echo $LODEV

for dev in $LODEV; do
	sudo umount $dev
	sudo losetup -d $dev
done

echo "Unmounted and all loop devices detached"
echo "Corrupt the image now."

[-- Attachment #4: prep-image-3-tar --]
[-- Type: text/plain, Size: 249 bytes --]

#!/bin/sh -x

if ! [ -f test.img ]; then
	echo "No image found"
	exit 1
fi

export ZX_OPT
ZX_OPT=-9 tar cJSvf image.tar.xz --owner=root --group=root test.img

echo "Created image.tar.gz from test.img"
echo "Link it to the test dir, run 'make test'"

Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and

[Qu Wenruo]

The binary image dump is definitely working, but the size still seems 
not so good.... :-(

For my case, 64M contains my /etc copy even after xz with -9 option, the 
size is still about 2.8M. (although
xz is already doing great job).
I know there is even larger btrfs-image dump case here, but several 
megabytes size binary still seems
not so good for me.

But on the other hand, btrfs-image with -c9 dump the uncorrupted fs 
image to less than 200K.
The point is that, I know exactly which leaf I can corrupt to produce 
the corrupted image and in fact,
I am using my leaf corruption patch to do 
it(https://patchwork.kernel.org/patch/5170691/), even
without the patch, I can still figure out where the leaf is and can use 
dd to corrupt the leaf.

So why not change the test cases to following method?
1. Untar the tar.gz, which contains the corruption script + a 
btrfs-image dump.
2. Exec the corruption script to corrupt the image (Of course, 
btrfs-corrupte-image must be able to corrupt it)
3. Do the test.

The trick may be step 2., which means every new repair function should 
have a corresponding corrupt function.

The above is just a advice, I will still submit the binary image dump 
for now.

Thanks,
Qu

-------- Original Message --------
Subject: Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and
From: David Sterba <dsterba@suse.cz>
To: Filipe David Manana <fdmanana@gmail.com>
Date: 2014年12月12日 23:31
> On Fri, Dec 12, 2014 at 08:34:09AM +0000, Filipe David Manana wrote:
>> Very simple solution.
>>
>> Do:
>>
>> 1) Create an empty file;
>> 2) Use it as the backing file for a loop device;
>> 3) Run mkfs.btrfs against the loop device;
>> 4) Mount it;
>> 5) Populate the fs;
>> 6) Umount it;
>> 7) Corrupt some nodes or leafs (by zeroing them out for e.g.);
>> 8) Create a tarball from the backing file like this: ZX_OPT=-9 tar
>> cJSvf foobar.tar.xz run.sh backing_file
>> 9) Add the tarball to the fsck-tests directory;
>> 10) Make the test run fsck against the backing file extracted from the
>> tarball - fsck can operate against regular files, and not only against
>> devices.
> I made a few scripts that help to automate most of the steps (no
> populating or fuzzing), attached.

Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and

[Qu Wenruo]

-------- Original Message --------
Subject: Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink mismatch and
From: Qu Wenruo <quwenruo@cn.fujitsu.com>
To: dsterba@suse.cz, Filipe David Manana <fdmanana@gmail.com>, 
linux-btrfs@vger.kernel.org <linux-btrfs@vger.kernel.org>
Date: 2014年12月15日 09:25
> The binary image dump is definitely working, but the size still seems 
> not so good.... :-(
>
> For my case, 64M contains my /etc copy even after xz with -9 option, 
> the size is still about 2.8M. (although
> xz is already doing great job).
> I know there is even larger btrfs-image dump case here, but several 
> megabytes size binary still seems
> not so good for me.
>
> But on the other hand, btrfs-image with -c9 dump the uncorrupted fs 
> image to less than 200K.
> The point is that, I know exactly which leaf I can corrupt to produce 
> the corrupted image and in fact,
> I am using my leaf corruption patch to do 
> it(https://patchwork.kernel.org/patch/5170691/), even
> without the patch, I can still figure out where the leaf is and can 
> use dd to corrupt the leaf.
>
> So why not change the test cases to following method?
> 1. Untar the tar.gz, which contains the corruption script + a 
> btrfs-image dump.
> 2. Exec the corruption script to corrupt the image (Of course, 
> btrfs-corrupte-image must be able to corrupt it)
> 3. Do the test.
>
> The trick may be step 2., which means every new repair function should 
> have a corresponding corrupt function.
>
> The above is just a advice, I will still submit the binary image dump 
> for now.
>
> Thanks,
> Qu
>
Oh, I'm terribly wrong about the
the 2M+ size binary xz image is a disaster for submitting a patch, 
base64(?) encoded patch grows to
3.6M, I'd better use the btrfs-image dump + custom corrupting script method.

Thanks,
Qu
> -------- Original Message --------
> Subject: Re: [PATCH v4 00/13] btrfs-progs:fsck: Add inode nlink 
> mismatch and
> From: David Sterba <dsterba@suse.cz>
> To: Filipe David Manana <fdmanana@gmail.com>
> Date: 2014年12月12日 23:31
>> On Fri, Dec 12, 2014 at 08:34:09AM +0000, Filipe David Manana wrote:
>>> Very simple solution.
>>>
>>> Do:
>>>
>>> 1) Create an empty file;
>>> 2) Use it as the backing file for a loop device;
>>> 3) Run mkfs.btrfs against the loop device;
>>> 4) Mount it;
>>> 5) Populate the fs;
>>> 6) Umount it;
>>> 7) Corrupt some nodes or leafs (by zeroing them out for e.g.);
>>> 8) Create a tarball from the backing file like this: ZX_OPT=-9 tar
>>> cJSvf foobar.tar.xz run.sh backing_file
>>> 9) Add the tarball to the fsck-tests directory;
>>> 10) Make the test run fsck against the backing file extracted from the
>>> tarball - fsck can operate against regular files, and not only against
>>> devices.
>> I made a few scripts that help to automate most of the steps (no
>> populating or fuzzing), attached.
>