For a directory tree:

/mnt/subvolA/subvolB

btrfsctl -s /mnt/subvolA/subvolB /mnt

Will create a directory loop with subvolA under subvolB.  This
commit uses the forward refs for each subvol and snapshot to error out
before creating the loop.
Signed-off-by: NChris Mason <chris.mason@oracle.com>

Subvols and snapshots can now be referenced from any point in the directory
tree.  We need to maintain back refs for them so we can find lost
subvols.

Forward refs are added so that we know all of the subvols and
snapshots referenced anywhere in the directory tree of a single subvol.  This
can be used to do recursive snapshotting (but they aren't yet) and it is
also used to detect and prevent directory loops when creating new snapshots.
Signed-off-by: NChris Mason <chris.mason@oracle.com>

This improves the comments at the top of many functions.  It didn't
dive into the guts of functions because I was trying to
avoid merging problems with the new allocator and back reference work.

extent-tree.c and volumes.c were both skipped, and there is definitely
more work todo in cleaning and commenting the code.
Signed-off-by: NChris Mason <chris.mason@oracle.com>

This patch updates the space balancing code to utilize the new
backref format.  Before, btrfs-vol -b would break any COW links
on data blocks or metadata.  This was slow and caused the amount
of space used to explode if a large number of snapshots were present.

The new code can keeps the sharing of all data extents and
most of the tree blocks.

To maintain the sharing of data extents, the space balance code uses
a seperate inode hold data extent pointers, then updates the references
to point to the new location.

To maintain the sharing of tree blocks, the space balance code uses
reloc trees to relocate tree blocks in reference counted roots.
There is one reloc tree for each subvol, and all reloc trees share
same root key objectid. Reloc trees are snapshots of the latest
committed roots of subvols (root->commit_root).

To relocate a tree block referenced by a subvol, there are two steps.
COW the block through subvol's reloc tree, then update block pointer in
the subvol to point to the new block. Since all reloc trees share
same root key objectid, doing special handing for tree blocks
owned by them is easy. Once a tree block has been COWed in one
reloc tree, we can use the resulting new block directly when the
same block is required to COW again through other reloc trees.
In this way, relocated tree blocks are shared between reloc trees,
so they are also shared between subvols.
Signed-off-by: NChris Mason <chris.mason@oracle.com>

File syncs and directory syncs are optimized by copying their
items into a special (copy-on-write) log tree.  There is one log tree per
subvolume and the btrfs super block points to a tree of log tree roots.

After a crash, items are copied out of the log tree and back into the
subvolume.  See tree-log.c for all the details.
Signed-off-by: NChris Mason <chris.mason@oracle.com>

This trivial patch contains two locking fixes and a off by one fix.

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

btrfs_find_dead_roots called btrfs_read_fs_root_no_radix, which
means we end up calling btrfs_search_slot with a path already held.

The fix is to remember the key inside btrfs_find_dead_roots and drop
the path.
Signed-off-by: NChris Mason <chris.mason@oracle.com>

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

Some programs (python) do rwm cycles at the granularity returned by
stat.
Signed-off-by: NChris Mason <chris.mason@oracle.com>

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

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

Dead roots are trees left over after a crash, and they were either in the
process of being removed or were waiting to be removed when the box crashed.
Before, a search of the entire tree of root pointers was done on mount
looking for dead roots.  Now, the search is done the first time we load
a root.

This makes mount faster when there are a large number of snapshots, and it
enables the block accounting code to properly update the block counts on
the latest root as old versions of the root are reaped after a crash.
Signed-off-by: NChris Mason <chris.mason@oracle.com>

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

Almost none of the files including module.h need to do so,
remove them.

Include sched.h in extent-tree.c to silence a warning about cond_resched()
being undeclared.
Signed-off-by: NZach Brown <zach.brown@oracle.com>
Signed-off-by: NChris Mason <chris.mason@oracle.com>

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

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

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

Attaching below is some of the code cleanups that i came across while
reading the code.

a) alloc_path already calls init_path.
b) Mention that btrfs_inode is the in memory copy.Ext4 have ext4_inode_info as
the in memory copy ext4_inode as the disk copy
Signed-off-by: NChris Mason <chris.mason@oracle.com>

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

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

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

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

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

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

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

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

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

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

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

Add (untested and simple) directory item code
Fix comp_keys to use the new key ordering
Add btrfs_insert_empty_item
Signed-off-by: NChris Mason <chris.mason@oracle.com>

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

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