btrfs-progs: remove dead condition for btrfs_map_block

The @search_cache_extent() only returns the next cache_extent or NULL,
it will never return the previous cache_extent.
So just remove the dead condition for previous cache_extent handle.

Signed-off-by: Gui Hecheng <guihc.fnst@cn.fujitsu.com>
Signed-off-by: David Sterba <dsterba@suse.cz>
btrfs-progs: convert: fix unable to rollback case with removed empty block groups

Run fstests: btrfs/012 will fail with message:
	unable to do rollback

It is because the rollback function checks sequentially each piece of space
to map to a certain block group. If some piece doesn't, rollback refuses to continue.

After kernel commit:
	commit 47ab2a6c689913db23ccae38349714edf8365e0a
	Btrfs: remove empty block groups automatically

Empty block groups are removed, so there are possible gaps:

	|--block group 1--|	|--block group 2--|
			     ^
			     |
			    gap

So the piece of space of the gap belongs to a removed empty block group,
and rollback should detect this case, and feel free to continue.

Signed-off-by: Gui Hecheng <guihc.fnst@cn.fujitsu.com>
Signed-off-by: David Sterba <dsterba@suse.cz>
btrfs-progs: Import btrfs_insert/del/lookup_extref() functions.

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

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
Signed-off-by: David Sterba <dsterba@suse.cz>
btrfs-progs: Import lookup/del_inode_ref() function.

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>
Signed-off-by: David Sterba <dsterba@suse.cz>
btrfs-progs: Add last_cache_extent() for extent-cache.

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>
Signed-off-by: David Sterba <dsterba@suse.cz>
btrfs-progs: Record highest inode number before repair.

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>
Signed-off-by: David Sterba <dsterba@suse.cz>
btrfs-progs: Add btrfs_unlink() and btrfs_add_link() functions.

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>
Signed-off-by: David Sterba <dsterba@suse.cz>
btrfs-progs: Add btrfs_mkdir() function for the incoming 'lost+found' fsck mechanism.

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>
Signed-off-by: David Sterba <dsterba@suse.cz>
btrfs-progs: Add count_digits() function to help calculate filename len.

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

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
Signed-off-by: David Sterba <dsterba@suse.cz>
btrfs-progs: Add helper function find_file_name/type for nlink and inode_item repair.

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>
Signed-off-by: David Sterba <dsterba@suse.cz>
btrfs-progs: Add fixing function for inodes whose nlink dismatch

[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>
Signed-off-by: David Sterba <dsterba@suse.cz>
btrfs-progs: record and report leaf/node corruption in fs/subvol tree

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>
Signed-off-by: David Sterba <dsterba@suse.cz>
btrfs-progs: Recover btree by dropping corrupted leaf/node.

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>
Signed-off-by: David Sterba <dsterba@suse.cz>
btrfs-progs: Add inode item rebuild function.

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>
Signed-off-by: David Sterba <dsterba@suse.cz>