Skip to content

RFC Remap tree

Mark Harmstone linux-btrfs oe-kbuild-all 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 RFC Latest10 patches 9 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/10btrfs: add definitions and constants for remap-treefs/btrfs/accessors.h fs/btrfs/sysfs.c fs/btrfs/tree-checker.c +3 more+23 -22 replies
2/10btrfs: add REMAP chunk typefs/btrfs/block-rsv.c fs/btrfs/block-rsv.h fs/btrfs/disk-io.c +7 more+47 -50 replies
3/10btrfs: allow remapped chunks to have zero stripesfs/btrfs/tree-checker.c fs/btrfs/volumes.c+16 -80 replies
4/10btrfs: add extended version of struct block_group_itemfs/btrfs/accessors.h fs/btrfs/block-group.c fs/btrfs/block-group.h +2 more+126 -272 replies
5/10btrfs: allow mounting filesystems with remap-tree incompat flagfs/btrfs/Kconfig fs/btrfs/accessors.h fs/btrfs/disk-io.c +4 more+84 -20 replies
6/10btrfs: redirect I/O for remapped block groupsfs/btrfs/ctree.c fs/btrfs/ctree.h fs/btrfs/relocation.c +2 more+105 -52 replies
7/10btrfs: handle deletions from remapped block groupfs/btrfs/block-group.c fs/btrfs/block-group.h fs/btrfs/disk-io.c +6 more+635 -550 replies
8/10btrfs: handle setting up relocation of block group with remap-treefs/btrfs/disk-io.c fs/btrfs/free-space-tree.c fs/btrfs/free-space-tree.h +4 more+467 -350 replies
9/10btrfs: move existing remaps before relocating block groupfs/btrfs/extent-tree.c fs/btrfs/relocation.c+448 -21 reply
10/10btrfs: replace identity maps with actual remaps when doing relocationsfs/btrfs/relocation.c+522 -02 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [RFC PATCH 00/10] Remap tree

Hi all,

This is an RFC for an experimental remap-tree incompat feature, which reworks how we perform relocations. Our present system involves following backrefs to rewrite addresses in the metadata trees, which can be slow and has knock-on effects such as breaking nocow files. Instead, this adds a remap tree to act as another layer of indirection: if a block group has the REMAPPED bit set, all I/O to addresses nominally within it get translated by a lookup to the remap tree.

See https://github.com/btrfs/btrfs-todo/issues/54 for Josef's original design, which I've elaborated on, and more on the rationale. To test this you will also need a patched btrfs-progs, for mkfs.btrfs -O remap-tree:
https://github.com/maharmstone/btrfs-progs/tree/remap-tree. See also
https://github.com/maharmstone/btrfs/blob/remap-tree/btrfs-dump.pl for a dumper script that's remap-aware.

The BTRFS_FEATURE_INCOMPAT_REMAP_TREE flag implies the following changes:

* There's a new remap tree, which is created empty

* The data reloc tree isn't created, as it's no longer needed (data relocation is no longer done via snapshots)

* There's a new metadata chunk type, REMAP, which consists solely of the remap tree. This is to avoid bootstrapping issues: REMAP chunks, like SYSTEM, are still relocated the old way (i.e. by COWing every leaf). We can't put the remap tree in SYSTEM: because the chunk items are put in the superblock, it would limit our available space

* The top of the remap tree is recorded in the superblock

* Two new fields are added to struct btrfs_block_group_item: le64 remap_bytes and le32 identity_remap_count. remap_bytes records how much data in a block group has been relocated from another block group. identity_remap_count records how many identity remaps exist for this block group (see later)

* If a block group has the REMAPPED flag set and identity_remaps == 0, its chunk will have 0 stripes and 0 dev extents: everything nominally within it its actually located elsewhere

* All data and metadata addresses are now translated addresses, for which we need to consult the remap tree to find the underlying addresses before doing I/O, if they live in a remapped BG. The exception is the free-space tree, which is entirely underlying addresses (the free-space cache v1 isn't supported here).

REMAP TREE
----------

The remap tree consists of three types of items: identity remaps, remaps, and remap backrefs. Each represents a non-overlapping range. Remaps are orthogonal to extents: an extent might be split into several ranges in the remap tree, or multiple consecutive extents might be remapped together.

Identity remaps represent a range for which we don't need to do a translation, i.e. the REMAPPED flag has been set for the BG but we haven't yet done a relocation.

Remaps have a u64 payload which gives the underlying address to use for the start of this range, i.e. the non-REMAPPED block group we should use for I/O.

Remap backrefs are a reverse index for the remaps, with their objectid being the underlying address and their u64 payload being the translated address. We need backrefs because when relocation a block group that contains existing remaps, these need to be moved first (we don't want to have to consult an ever-increasing chain of BGs).

RELOCATION
----------

For SYSTEM and REMAP block groups, relocation is as it is at the moment (mark the BG readonly, COW every leaf).

For DATA and METADATA block groups, we do the following:

* If remap_bytes > 0, search the remap tree for the remap backrefs that are physically located in this block group. Move the data on disk, munge the remap and free-space trees to reflect this, and reduce remap_bytes. Loop until remap_bytes is 0.

* Search the free-space tree for holes, convert these into identity remaps within the remap tree, set the identity_remap_count within in the block group item, and set the REMAPPED flag on the block group item and the chunk. The REMAPPED flag will prevent new allocations from being made from this block group.

* Walk through the remap tree looking for the identity remaps that we have created. For each one, try to reserve the same amount of space in another block group. Read the data into memory, and write an exact copy into the new location. Increase remap_bytes in the destination block group, and reduce identity_remap_count in the source block group if we can move the whole thing. Add the space back to the free-space tree in the source BG, and remove the space in the free-space tree for the destination BG.

* When identity_remaps_count == 0, the block group has been fully remapped, and now exists solely for the purposes of remapping. Set num_stripes to 0 in the chunk item, remove its stripes, and remove the entries in the dev extent tree.

* If a block group has the REMAPPED flag set, identity_remaps_count == 0, and remap_bytes == 0, it is now empty. The block group item, chunk item, and entries in the free-space tree can be removed.

KNOWN ISSUES
------------

* Still a few problems with some fstests: btrfs/156, btrfs/170, btrfs/177, btrfs/226, btrfs/250, btrfs/252.

* There's a race when it comes to nodatacow writes. I think we ought to be calling btrfs_inc_nocow_writers(), but that COWs rather than blocking.

* It can be reluctant to drop entries for empty remapped block groups. This doesn't waste substantial amounts of space on disk as there's no dev extents, but it is polluting the block group and chunk trees. Similarly we ought to be removing any enties in the free-space tree for fully remapped block groups: no new allocations can be done within them, and they no longer correspond to a location on disk.

* At the moment we're allocating 1GB for the REMAP chunks, which is probably overkilled. One 16KB leaf of the remap tree can cover ~250GB in the best case and ~1MB in the worst case. Possibly 32MB is the sweet spot, as for SYSTEM. Allocating more REMAP chunks isn't a problem, as unlike SYSTEM they don't go in the superblock.

* There's a spurious lockdep warning when doing remapped metadata reads, as we're locking an extent buffer within the remap tree while already holding another extent buffer lock. We either need to disable the warning for this, or change the code to use search_commit_root. We can't add another level to the lockdep hierarchy as we're already maxed out at 8.

* I'm think the lookup code in btrfs_translate_remap() probably needs to be refined. Possibly we can do without the call to btrfs_prev_leaf().

* At present we scan the free-space holes and create the identity remaps all in the same transaction. For the worst-case scenario of a 1GB block group with every other sector allocated, relocation takes ~30 seconds on my system, on an NVMe drive with no other load. Josef has suggested that we split this into multiple transactions, setting something like BTRFS_BLOCK_GROUP_ADDING_IDENTITY_REMAPS at the start, and discarding any progress on mount if we find a BG with this flag set, which makes sense to me. The code is currently gated behind CONFIG_BTRFS_EXPERIMENTAL. My preference would be that, like with the RAID stripe tree, we accept that there may be minor on-disk format changes until it can be moved out of experimental - i.e. we treat this as a (near-)future improvement rather than a blocker.

* Josef has also suggested that we don't log metadata items for the remap tree in the extent tree, in anticipation of later omitting all COW-only metadata items from the extent tree. My view is that treating the remap tree as a special case would be more trouble than it's worth, both here and in progs, and omitting all COW-only metadata items should be relegated to a later incompat change that depends on this one.

* There's still a lot of userspace work to be done: making sure that all space reporting etc. tools are okay, adding a comprehensive series of tests to btrfs check, allowing toggling this incompat flag on and off in btrfstune.

Thanks

Mark

Mark Harmstone (10):
btrfs: add definitions and constants for remap-tree
btrfs: add REMAP chunk type
btrfs: allow remapped chunks to have zero stripes
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          |  181 ++-
 fs/btrfs/block-group.h          |   15 +-
 fs/btrfs/block-rsv.c            |    8 +
 fs/btrfs/block-rsv.h            |    1 +
 fs/btrfs/ctree.c                |   11 +-
 fs/btrfs/ctree.h                |    3 +
 fs/btrfs/disk-io.c              |   88 +-
 fs/btrfs/extent-tree.c          |   38 +-
 fs/btrfs/free-space-tree.c      |    4 +-
 fs/btrfs/free-space-tree.h      |    5 +-
 fs/btrfs/fs.h                   |    7 +-
 fs/btrfs/relocation.c           | 2065 ++++++++++++++++++++++++++++++-
 fs/btrfs/relocation.h           |    8 +-
 fs/btrfs/space-info.c           |   20 +-
 fs/btrfs/sysfs.c                |    4 +
 fs/btrfs/transaction.c          |    7 +
 fs/btrfs/tree-checker.c         |   37 +-
 fs/btrfs/volumes.c              |  106 +-
 fs/btrfs/volumes.h              |   17 +-
 include/uapi/linux/btrfs.h      |    1 +
 include/uapi/linux/btrfs_tree.h |   29 +-
 23 files changed, 2509 insertions(+), 177 deletions(-)
Signature · 1 line
2.49.0