Btrfs: update converter for the new disk format

This patch updates the ext3 to btrfs converter for the new
disk format. This mainly involves changing the convert's
data relocation and free space management code. This patch
also ports some functions from kernel module to btrfs-progs.
Thank you,

Signed-off-by: Yan Zheng <zheng.yan@oracle.com>

Btrfs: Add inode sequence number for NFS and reserved space in a few structs

This adds a sequence number to the btrfs inode that is increased on
every update.  NFS will be able to use that to detect when an inode has
changed, without relying on inaccurate time fields.

While we're here, this also:

Puts reserved space into the super block and inode

Adds a log root transid to the super so we can pick the newest super
based on the fsync log as well as the main transaction ID.  For now
the log root transid is always zero, but that'll get fixed.

Adds a starting offset to the dev_item.  This will let us do better
alignment calculations if we know the start of a partition on the disk.

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

superblock duplication

This patch updates btrfs-progs for superblock duplication.
Note: I didn't make this patch as complete as the one for
kernel since updating the converter requires changing the
code again. Thank you,

Signed-off-by: Yan Zheng <zheng.yan@oracle.com>

Btrfs: move data checksumming into a dedicated tree

Btrfs stores checksums for each data block.  Until now, they have
been stored in the subvolume trees, indexed by the inode that is
referencing the data block.  This means that when we read the inode,
we've probably read in at least some checksums as well.

But, this has a few problems:

* The checksums are indexed by logical offset in the file.  When
compression is on, this means we have to do the expensive checksumming
on the uncompressed data.  It would be faster if we could checksum
the compressed data instead.

* If we implement encryption, we'll be checksumming the plain text and
storing that on disk.  This is significantly less secure.

* For either compression or encryption, we have to get the plain text
back before we can verify the checksum as correct.  This makes the raid
layer balancing and extent moving much more expensive.

* It makes the front end caching code more complex, as we have touch
the subvolume and inodes as we cache extents.

* There is potentitally one copy of the checksum in each subvolume
referencing an extent.

The solution used here is to store the extent checksums in a dedicated
tree.  This allows us to index the checksums by phyiscal extent
start and length.  It means:

* The checksum is against the data stored on disk, after any compression
or encryption is done.

* The checksum is stored in a central location, and can be verified without
following back references, or reading inodes.

This makes compression significantly faster by reducing the amount of
data that needs to be checksummed.  It will also allow much faster
raid management code in general.

The checksums are indexed by a key with a fixed objectid (a magic value
in ctree.h) and offset set to the starting byte of the extent.  This
allows us to copy the checksum items into the fsync log tree directly (or
any other tree), without having to invent a second format for them.

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

Rev the disk format for the compat code and the csum selection

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

btrfs-progs: support for different csum algorithims

This is the btrfs-progs version of the patch to add the ability to have
different csum algorithims.  Note I didn't change the image maker since it
seemed a bit more complicated than just changing some stuff around so I will let
Yan take care of that.

Everything else was converted and for now a mkfs just
sets the type to be BTRFS_CSUM_TYPE_CRC32.

Signed-off-by: Josef Bacik <jbacik@redhat.com>

btrfs-progs: add support for compat flags

This patch updates btrfs-progs with the disk format changes for the
compatability flags.

Signed-off-by: Josef Bacik <jbacik@redhat.com>

Fix image tool compile warnings

Btrfs image tool

This patch adds btrfs image tool. The image tool is
a debugging tool that creates/restores btrfs metadump
image.

Signed-off-by: Yan Zheng <zheng.yan@oracle.com>

Update the super magic string to match the seed and root format changes

Add disk format requirements for subvol backward and forward refs

Modify the subvol and snapshot creation ioctls to work anywhere in the tree

This changes the snapshot and subvol ioctl API and command lines so
that new snapshots and subvols can be created anywhere.

Subvolume creation hasn't changed much:

btrfsctl -S subvol_name directory

This creates a new subvolume under 'directory'

Snapshot creation looks the same, but is actually different:

btrfsctl -s full_path_to_new_snapshot file_or_dir

For example: btrfsctl -s /mnt/new_snap /mnt/subvol

Will create a new snapshot named new_snap under /mnt of the root
found in /mnt/subvol.  It always snapshots the entire root regardless of
which file or directory inside the root you give it.

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

update btrfs-progs for seed device support

This patch does the following:

1) Update device management code to match the kernel code.

2) Allocator fixes.

3) Add a program called btrfstune to set/clear the SEEDING
   super block flags.

Add fallocate support v2

This patch updates btrfs-progs for fallocate support.

Signed-off-by: Yan Zheng <zheng.yan@oracle.com>

Avoid tree of tree root cow when committing a clean FS

The root node generation number code made commit_tree_root look like the
kernel code.  It forces a cow of the tree of tree roots even when
the FS hasn't changed.

This causes errors during fsck and other readonly operations.  This adds
a check to see if commit_tree_root is going to trigger writes to the
tree of tree roots, and bails if none are pending.

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

Rev the disk format for compression and root pointer generation fields

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

Add root tree pointer transaction ids

This patch adds transaction IDs to root tree pointers.
Transaction IDs in tree pointers are compared with the
generation numbers in block headers when reading root
blocks of trees. This can detect some types of IO errors.

Signed-off-by: Yan Zheng <zheng.yan@oracle.com>

Add disk format elements for compression

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

Rev the disk format for the new back reference format

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

Count space allocated to file in bytes

This patch updates btrfs-progs for counting space
allocated to file in bytes.

Signed-off-by: Yan Zheng <zheng.yan@oracle.com>

Remove offset field from struct btrfs_extent_ref

The offset field in struct btrfs_extent_ref records the position
inside file that file extent is referenced by. In the new back
reference system, tree leaves holding reference to file extent
are recorded explicitly. We can quickly scan these tree leaves, so the
offset field is not required.

This patch also makes the back reference system check the objectid
when extents are being deleted

Signed-off-by: Yan Zheng <zheng.yan@oracle.com>

update mkfs.btrfs for the new space balancing code

The new space balancing code needs a subvol to store the
temporary inode for data extent relocation.

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

Full back reference support

This patch makes the back reference system to explicit record the
location of parent node for all types of extents. The location of
parent node is placed into the offset field of backref key. Every
time a tree block is balanced, the back references for the affected
lower level extents are updated.

Disk format changes required for write ahead tree log

Rev the disk format

Switch btrfs_name_hash() to crc32c

Date: Tue, 19 Aug 2008 19:21:22 +0100
Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>

Use git for version number too

Date: Tue, 19 Aug 2008 18:57:17 +0100
Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>

fix btrfs-progs version script

btrfs-progs-0.16.tar.bz2 seems to be distributed w/o an .hg,
which make the version.sh script go bonk.

Signed-off-by: Eric Sandeen <sandeen@redhat.com>
---

Added tag v0.16 for changeset 2b26e4f8c71e

Update version.sh to v0.16

btrfs-convert: Iterate correctly using libext2fs functions

This patch corrects open-coded inode_map iteration, which happens to be
illegal in new libext2fs due to inode_map being private, causing warning,
which becomes a compile error.

Cleanup btrfsctl help message

Many options were not mentioned in the usage message, fix that and
cleaning up the brackets

Signed-Off-By: Ahmed Kamal <email.ahmedkamal@googlemail.com>

Fix: btrfsctl arguments handling

btrfsctl -A
in the current -unstable branch, does not result in the error message
designated for it, namely "-A requires an arg\n"

btrfs-convert new dir index support

This patch updates btrfs-convert for the new dir index format.

btrfs-progs: add orphan support to print-tree

This adds orphan support to print-tree so when debug_tree hits an orphan item it
will print out "orphan item" under it so you know what it is

Rev the disk format

btrfs-progs new dir index support

Print the version string in a few programs

Add version strings

Add .hgignore file to ignore verison.h

Add sync and transaction ioctl defs

btrfsctl -c forces a single FS sync

The transaction ioctls are unsafe for general use because they can lead
to deadlocks if the application is not very careful.  But, ceph is
experimenting with btrfs as a backing store, and these ioctls are required
for testing.

btrfsctl: print usage when called with bad args

Added tag v0.15 for changeset e6571e2ce0c8

Verify parent generation number on btree reads

Pass down the expected generation number when reading tree blocks

Fix the pretty print code for num_bytes == 0

Add a readonly flag open_ctree to force RO opens

bcp updates for single file copies

Add bcp to test the clone file ioctl

Fix compiler warning in volumes.c

Add the clone ioctl number

Fix uninitialized variables, and use -O so gcc starts checking for them

Gcc only sends warnings for uninitialized variables when you compile with -O,
and there were a couple of bugs sprinkled in the code.  The biggest was the
alloc_start variable for mkfs, which can cause strange things to happen.

(thanks to Gabor Micsko for helping to find this)

Added tag v0.14 for changeset 969099968b60

Fix btrfs-convert's large file support.

This patch add ext2_inode.i_size_high into account when calculating regular
file's size in btrfs-convert,  which makes it deal with large files bigger than
4GB properly.

Add btrfs-vol command to balance, add and (eventually) remove devices

Add mkfs.btrfs -A offset to control allocation start on devices

This is a utility option for the resizer, it makes sure to allocate
at offset bytes in the disk or higher.  It ensures the resizer will have
something to move when testing it.

Speed improvement and bug fixes for ext3 converter

This patch improves converter's allocator and fixes a bug in data relocation
function. The new allocator caches free blocks as Btrfs's default allocator.
In testing here, the user CPU time reduced to half of the original when
checksum and small file packing was disabled. This patch also enlarges the
size of block groups created by the converter.

Fix balance_level to free the middle block if there is room in the left one

balance level starts by trying to empty the middle block, and then
pushes from the right to the middle.  This might empty the right block
and leave a small number of pointers in the middle.

Don't empty the middle buffer in push_nodes_for_insert

Keep more pointers free in the nodes for double splits

Drop quick-test from the list of programs built by default

Update the Ext3 converter

The main changes in this patch are adding chunk handing and data relocation
ability. In the last step of conversion, the converter relocates data in system
chunk and move chunk tree into system chunk. In the rollback process, the
converter remove chunk tree from system chunk and copy data back.

Regards
YZ
---

Add a command to show all of the btrfs filesystems on the box (btrfs-show)

Fix chunk allocation when some devices don't have enough room for the stripe

Add checks to avoid adding the same device twice during mkfs

Use better chunk sizes for small and large filesystems

Add support for filesystem labels via mkfs.btrfs -L

Use device uuids when scanning devices

Add raid10 support

Add chunk uuids and update multi-device back references

Block headers now store the chunk tree uuid

Chunk items records the device uuid for each stripes

Device extent items record better back refs to the chunk tree

Block groups record better back refs to the chunk tree

The chunk tree format has also changed.  The objectid of BTRFS_CHUNK_ITEM_KEY
used to be the logical offset of the chunk.  Now it is a chunk tree id,
with the logical offset being stored in the offset field of the key.

This allows a single chunk tree to record multiple logical address spaces,
upping the number of bytes indexed by a chunk tree from 2^64 to
2^128.

Fix up the quick btree code test program

Fix a few casts for 32 bit compile

Write all super blocks during commit

Retry metadata reads in the face of checksum failures

Change btrfs_map_block to return a structure with mappings for all stripes

Don't allow written blocks from this transaction to be reallocated

When a block is freed, it can be immediately reused if it is from
the current transaction.  But, an extra check is required to make sure
the block had not been written yet.  If it were reused after being written,
the transid in the block header might match the transid of the
next time the block was allocated.

The parent node records the transaction ID of the block it is pointing to,
and this is used as part of validating the block on reads.  So, there
can only be one version of a block per transaction.

Use leafsize and nodesize == pagesize for now

Recow all roots at the end of mkfs

The mkfs code bootstraps the filesystem on a single device.  Once
the raid block groups are setup, it needs to recow all of the blocks so
that each tree is properly allocated.

Add mkfs options for data and metadata mirroring modes

mkfs.btrfs --data {raid0,raid1,single}
mkfs.btrfs --metadata {raid0,raid1,single}

In single mode, no extra duplication or striping is done.
In raid0 mode, blocks are spread across all of the available devices
In raid1 mode, blocks are mirrored across two devices.

For metadata, if raid1 is used and there is only one device, the
metadata is duplicated on that single spindle.

The defaults are raid0 for data and raid1 for metadata

Add support for single single duplication of metadata

Add mirroring support across multiple drives

Use getopt_long and introduce long mkfs options.  -s now means --sectorsize

btrfs-progs: Fix printf format casting errors

We get lots of warnings of the flavor:

utils.c:441: warning: format '%Lu' expects type 'long long unsigned int' but argument 2 has type 'u64'

And thanks to -Werror, the build fails. Clean up these printfs
by properly casting the arg to the format specified.

Signed-off-by: Alex Chiang <achiang@hp.com>

btrfs-progs: Stop stomping on 'name' input parameter

In btrfs_name_hash, Local variable 'buf' is declared as

__u32 buf[2];

but we then try to do this:

buf[0] = 0x67452301;
buf[1] = 0xefcdab89;
buf[2] = 0x98badcfe;
buf[3] = 0x10325476;

Oops. Fix buf to be the proper size.

Signed-off-by: Alex Chiang <achiang@hp.com>

check if partition is mounted before mkfs

This saves from the blunder of formatting a live mounted filesystem.
This can be extended to get the mount flags of the filesystem
mounted.

Signed-off-by: Goldwyn Rodrigues <rgoldwyn@gmail.com>

Update struct btrfs_header flags, and use it to indicate buffers are written

Implement raid0 when multiple devices are present

This defaults to striping across all devices

Walk all block devices looking for btrfs

ioctls to scan for btrfs filesystems

Btrfsck updates for multi-device filesystems

Dynamic chunk allocation

Add support for multiple devices per filesystem

Remove extent back refs in batches, and avoid duplicate searches

Add debugging for block group update failure

Call btrfs_cow_block while lowering tree level.

When freeing root block of a tree,  btrfs_free_extent' parameter
'ref_generation' is from root block itseft.  When freeing non-root
block,  'ref_generation' is from its parent. so when converting a
non-root block to root block, we must guarantee its generation is
equal to its parent's generation.

Insert extent record and the first backref in a single balance

Copy correct tree when inserting into slot 0

Add inode item and backref in one insert, reducing cpu usage

During deletes and truncate, remove many items at once from the tree

Add some extra debugging around file data checksum failures