Btrfs-image: add the ability to santize file names when making an image

We've had a few users who wouldn't (or couldn't) provide us btrfs-images because
we maintain the file names when making an image.  So introduce a sanitize
option.  There are two uses, one that is fast and the other that is dog slow.
The fast way just generates garbage that's equal in length to the original name.
The slow way will try and find a crc32c collision for the file name that is also
the same length.  Finding a crc32c collision for the file name "btrfs-progs" on
my box without CPU crc32c support takes a little more than 3 minutes, and a
little less than 2 minutes for my box that has CPU crc32c support, so it's a
lengthy and CPU intensive process.

The idea is that we use -s for most cases, and then only use -ss when we need
the file system tree to be somewhat sane.  I could probably do a better job
about finding collisions, but I'll have to revist that later.  Thanks,

Signed-off-by: Josef Bacik <jbacik@fusionio.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: make fsck fix certain file extent inconsistencies

The tree log bug I introduced could create inconsistent file extent entries in
the file system tree and in some worst cases even create multiple extent entries
for the same entry.  To fix this we need to do a few things

1) Keep track of extent items that overlap and then pick the one that covers the
largest area and delete the rest of the items.

2) Keep track of file extent items that land in extent items but don't match
disk_bytenr/disk_num_bytes exactly.  Once we find these we need to figure out
who is the right ref and then fix all of the other refs to agree.

Each of these cases require a complete rescan of all of the extents, so
unfortunately if you hit this particular problem the fsck is going to take quite
a while since it will likely rescan all the trees 2 or 3 times.  With this patch
the broken file system a user sent me is fixed and a broken file system that was
created by my reproducer is also fixed.  Thanks,

Signed-off-by: Josef Bacik <jbacik@fusionio.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: pass properly formated key to read_fs_root

We have a BUG_ON() in read_fs_root that expects key->offset == (u64)-1.  Restore
will just pass in the location it reads out of the inode if it has a subvol
reference and pass that in, which doesn't have offset == (u64)-1, so it causes
restore blow up.  This was reported in bugzilla and this patch fixed the
problem.  Thanks,

Signed-off-by: Josef Bacik <jbacik@fusionio.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: make image restore with the original device offsets

I noticed a slight problem with btrfs-image, since it was building a chunk tree
by setting the physical offset of the stripes to the same as the logical offset
it created this problem where the super block was now mapped into the file
system differently than it was before.  This isn't a huge deal except that we
also carry along the free space cache with us, which is setup with the idea that
super at physical X is at logical Y.  So this would make the free space checker
in fsck freak out because it would see that the cache says that the super block
is free space, and that the area where it thought the super block was located is
in fact used.  In the mount case we'd end up overwriting real metadata with
backup super blocks.  So we need to maintain the physical offsets in our
stripes.  This is a huge pain because we store the logical bytenrs of all of our
metadata.  This patch scans the entire image looking for chunk tree blocks and
builds an in memory chunk tree so we can write logical blocks to their physical
offsets.  With this patch we no longer have the problems I described above.
Thanks,

Signed-off-by: Josef Bacik <jbacik@fusionio.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: add a newline to a free space cache message

Left out a newline in the generation check printf.

Signed-off-by: Josef Bacik <jbacik@fusionio.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: add --init-extent-tree to btrfsck

In some cases the extent tree can just be so gone there is no point in trying to
figure out how to put it back together.  So add a --init-extent-tree mode which
will zero out the extent tree and then re-add extents for all of the blocks we
find.  This will also undo any balance that was going on at the time of the
crash, this is needed because the reloc tree seems to confuse fsck at the
moment.  With this patch I can put back together a users file system that was
completely gone.  Thanks,

Signed-off-by: Josef Bacik <jbacik@fusionio.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: fix free space cache checks

This fixes two bugs with the free space cache checker.  First is we apparently
always use root->sectorsize for our unit in the kernel so we have to do that in
progs otherwise bitmaps turn out to not look right if we have leafsize !=
sectorsize.  The second is a small issue if we had skinny metadata extents set,
we wouldn't advance last properly because we unconditionally use key.offset
instead of root->leafsize.  Thanks,

Signed-off-by: Josef Bacik <jbacik@fusionio.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: fix the allocator

The allocator looks for these hints when moving on to another block group which
will make it reset which block group it looks at, when we've already searched
that block group and didn't find any space to allocate, we need to fix this by
just letting the allocator make the determination if the block group is good
enough.  This also fixes a problem where if we couldn't find space in the block
group we were given we'd just error out instead of moving on to the next block
group.  Previously I couldn't fix some file systems that were relatively full,
but with this patch I can now run fsck on them with no allocation errors.
Thanks,

Signed-off-by: Josef Bacik <jbacik@fusionio.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: fix fsck dealing with finding backrefs first

There is a problem where if we find a backref extent record first that doesn't
match a extent item we will delete some of the duplicates but not others.  In
order to deal with this we need to make sure we only pay attention to duplicates
that actually have duplicate extent items.  If a extent_rec has a duplicate but
the record itself doesn't have an associated extent item we promote the
duplicate to the extent record and just discard the original extent_rec since it
was just added by the backref.  We copy the backref onto the promoted extent
record and then continue processing.  This allowed me to fix a file system that
previously was not able to be fixed by fsck.  Thanks,

Signed-off-by: Josef Bacik <jbacik@fusionio.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: fix incorrect root backref errors in fsck

A user reported that fsck was complaining about unresolved refs for some
snapshots.  You can reproduce this by doing

mkfs.btrfs /dev/sdb
mount /dev/sdb /mnt
btrfs subvol snap /mnt/ /mnt/a
btrfs subvol snap /mnt/ /mnt/b
btrfs subvol del /mnt/a
umount /mnt
btrfsck /dev/sdb

and you'd get this

unresolved ref root 258 dir 256 index 2 namelen 1 name a error 600

because snapshot b has a dir item that points to a.  Except we encode in our
root ref the dirid of the ref holder, and if it doesn't match we just give it
back a empty directory since we can't hardlink directories.  This makes the
check in btrfsck bogus, when we delete a we remove the ref key for it so any
lookups into /mnt/b/a will just give a blank directory as it's supposed to.  Fix
this by only saying the backref is reachable if there is both a DIR_ITEM and a
REF_KEY for the given root.  With this patch I no longer see errors when running
this reproducer.  Thanks,

Signed-off-by: Josef Bacik <jbacik@fusionio.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Btrfs-progs: fix reference check for roots in btrfsck

I noticed that I was getting these errors on a bigger file system with more
snapshots that had been removed.  This check is bogus since we won't inc
rec->found_ref if we don't find a REF_KEY _and_ a DIR_ITEM, so we only have to
worry about there being no references to a root if it actually has a root item.
If it doesn't then it's just referenced by things that will go no where anyway.
With this patch fsck no longer incorrectly complains about this file system
image I have.  Thanks,

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