[PATCH 0/6] btrfs-progs: New 'lost+found' infrastructrue with

[PATCH 0/6] btrfs-progs: New 'lost+found' infrastructrue with

[Qu Wenruo]

[SUMMARY]
Introduce the new 'lost+found' dir and related infrastructure to create it
in btrfs-progs.

[BUG]
With the new infrastructure, fix a bug that some people reported in both
kernel BZ and maillist, which there is some files' nlink is 1 but backref
points to non-exist parent.
The two reporters all report missing file(chrome config file), so we'd
better not to delete such files but use the 'lost+found' dir.

This bug is a kernel bug needing to be investigated, but the progs fix is
here before kernel fix.

[ROADMAP]
1. Fix the leaf corruption.
Currently, btrfs-progs can ignore corrupt leaf and continue
checking/reparing, however in that case, most problem can't be recovered
since its parent is missing(in corrupted leaf) and we were not able to
move them to someplace due to the missing of 'lost+found' dir.

With this patchset, there is a hope to fix such problems and I will
continue such work until we can fix most of most of the fs.

2. Unify the repair framework.
When writing the 6th patch, I think it is better to build a frame work
that unify the check and repair framework.
In 6th patch, my patchset and Josef's commit 2dc4c001 in fact has some
similar function but do the repair in different time and functions.

I will try to build a unified framework for repair, each repair will be
independent and have its own err number.
And each repair function should work like the following:
1) Check the error number
2) Do the repair
3) Update the related btrfsck record(like newly created inode, deleted inode)

Qu Wenruo (6):
  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 btrfs_unlink() and btrfs_add_link() functions.
  btrfs-progs: Add btrfs_mkdir() function for the incoming 'lost+found' 
       fsck mechanism.
  btrfs-progs: Add fixing function for inodes whose nlink dismatch

 Makefile     |   2 +-
 cmds-check.c | 284 +++++++++++++++++++++++++++++++++++--
 ctree.c      |   6 +
 ctree.h      |  38 +++++
 inode-item.c | 318 +++++++++++++++++++++++++++++++++++++++++
 inode.c      | 453 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 1090 insertions(+), 11 deletions(-)
 create mode 100644 inode.c

-- 
2.1.3

[PATCH 1/6] 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>
---
 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 2/6] 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>
---
 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 3/6] 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>
---
 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 4/6] 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>
---
 Makefile     |   2 +-
 cmds-check.c |   7 +-
 ctree.h      |  12 ++
 inode.c      | 361 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 375 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 9fc1410..6419caf 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..17b3b20 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2444,4 +2444,16 @@ static inline int is_fstree(u64 rootid)
 		return 1;
 	return 0;
 }
+
+/* inode.c */
+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..7305e58
--- /dev/null
+++ b/inode.c
@@ -0,0 +1,361 @@
+/*
+ * 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;
+}
+
+/*
+ * 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;
+
+	ret = btrfs_find_free_dir_index(root, 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 5/6] 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>
---
 ctree.h |  2 ++
 inode.c | 92 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 94 insertions(+)

diff --git a/ctree.h b/ctree.h
index 17b3b20..ec969ab 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2456,4 +2456,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 7305e58..03dece7 100644
--- a/inode.c
+++ b/inode.c
@@ -359,3 +359,95 @@ 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;
+	int ret = 0;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	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_item_key_to_cpu(path->nodes[0], &found_key, path->slots[0]);
+		ret_ino = found_key.objectid;
+		if (btrfs_dir_type(path->nodes[0], dir_item) != BTRFS_FT_DIR)
+			ret = -EEXIST;
+		goto out;
+	}
+
+	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 6/6] 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 delete all the invalid backref,
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>
---
 cmds-check.c | 276 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 272 insertions(+), 4 deletions(-)

diff --git a/cmds-check.c b/cmds-check.c
index 6419caf..2b3263b 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -27,6 +27,7 @@
 #include <unistd.h>
 #include <getopt.h>
 #include <uuid/uuid.h>
+#include <math.h>
 #include "ctree.h"
 #include "volumes.h"
 #include "repair.h"
@@ -1777,6 +1778,73 @@ static int create_inode_item(struct btrfs_root *root,
 	return 0;
 }
 
+/* Check the dir_item/index conflicts before insert */
+static 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)) {
+		ret = PTR_ERR(dir_item);
+		goto out;
+	}
+	if (dir_item) {
+		ret = -EEXIST;
+		goto out;
+	}
+
+out:
+	btrfs_free_path(path);
+	return ret;
+}
+
 static int repair_inode_backrefs(struct btrfs_root *root,
 				 struct inode_record *rec,
 				 struct cache_tree *inode_cache,
@@ -1837,6 +1905,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;
@@ -1874,20 +1954,206 @@ static int repair_inode_backrefs(struct btrfs_root *root,
 	return ret ? ret : repaired;
 }
 
+/*
+ * Search for the inode_ref of given 'ino' to get the filename and
+ * btrfs type.
+ * This will only use the first inode_ref.
+ */
+static int find_file_name_type(struct btrfs_root *root,
+			       struct btrfs_path *path,
+			       u64 ino, char *buf,
+			       int *namelen, u8 *type)
+{
+	struct btrfs_key key;
+	struct btrfs_key found_key;
+	struct btrfs_inode_ref *inode_ref;
+	struct btrfs_inode_item *inode_item;
+	struct extent_buffer *node;
+	u32 ret_namelen;
+	int slot;
+	int ret = 0;
+
+	/* Search for name in backref(Use the first one) */
+	key.objectid = ino;
+	key.type = BTRFS_INODE_REF_KEY;
+	key.offset = 0;
+
+	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
+	if (ret < 0)
+		goto out;
+	node = path->nodes[0];
+	slot = path->slots[0];
+	btrfs_item_key_to_cpu(node, &found_key, slot);
+	if (found_key.objectid != ino ||
+	    found_key.type != BTRFS_INODE_REF_KEY) {
+		ret = -ENOENT;
+		goto out;
+	}
+	inode_ref = btrfs_item_ptr(node, slot, struct btrfs_inode_ref);
+	ret_namelen = btrfs_inode_ref_name_len(node, inode_ref);
+	read_extent_buffer(node, buf, (unsigned long)(inode_ref + 1),
+			   ret_namelen);
+	/* Search for inode type */
+	ret = btrfs_previous_item(root, path, ino, BTRFS_INODE_ITEM_KEY);
+	if (ret) {
+		if (ret > 0)
+			ret = -ENOENT;
+		goto out;
+	}
+	node = path->nodes[0];
+	slot = path->slots[0];
+	inode_item = btrfs_item_ptr(node, slot, struct btrfs_inode_item);
+
+	if (namelen)
+		*namelen = ret_namelen;
+	if (type)
+		*type = imode_to_type(btrfs_inode_mode(node, inode_item));
+out:
+	btrfs_release_path(path);
+	return ret;
+}
+
+
+static int remove_all_invalid_backref(struct btrfs_trans_handle *trans,
+				      struct btrfs_root *root,
+				      struct inode_record *rec)
+{
+	struct inode_backref *backref;
+	struct inode_backref *tmp;
+	int ret = 0;
+
+	list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
+		if (backref->found_dir_item &&
+		    backref->found_inode_ref &&
+		    backref->found_dir_index)
+			continue;
+
+		/*
+		 * We can only handle case that has inode ref but points to
+		 * invalid dir_index/dir_item.
+		 */
+		if (!backref->found_inode_ref)
+			return -ENOENT;
+		ret = btrfs_unlink(trans, root, rec->ino, backref->dir,
+				   backref->index, backref->name,
+				   backref->namelen, 0);
+		if (ret < 0)
+			goto out;
+		list_del(&backref->list);
+		free(backref);
+		rec->nlink--;
+	}
+out:
+	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 ret = 0;
+
+	/*
+	 * Get file name and type first before these invalid inode ref
+	 * are deleted by remove_all_invalid_backref()
+	 */
+	ret = find_file_name_type(root, path, rec->ino, namebuf,
+				  &namelen, &type);
+	if (ret < 0) {
+		fprintf(stderr,
+			"Fail to get file name of inode %llu: %s\n",
+			rec->ino, strerror(-ret));
+		goto out;
+	}
+	ret = remove_all_invalid_backref(trans, root, rec);
+	if (ret < 0) {
+		fprintf(stderr,
+			"Fail to cleanup invalid backref for inode %llu: %s\n",
+			rec->ino, strerror(-ret));
+		goto out;
+	}
+
+	if (rec->found_link == 0) {
+		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 '.' and +1 for log10
+			 */
+			if (namelen + log10(rec->ino) + 2 > BTRFS_NAME_LEN) {
+				ret = -EFBIG;
+				goto out;
+			}
+			snprintf(namebuf + namelen, BTRFS_NAME_LEN - namelen,
+				 ".%llu", rec->ino);
+			namelen += (log10(rec->ino) + 2);
+			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 due to its invalid 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);
@@ -1897,6 +2163,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;
@@ -2032,6 +2300,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)) {
@@ -2044,8 +2314,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

Re: [PATCH 0/6] btrfs-progs: New 'lost+found' infrastructrue with

[David Sterba]

On Mon, Nov 24, 2014 at 05:06:59PM +0800, Qu Wenruo wrote:
> Introduce the new 'lost+found' dir and related infrastructure to create it
> in btrfs-progs.
> 
> [BUG]
> With the new infrastructure, fix a bug that some people reported in both
> kernel BZ and maillist, which there is some files' nlink is 1 but backref
> points to non-exist parent.
> The two reporters all report missing file(chrome config file), so we'd
> better not to delete such files but use the 'lost+found' dir.

Well, I don't like introducing the lost+found directory.

My idea is to extend the rescue utilities to extract the unlinked and
copy them to a user defined directory and do not touch the filesystem.

Or, at least make the in-filesytem lost+found directory creation
optional. You've split the patches well so I'm going to pull 1-5
directly. Patch 6 should be updated a bit, I'll look closer and will let
you know.

> 2. Unify the repair framework.
> When writing the 6th patch, I think it is better to build a frame work
> that unify the check and repair framework.
> In 6th patch, my patchset and Josef's commit 2dc4c001 in fact has some
> similar function but do the repair in different time and functions.
> 
> I will try to build a unified framework for repair, each repair will be
> independent and have its own err number.
> And each repair function should work like the following:
> 1) Check the error number
> 2) Do the repair
> 3) Update the related btrfsck record(like newly created inode, deleted inode)

The unification is most welcome, feel free to send me anything that could be
merged as preparatory work (cleanups, safe changes, etc).

Re: [PATCH 0/6] btrfs-progs: New 'lost+found' infrastructrue with

[Qu Wenruo]

-------- Original Message --------
Subject: Re: [PATCH 0/6] btrfs-progs: New 'lost+found' infrastructrue with
From: David Sterba <dsterba@suse.cz>
To: Qu Wenruo <quwenruo@cn.fujitsu.com>
Date: 2014年11月26日 02:32
> On Mon, Nov 24, 2014 at 05:06:59PM +0800, Qu Wenruo wrote:
>> Introduce the new 'lost+found' dir and related infrastructure to create it
>> in btrfs-progs.
>>
>> [BUG]
>> With the new infrastructure, fix a bug that some people reported in both
>> kernel BZ and maillist, which there is some files' nlink is 1 but backref
>> points to non-exist parent.
>> The two reporters all report missing file(chrome config file), so we'd
>> better not to delete such files but use the 'lost+found' dir.
> Well, I don't like introducing the lost+found directory.
>
> My idea is to extend the rescue utilities to extract the unlinked and
> copy them to a user defined directory and do not touch the filesystem.
Personally, also mentioned by others (maybe Chris?), I think btrfs 
should only have two fsck facilities:
btrfsck for offline check and recovery, and scrub for online check and 
recovery.

So rescue may finally be merged into btrfsck and extending rescue may 
not be a good idea.

Also, such nlink mismatch is not such a huge bug destroying the whole fs 
or making it unable to mount,
end users may not be happy with the fact they need to extra command 
other than btrfsck to fix such
a small problem.
>
> Or, at least make the in-filesytem lost+found directory creation
> optional.
This seems better, but when user gives '--repair' option, they should be 
aware of the fact that the fs
maybe modified by btrfsck.

Still your idea about optional creation of 'lost+found' dir is indeed 
important for end users,
just like e2fsck's annoying but solid prompt.

What about try to prompt user that we are going to modify the fs and ask 
for y/n ?
> You've split the patches well so I'm going to pull 1-5
> directly. Patch 6 should be updated a bit, I'll look closer and will let
> you know.
0004 and 0005 have some small fixes, I'll send the v2 patches soon.

Thanks,
Qu
>
>> 2. Unify the repair framework.
>> When writing the 6th patch, I think it is better to build a frame work
>> that unify the check and repair framework.
>> In 6th patch, my patchset and Josef's commit 2dc4c001 in fact has some
>> similar function but do the repair in different time and functions.
>>
>> I will try to build a unified framework for repair, each repair will be
>> independent and have its own err number.
>> And each repair function should work like the following:
>> 1) Check the error number
>> 2) Do the repair
>> 3) Update the related btrfsck record(like newly created inode, deleted inode)
> The unification is most welcome, feel free to send me anything that could be
> merged as preparatory work (cleanups, safe changes, etc).