Btrfs-progs: fix missing recow roots when making btrfs filesystem

When making btrfs filesystem. we firstly write root leaf to
specified filed, and then we recow the root. If we don't recow,
some trees are not in the correct block group.

Steps to reproduce:
	dd if=/dev/zero of=test.img bs=1M count=100
	mkfs.btrfs -f test.img
	btrfs-debug-tree test.img

extent tree key (EXTENT_TREE ROOT_ITEM 0)
leaf 4210688 items 10 free space 3349 generation 4 owner 2
fs uuid 2e08fd93-f24d-4f44-a226-e2116fcd544f
chunk uuid dc482988-6246-46ce-9329-68bcf6d3683c
	item 0 key (0 BLOCK_GROUP_ITEM 4194304) itemoff 3971 itemsize 24
		block group used 12288 chunk_objectid 256 flags 2
	[..snip..]
	item 3 key (1138688 EXTENT_ITEM 4096) itemoff 3827 itemsize 42
		extent refs 1 gen 1 flags 2
		tree block key (0 UNKNOWN.0 0) level 0
	item 4 key (1138688 TREE_BLOCK_REF 7) itemoff 3827 itemsize 0
		tree block backref
	[..snip..]

checksum tree key (CSUM_TREE ROOT_ITEM 0)
leaf 1138688 items 0 free space 3995 generation 1 owner 7
fs uuid 2e08fd93-f24d-4f44-a226-e2116fcd544f
chunk uuid dc482988-6246-46ce-9329-68bcf6d3683c

For the above example, csum root leaf comes into system block group which
is wrong,csum root leaf should be in metadata block group.

Signed-off-by: Wang Shilong <wangsl-fnst@cn.fujitsu.com>
Reviewed-by: Miao Xie <miaox@cn.fujitsu.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: don't close the file descriptor 0 when closing a device

As we know, the file descriptor 0 is a special number, so we shouldn't
use it to initialize the file descriptor of the devices, or we might
close this special file descriptor by mistake when we close the devices.
"-1" is a better choice.

Signed-off-by: Miao Xie <miaox@cn.fujitsu.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: Don't free the devices when close the ctree

Some commands(such as btrfs-convert) access the devices again after we close
the ctree, so it is better that we don't free the devices objects when the ctree
is closed, or we need re-allocate the memory for the devices. We needn't worry
the memory leak problem, because all the memory will be freed after the taskes
die.

Signed-off-by: Miao Xie <miaox@cn.fujitsu.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: cleanup similar code in open_ctree_* and close_ctree

Signed-off-by: Miao Xie <miaox@cn.fujitsu.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: introduce common insert/search/delete functions for rb-tree

In fact, the code of many rb-tree insert/search/delete functions is similar,
so we can abstract them, and implement common functions for rb-tree, and then
simplify them.

Signed-off-by: Miao Xie <miaox@cn.fujitsu.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: use rb-tree instead of extent cache tree for fs/file roots

Because the fs/file roots are not extents, so it is better to use rb-tree
to manage them. Fix it.

Signed-off-by: Miao Xie <miaox@cn.fujitsu.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: extend the extent cache for the device extent

As we know, btrfs can manage several devices in the same fs, so [offset, size]
is not sufficient for unique identification of an device extent, we need the
device id to identify the device extents which have the same offset and size,
but are not in the same device. So, we added a member variant named objectid
into the extent cache, and introduced some functions to make the extent cache
be suitable to manage the device extent.

Signed-off-by: Miao Xie <miaox@cn.fujitsu.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: Add block group check funtion

This patch adds the function to check correspondence between block group,
chunk and device extent.

Original-signed-off-by: Cheng Yang <chenyang.fnst@cn.fujitsu.com>
Signed-off-by: Miao Xie <miaox@cn.fujitsu.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: Add chunk recover function - using old chunk items

Add chunk-recover program to check or rebuild chunk tree when the system
chunk array or chunk tree is broken.

Due to the importance of the system chunk array and chunk tree, if one of
them is broken, the whole btrfs will be broken even other data are OK.

But we have some hint(fsid, checksum...) to salvage the old metadata.
So this function will first scan the whole file system and collect the
needed data(chunk/block group/dev extent), and check for the references
between them. If the references are OK, the chunk tree can be rebuilt and
luckily the file system will be mountable.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
Signed-off-by: Miao Xie <miaox@cn.fujitsu.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: introduce list_{first, next}_entry/list_splice_tail{_init}

Signed-off-by: Miao Xie <miaox@cn.fujitsu.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: Add chunk rebuild function for RAID1/SINGLE/DUP

Add chunk rebuild for RAID1/SINGLE/DUP to chunk-recover command.

Before this patch chunk-recover can only scan and reuse the old chunk
data to recover. With this patch, chunk-recover can use the reference
between chunk/block group/dev extent to rebuild the whole chunk tree
even when old chunks are not available.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
Signed-off-by: Miao Xie <miaox@cn.fujitsu.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: recover raid0/raid10/raid5/raid6 metadata chunk

According to the bytenr of the extent buffer record, we can calculate the index
of the stripes, and we also know which device and where we read out the extent
buffer record, that means we can know the relationship between the device extent
and the stripes in the chunk, by this relationship, we can recover the raid0/radi10/
raid5/raid6 metadata chunk.

Signed-off-by: Miao Xie <miaox@cn.fujitsu.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: fix misuse of skinny metadata in btrfs-image

As for skinny metadata, key.offset stores levels rather than extent length.

Signed-off-by: Liu Bo <bo.li.liu@oracle.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: skip open devices which is missing

A device can be added to the device list without getting a name, so we may
access to illegal addresses while opening devices with their name.

Signed-off-by: Liu Bo <bo.li.liu@oracle.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: delete fs_devices itself from fs_uuid list before freeing

Otherwise we will access illegal addresses while searching on fs_uuid list.

Signed-off-by: Liu Bo <bo.li.liu@oracle.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: cleanup btrfs-image usage

A '\n' is missing.

Signed-off-by: Liu Bo <bo.li.liu@oracle.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: enhance btrfs-image to restore image onto multiple disks

This adds a 'btrfs-image -m' option, which let us restore an image that
is built from a btrfs of multiple disks onto several disks altogether.

This aims to address the following case,
$ mkfs.btrfs -m raid0 sda sdb
$ btrfs-image sda image.file
$ btrfs-image -r image.file sdc
---------
so we can only restore metadata onto sdc, and another thing is we can
only mount sdc with degraded mode as we don't provide informations of
another disk.  And, it's built as RAID0 and we have only one disk,
so after mount sdc we'll get into readonly mode.

This is just annoying for people(like me) who're trying to restore image
but turn to find they cannot make it work.

So this'll make your life easier, just tap
$ btrfs-image -m image.file sdc sdd
---------
then you get everything about metadata done, the same offset with that of
the originals(of course, you need offer enough disk size, at least the disk
size of the original disks).

Besides, this also works with raid5 and raid6 metadata image.

Signed-off-by: Liu Bo <bo.li.liu@oracle.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Merge branch 'liubo-image-restore'

Signed-off-by: Chris Mason <chris.mason@fusionio.com>

Conflicts:
	disk-io.c
	volumes.h
Btrfs-progs: fix closing of devices

If a device could not be opened in volumes.c:read_one_dev(), a
btrfs_device instance was allocated and added to the list of
devices of the fs - however this device instance had its fd,
name and label fields not initialized. This is problematic in
disk-io.c:close_all_devices() as it tried to sync, fadvise and
close the (invalid) fd of the device, and kfree() its name and
label, which pointed to random memory locations.

  Thread 1 (Thread 0x7f0a3d2d1740 (LWP 23585)):
  #0  __GI___libc_free (mem=0xa5a5a5a5a5a5a5a5) at malloc.c:2970
  #1  0x000000000042054b in close_all_devices (fs_info=0x1e92bf0) at disk-io.c:1276
  #2  0x0000000000421dcd in close_ctree (root=<optimized out>) at disk-io.c:1336
  #3  0x0000000000418cfa in cmd_check (argc=<optimized out>, argv=<optimized out>) at cmds-check.c:4171
  #4  0x0000000000403ed4 in main (argc=2, argv=0x7fff9a583d28) at btrfs.c:295

v2: Added Liu Bo's review mention.

Reviewed-by: Liu Bo <bo.li.liu@oracle.com>
Signed-off-by: Filipe David Borba Manana <fdmanana@gmail.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
btrfsck: fix incorrect casting on items in the corrupt_blocks tree

check_extent_refs is pinning down all the corrupt tree blocks it finds,
but it is incorrectly casting these to an extent_record first.

Signed-off-by: Chris Mason <chris.mason@fusionio.com>