[PATCH 00/12] btrfs: remap tree

[Mark Harmstone <maharmstone@fb.com>]

This patch series adds a disk format change gated behind
CONFIG_BTRFS_EXPERIMENTAL to add a "remap tree", which acts as a layer of
indirection when doing I/O. When doing relocation, rather than fixing up every
tree, we instead record the old and new addresses in the remap tree. This should
hopefully make things more reliable and flexible, as well as enabling some
future changes we'd like to make, such as larger data extents and reducing
write amplification by removing cow-only metadata items.

The remap tree lives in a new REMAP chunk type. This is because bootstrapping
means that it can't be remapped itself, and has to be relocated by COWing it as
at present. It can't go in the SYSTEM chunk as we are then limited by the chunk
item needing to fit in the superblock.

For more on the design and rationale, please see my RFC sent last month[1], as
well as Josef Bacik's original design document[2]. The main change from Josef's
design is that I've added remap backrefs, as we need to be able to move a
chunk's existing remaps before remapping it.

You will also need my patches to btrfs-progs[3] to make
`mkfs.btrfs -O remap-tree` work, as well as allowing `btrfs check` to recognize
the new format.

Changes since the RFC:

* I've reduce the REMAP chunk size from the normal 1GB to 32MB, to match the
  SYSTEM chunk. For a filesystem with 4KB sectors and 16KB node size, the worst
  case is that one leaf covers ~1MB of data, and the best case ~250GB. For a
  chunk, that implies a worst case of ~2GB and a best case of ~500TB.
  This isn't a disk-format change, so we can always adjust it if it proves too
  big or small in practice. mkfs creates 8MB chunks, as it does for everything.

* You can't make new allocations from remapped block groups, so I've changed
  it so there's no free-space entries for these (thanks to Boris Burkov for the
  suggestion).

* The remap tree doesn't have metadata items in the extent tree (thanks to Josef
  for the suggestion). This was to work around some corruption that delayed refs
  were causing, but it also fits it with our future plans of removing all
  metadata items for COW-only trees, reducing write amplification.
  A knock-on effect of this is that I've had to disable balancing of the remap
  chunk itself. This is because we can no longer walk the extent tree, and will
  have to walk the remap tree instead. When we remove the COW-only metadata
  items, we will also have to do this for the chunk and root trees, as
  bootstrapping means they can't be remapped.

* btrfs_translate_remap() uses search_commit_root when doing metadata lookups,
  to avoid nested locking issues. This also seems to be a lot quicker (btrfs/187
  went from ~20mins to ~90secs).

* Unused remapped block groups should now get cleaned up more aggressively

* Other miscellaneous cleanups and fixes

Known issues:

* Relocation still needs to be implemented for the remap tree itself (see above)

* Some test failures: btrfs/156, btrfs/170, btrfs/226, btrfs/250

* nodatacow extents aren't safe, as they can race with the relocation thread.
  We either need to follow the btrfs_inc_nocow_writers() approach, which COWs
  the extent, or change it so that it blocks here.

* When initially marking a block group as remapped, we are walking the free-
  space tree and creating the identity remaps all in one transaction. For the
  worst-case scenario, i.e. a 1GB block group with every other sector allocated
  (131,072 extents), this can result in transaction times of more than 10 mins.
  This needs to be changed to allow this to happen over multiple transactions.

* All this is disabled for zoned devices for the time being, as I've not been
  able to test it. I'm planning to make it compatible with zoned at a later
  date.

Thanks

[1] https://lwn.net/Articles/1021452/
[2] https://github.com/btrfs/btrfs-todo/issues/54
[3] https://github.com/maharmstone/btrfs-progs/tree/remap-tree

Mark Harmstone (12):
  btrfs: add definitions and constants for remap-tree
  btrfs: add REMAP chunk type
  btrfs: allow remapped chunks to have zero stripes
  btrfs: remove remapped block groups from the free-space tree
  btrfs: don't add metadata items for the remap tree to the extent tree
  btrfs: add extended version of struct block_group_item
  btrfs: allow mounting filesystems with remap-tree incompat flag
  btrfs: redirect I/O for remapped block groups
  btrfs: handle deletions from remapped block group
  btrfs: handle setting up relocation of block group with remap-tree
  btrfs: move existing remaps before relocating block group
  btrfs: replace identity maps with actual remaps when doing relocations

 fs/btrfs/Kconfig                |    2 +
 fs/btrfs/accessors.h            |   29 +
 fs/btrfs/block-group.c          |  202 +++-
 fs/btrfs/block-group.h          |   15 +-
 fs/btrfs/block-rsv.c            |    8 +
 fs/btrfs/block-rsv.h            |    1 +
 fs/btrfs/discard.c              |   11 +-
 fs/btrfs/disk-io.c              |   91 +-
 fs/btrfs/extent-tree.c          |  152 ++-
 fs/btrfs/free-space-tree.c      |    4 +-
 fs/btrfs/free-space-tree.h      |    5 +-
 fs/btrfs/fs.h                   |    7 +-
 fs/btrfs/relocation.c           | 1897 ++++++++++++++++++++++++++++++-
 fs/btrfs/relocation.h           |    8 +-
 fs/btrfs/space-info.c           |   22 +-
 fs/btrfs/sysfs.c                |    4 +
 fs/btrfs/transaction.c          |    7 +
 fs/btrfs/tree-checker.c         |   37 +-
 fs/btrfs/volumes.c              |  115 +-
 fs/btrfs/volumes.h              |   17 +-
 include/uapi/linux/btrfs.h      |    1 +
 include/uapi/linux/btrfs_tree.h |   29 +-
 22 files changed, 2444 insertions(+), 220 deletions(-)

-- 
2.49.0