Re: [RFC PATCH 10/10] btrfs: replace identity maps with actual remaps when doing relocations

Mark Harmstone
2025-05-23T14:54:10Z

Thanks Boris.

On 21/5/25 01:04, Boris Burkov wrote:
> >
> On Thu, May 15, 2025 at 05:36:38PM +0100, Mark Harmstone wrote:
>> Add a function do_remap_tree_reloc(), which does the actual work of
>> doing a relocation using the remap tree.
>>
>> In a loop we call do_remap_tree_reloc_trans(), which searches for the
>> first identity remap for the block group. We call btrfs_reserve_extent()
>> to find space elsewhere for it, and read the data into memory and write
>> it to the new location. We then carve out the identity remap and replace
>> it with an actual remap, which points to the new location in which to
>> look.
>>
>> Once the last identity remap has been removed we call
>> last_identity_remap_gone(), which, as with deletions, removes the
>> chunk's stripes and device extents.
>
> I think this is a good candidate for unit testing. Just hammer a bunch
> of cases adding/removing/merging remaps.

Yes, makes sense

>>
>> Signed-off-by: Mark Harmstone <maharmstone@fb.com>
>> ---
>> fs/btrfs/relocation.c | 522 ++++++++++++++++++++++++++++++++++++++++++
>> 1 file changed, 522 insertions(+)
>>
>> diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
>> index 7da95b82c798..bcf04d4c5af1 100644
>> --- a/fs/btrfs/relocation.c
>> +++ b/fs/btrfs/relocation.c
>> @@ -4660,6 +4660,60 @@ static int mark_bg_remapped(struct btrfs_trans_handle *trans,
>> return ret;
>> }
>>
>
> Thinking out loud: I wonder if you do end up re-modeling the
> transactions s.t. we do one transaction per loop or something, then
> maybe you can use btrfs_for_each_slot.

That is what we're doing in do_remap_tree_reloc(). I think the downside
of btrfs_for_each_slot is that we're not necessarily removing the whole
identity remap every time, as btrfs_reserve_extent() might give us less
than we asked for.

>> +static int find_next_identity_remap(struct btrfs_trans_handle *trans,
>> + struct btrfs_path *path, u64 bg_end,
>> + u64 last_start, u64 *start,
>> + u64 *length)
>> +{
>> + int ret;
>> + struct btrfs_key key, found_key;
>> + struct btrfs_root *remap_root = trans->fs_info->remap_root;
>> + struct extent_buffer *leaf;
>> +
>> + key.objectid = last_start;
>> + key.type = BTRFS_IDENTITY_REMAP_KEY;
>> + key.offset = 0;
>> +
>> + ret = btrfs_search_slot(trans, remap_root, &key, path, 0, 0);
>> + if (ret < 0)
>> + goto out;
>> +
>> + leaf = path->nodes[0];
>> + while (true) {
>> + btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
>> +
>> + if (found_key.objectid >= bg_end) {
>> + ret = -ENOENT;
>> + goto out;
>> + }
>> +
>> + if (found_key.type == BTRFS_IDENTITY_REMAP_KEY) {
>> + *start = found_key.objectid;
>> + *length = found_key.offset;
>> + ret = 0;
>> + goto out;
>> + }
>> +
>> + path->slots[0]++;
>> + if (path->slots[0] >= btrfs_header_nritems(leaf)) {
>> + ret = btrfs_next_leaf(remap_root, path);
>> +
>> + if (ret != 0) {
>> + if (ret == 1)
>> + ret = -ENOENT;
>> + goto out;
>> + }
>> +
>> + leaf = path->nodes[0];
>> + }
>> + }
>> +
>> +out:
>> + btrfs_release_path(path);
>> +
>> + return ret;
>> +}
>> +
>> static int remove_chunk_stripes(struct btrfs_trans_handle *trans,
>> struct btrfs_chunk_map *chunk,
>> struct btrfs_path *path)
>> @@ -4779,6 +4833,288 @@ static int adjust_identity_remap_count(struct btrfs_trans_handle *trans,
>> return ret;
>> }
>>
>> +static int merge_remap_entries(struct btrfs_trans_handle *trans,
>> + struct btrfs_path *path,
>> + struct btrfs_block_group *src_bg, u64 old_addr,
>> + u64 new_addr, u64 length)
>> +{
>> + struct btrfs_fs_info *fs_info = trans->fs_info;
>> + struct btrfs_remap *remap_ptr;
>> + struct extent_buffer *leaf;
>> + struct btrfs_key key, new_key;
>> + u64 last_addr, old_length;
>> + int ret;
>> +
>> + leaf = path->nodes[0];
>> + btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
>> +
>> + remap_ptr = btrfs_item_ptr(leaf, path->slots[0],
>> + struct btrfs_remap);
>> +
>> + last_addr = btrfs_remap_address(leaf, remap_ptr);
>> + old_length = key.offset;
>> +
>> + if (last_addr + old_length != new_addr)
>> + return 0;
>> +
>> + /* Merge entries. */
>> +
>> + new_key.objectid = key.objectid;
>> + new_key.type = BTRFS_REMAP_KEY;
>> + new_key.offset = old_length + length;
>> +
>> + btrfs_set_item_key_safe(trans, path, &new_key);
>> +
>> + btrfs_release_path(path);
>> +
>> + /* Merge backref too. */
>> +
>> + key.objectid = new_addr - old_length;
>> + key.type = BTRFS_REMAP_BACKREF_KEY;
>> + key.offset = old_length;
>> +
>> + ret = btrfs_search_slot(trans, fs_info->remap_root, &key, path, 0, 1);
>> + if (ret < 0) {
>> + return ret;
>> + } else if (ret == 1) {
>> + btrfs_release_path(path);
>> + return -ENOENT;
>> + }
>> +
>> + new_key.objectid = new_addr - old_length;
>> + new_key.type = BTRFS_REMAP_BACKREF_KEY;
>> + new_key.offset = old_length + length;
>> +
>> + btrfs_set_item_key_safe(trans, path, &new_key);
>> +
>> + btrfs_release_path(path);
>> +
>> + /* Fix the following identity map. */
>> +
>> + key.objectid = old_addr;
>> + key.type = BTRFS_IDENTITY_REMAP_KEY;
>> + key.offset = 0;
>> +
>> + ret = btrfs_search_slot(trans, fs_info->remap_root, &key, path, 0, 1);
>> + if (ret < 0)
>> + return ret;
>> +
>> + btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
>> +
>> + if (key.objectid != old_addr || key.type != BTRFS_IDENTITY_REMAP_KEY)
>> + return -ENOENT;
>> +
>> + if (key.offset == length) {
>> + ret = btrfs_del_item(trans, fs_info->remap_root, path);
>> + if (ret)
>> + return ret;
>> +
>> + btrfs_release_path(path);
>> +
>> + ret = adjust_identity_remap_count(trans, path, src_bg, -1);
>> + if (ret)
>> + return ret;
>> +
>> + return 1;
>> + }
>> +
>> + new_key.objectid = old_addr + length;
>> + new_key.type = BTRFS_IDENTITY_REMAP_KEY;
>> + new_key.offset = key.offset - length;
>> +
>> + btrfs_set_item_key_safe(trans, path, &new_key);
>> +
>> + btrfs_release_path(path);
>> +
>> + return 1;
>> +}
>> +
>> +static int add_new_remap_entry(struct btrfs_trans_handle *trans,
>> + struct btrfs_path *path,
>> + struct btrfs_block_group *src_bg, u64 old_addr,
>> + u64 new_addr, u64 length)
>> +{
>> + struct btrfs_fs_info *fs_info = trans->fs_info;
>> + struct btrfs_key key, new_key;
>> + struct btrfs_remap remap;
>> + int ret;
>> + int identity_count_delta = 0;
>> +
>> + btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
>> +
>> + /* Shorten or delete identity mapping entry. */
>> +
>> + if (key.objectid == old_addr) {
>> + ret = btrfs_del_item(trans, fs_info->remap_root, path);
>> + if (ret)
>> + return ret;
>> +
>> + identity_count_delta--;
>> + } else {
>> + new_key.objectid = key.objectid;
>> + new_key.type = BTRFS_IDENTITY_REMAP_KEY;
>> + new_key.offset = old_addr - key.objectid;
>> +
>> + btrfs_set_item_key_safe(trans, path, &new_key);
>> + }
>> +
>> + btrfs_release_path(path);
>> +
>> + /* Create new remap entry. */
>> +
>> + new_key.objectid = old_addr;
>> + new_key.type = BTRFS_REMAP_KEY;
>> + new_key.offset = length;
>> +
>> + ret = btrfs_insert_empty_item(trans, fs_info->remap_root,
>> + path, &new_key, sizeof(struct btrfs_remap));
>> + if (ret)
>> + return ret;
>> +
>> + btrfs_set_stack_remap_address(&remap, new_addr);
>> +
>> + write_extent_buffer(path->nodes[0], &remap,
>> + btrfs_item_ptr_offset(path->nodes[0], path->slots[0]),
>> + sizeof(struct btrfs_remap));
>> +
>> + btrfs_release_path(path);
>> +
>> + /* Add entry for remainder of identity mapping, if necessary. */
>> +
>> + if (key.objectid + key.offset != old_addr + length) {
>> + new_key.objectid = old_addr + length;
>> + new_key.type = BTRFS_IDENTITY_REMAP_KEY;
>> + new_key.offset = key.objectid + key.offset - old_addr - length;
>> +
>> + ret = btrfs_insert_empty_item(trans, fs_info->remap_root,
>> + path, &new_key, 0);
>> + if (ret)
>> + return ret;
>> +
>> + btrfs_release_path(path);
>> +
>> + identity_count_delta++;
>> + }
>> +
>> + /* Add backref. */
>> +
>> + new_key.objectid = new_addr;
>> + new_key.type = BTRFS_REMAP_BACKREF_KEY;
>> + new_key.offset = length;
>> +
>> + ret = btrfs_insert_empty_item(trans, fs_info->remap_root, path,
>> + &new_key, sizeof(struct btrfs_remap));
>> + if (ret)
>> + return ret;
>> +
>> + btrfs_set_stack_remap_address(&remap, old_addr);
>> +
>> + write_extent_buffer(path->nodes[0], &remap,
>> + btrfs_item_ptr_offset(path->nodes[0], path->slots[0]),
>> + sizeof(struct btrfs_remap));
>> +
>> + btrfs_release_path(path);
>> +
>> + if (identity_count_delta == 0)
>> + return 0;
>> +
>> + ret = adjust_identity_remap_count(trans, path, src_bg,
>> + identity_count_delta);
>> + if (ret)
>> + return ret;
>> +
>> + return 0;
>> +}
>> +
>> +static int add_remap_entry(struct btrfs_trans_handle *trans,
>> + struct btrfs_path *path,
>> + struct btrfs_block_group *src_bg, u64 old_addr,
>> + u64 new_addr, u64 length)
>> +{
>> + struct btrfs_fs_info *fs_info = trans->fs_info;
>> + struct btrfs_key key;
>> + struct extent_buffer *leaf;
>> + int ret;
>> +
>> + key.objectid = old_addr;
>> + key.type = BTRFS_IDENTITY_REMAP_KEY;
>> + key.offset = 0;
>> +
>
> Can this lookup code be shared at all with the remapping logic in the
> previous patch? It seems fundamentally both are finding a remap entry for
> a given logical address. Or is it impossible since this one needs cow?
>
> Maybe some kind of prev_item helper that's either remap tree specific or
> for this use case of going back exactly one item instead of obeying a
> min_objectid?

Thanks - yes, there's some overlap between add_remap_entry() and
move_existing_remap(), it'd make sense to merge them as much as possible.

>
>> + ret = btrfs_search_slot(trans, fs_info->remap_root, &key, path, 0, 1);
>> + if (ret < 0)
>> + goto end;
>> +
>> + btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
>> +
>> + if (key.objectid >= old_addr) {
>> + if (path->slots[0] == 0) {
>> + ret = btrfs_prev_leaf(trans, fs_info->remap_root, path,
>> + 0, 1);
>> + if (ret < 0)
>> + goto end;
>> + } else {
>> + path->slots[0]--;
>> + }
>> + }
>> +
>> + while (true) {
>> + leaf = path->nodes[0];
>> + if (path->slots[0] >= btrfs_header_nritems(leaf)) {
>> + ret = btrfs_next_leaf(fs_info->remap_root, path);
>> + if (ret < 0)
>> + goto end;
>> + else if (ret == 1)
>> + break;
>> + leaf = path->nodes[0];
>> + }
>> +
>> + btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
>> +
>> + if (key.objectid >= old_addr + length) {
>> + ret = -ENOENT;
>> + goto end;
>> + }
>> +
>> + if (key.type != BTRFS_REMAP_KEY &&
>> + key.type != BTRFS_IDENTITY_REMAP_KEY) {
>> + path->slots[0]++;
>> + continue;
>> + }
>> +
>> + if (key.type == BTRFS_REMAP_KEY &&
>> + key.objectid + key.offset == old_addr) {
>> + ret = merge_remap_entries(trans, path, src_bg, old_addr,
>> + new_addr, length);
>> + if (ret < 0) {
>> + goto end;
>> + } else if (ret == 0) {
>> + path->slots[0]++;
>> + continue;
>> + }
>> + break;
>> + }
>> +
>> + if (key.objectid <= old_addr &&
>> + key.type == BTRFS_IDENTITY_REMAP_KEY &&
>> + key.objectid + key.offset > old_addr) {
>> + ret = add_new_remap_entry(trans, path, src_bg,
>> + old_addr, new_addr, length);
>> + if (ret)
>> + goto end;
>> + break;
>> + }
>> +
>> + path->slots[0]++;
>> + }
>> +
>> + ret = 0;
>> +
>> +end:
>> + btrfs_release_path(path);
>> +
>> + return ret;
>> +}
>> +
>> static int mark_chunk_remapped(struct btrfs_trans_handle *trans,
>> struct btrfs_path *path, uint64_t start)
>> {
>> @@ -4828,6 +5164,188 @@ static int mark_chunk_remapped(struct btrfs_trans_handle *trans,
>> return ret;
>> }
>>
>> +static int do_remap_tree_reloc_trans(struct btrfs_fs_info *fs_info,
>> + struct btrfs_block_group *src_bg,
>> + struct btrfs_path *path, u64 *last_start)
>> +{
>> + struct btrfs_trans_handle *trans;
>> + struct btrfs_root *extent_root;
>> + struct btrfs_key ins;
>> + struct btrfs_block_group *dest_bg = NULL;
>> + struct btrfs_chunk_map *chunk;
>> + u64 start, remap_length, length, new_addr, min_size;
>> + int ret;
>> + bool no_more = false;
>> + bool is_data = src_bg->flags & BTRFS_BLOCK_GROUP_DATA;
>> + bool made_reservation = false, bg_needs_free_space;
>> + struct btrfs_space_info *sinfo = src_bg->space_info;
>> +
>> + extent_root = btrfs_extent_root(fs_info, src_bg->start);
>> +
>> + trans = btrfs_start_transaction(extent_root, 0);
>> + if (IS_ERR(trans))
>> + return PTR_ERR(trans);
>> +
>> + mutex_lock(&fs_info->remap_mutex);
>> +
>> + ret = find_next_identity_remap(trans, path, src_bg->start + src_bg->length,
>> + *last_start, &start, &remap_length);
>> + if (ret == -ENOENT) {
>> + no_more = true;
>> + goto next;
>> + } else if (ret) {
>> + mutex_unlock(&fs_info->remap_mutex);
>> + btrfs_end_transaction(trans);
>> + return ret;
>> + }
>> +
>> + /* Try to reserve enough space for block. */
>> +
>> + spin_lock(&sinfo->lock);
>> + btrfs_space_info_update_bytes_may_use(sinfo, remap_length);
>
> Why isn't this partly leaked if btrfs_reserve_extent returns a smaller extent than
> remap_length?
>
>> + spin_unlock(&sinfo->lock);
>> +
>> + if (is_data)
>> + min_size = fs_info->sectorsize;
>> + else
>> + min_size = fs_info->nodesize;
>> +
>> + ret = btrfs_reserve_extent(fs_info->fs_root, remap_length,
>> + remap_length, min_size,
>> + 0, 0, &ins, is_data, false);
>
> ^ i.e., this will reduce bytes_may_use by the amount it actually
> reserved, and I don't see anywhere where we make up the difference. Then
> it looks like we will remap the extent we can, find the next free range
> and come back to this function and that remaining range to bytes_may_use
> a second time.

As I said to you off-list, this tripped me up! btrfs_reserve_extent()
reverses the whole bytes_may_use value, even if it hands out less than that.

>
>> + if (ret) {
>> + spin_lock(&sinfo->lock);
>> + btrfs_space_info_update_bytes_may_use(sinfo, -remap_length);
>> + spin_unlock(&sinfo->lock);
>> +
>> + mutex_unlock(&fs_info->remap_mutex);
>> + btrfs_end_transaction(trans);
>> + return ret;
>> + }
>> +
>> + made_reservation = true;
>> +
>> + new_addr = ins.objectid;
>> + length = ins.offset;
>> +
>> + if (!is_data && length % fs_info->nodesize) {
>> + u64 new_length = length - (length % fs_info->nodesize);
>
> Why not use the IS_ALIGNED / ALIGN_DOWN macros? Nodesize is a power of
> two, so I think it should be quicker. Probably doesn't matter, but it
> does seem to be the predominant pattern in the code base. Also avoids
> ever worrying about dividing by zero.

Makes sense, thank you. I changed this to use & after kernelbot
complained that I broke compilation on 32-bit CPUs, which is presumably
what the macro is doing.

>
>> +
>> + btrfs_free_reserved_extent(fs_info, new_addr + new_length,
>> + length - new_length, 0);
>> +
>> + length = new_length;
>> + }
>> +
>> + ret = add_to_free_space_tree(trans, start, length);
>
> Can you explain this? Intuitively, to me, the old remapped address is
> not a logical range we can allocate from, so it should not be in the
> free space tree. Is this a hack to get the bytes back into the
> accounting and allocations are blocked by the remapped block group being
> remapped / read-only?

Yes, good point - we should be clearing out the FST once a block is
marked REMAPPED. I think I'll have to fix the discard code, IIRC it
works by walking the FST. Plus btrfs-check as well of course

>
>> + if (ret)
>> + goto fail;
>> +
>> + dest_bg = btrfs_lookup_block_group(fs_info, new_addr);
>> +
>> + mutex_lock(&dest_bg->free_space_lock);
>> + bg_needs_free_space = test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE,
>> + &dest_bg->runtime_flags);
>> + mutex_unlock(&dest_bg->free_space_lock);
>> +
>> + if (bg_needs_free_space) {
>> + ret = add_block_group_free_space(trans, dest_bg);
>> + if (ret)
>> + goto fail;
>> + }
>> +
>> + ret = remove_from_free_space_tree(trans, new_addr, length);
>> + if (ret)
>> + goto fail;
>
> I think you have also discussed this recently with Josef, but it seems
> a little sketchy. I suppose it depends if the remap tree ends up getting
> delayed refs and going in the extent tree? I think this is currently
> only called from alloc_reserved_extent.

Do you mean the bit about BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE? We delay
populating the in-memory representation of the FST for a BG until we
need it, so we have to force it here. Presumably if we accept that
remapped BGs don't have anything in the FST we can remove this code.

>> +
>> + ret = do_copy(fs_info, start, new_addr, length);
>> + if (ret)
>> + goto fail;
>> +
>> + ret = add_remap_entry(trans, path, src_bg, start, new_addr, length);
>> + if (ret)
>> + goto fail;
>> +
>> + adjust_block_group_remap_bytes(trans, dest_bg, length);
>> + btrfs_free_reserved_bytes(dest_bg, length, 0);
>> +
>> + spin_lock(&sinfo->lock);
>> + sinfo->bytes_readonly += length;
>> + spin_unlock(&sinfo->lock);
>> +
>> +next:
>> + if (dest_bg)
>> + btrfs_put_block_group(dest_bg);
>> +
>> + if (made_reservation)
>> + btrfs_dec_block_group_reservations(fs_info, new_addr);
>> +
>> + if (src_bg->used == 0 && src_bg->remap_bytes == 0) {
>> + chunk = btrfs_find_chunk_map(fs_info, src_bg->start, 1);
>> + if (!chunk) {
>> + mutex_unlock(&fs_info->remap_mutex);
>> + btrfs_end_transaction(trans);
>> + return -ENOENT;
>> + }
>> +
>> + ret = last_identity_remap_gone(trans, chunk, src_bg, path);
>> + if (ret) {
>> + btrfs_free_chunk_map(chunk);
>> + mutex_unlock(&fs_info->remap_mutex);
>> + btrfs_end_transaction(trans);
>> + return ret;
>> + }
>> +
>> + btrfs_free_chunk_map(chunk);
>> + }
>> +
>> + mutex_unlock(&fs_info->remap_mutex);
>> +
>> + ret = btrfs_end_transaction(trans);
>> + if (ret)
>> + return ret;
>> +
>> + if (no_more)
>> + return 1;
>> +
>> + *last_start = start;
>> +
>> + return 0;
>> +
>> +fail:
>> + if (dest_bg)
>> + btrfs_put_block_group(dest_bg);
>> +
>> + btrfs_free_reserved_extent(fs_info, new_addr, length, 0);
>> +
>> + mutex_unlock(&fs_info->remap_mutex);
>> + btrfs_end_transaction(trans);
>> +
>> + return ret;
>> +}
>> +
>> +static int do_remap_tree_reloc(struct btrfs_fs_info *fs_info,
>> + struct btrfs_path *path,
>> + struct btrfs_block_group *bg)
>> +{
>> + u64 last_start;
>> + int ret;
>> +
>> + last_start = bg->start;
>> +
>> + while (true) {
>> + ret = do_remap_tree_reloc_trans(fs_info, bg, path,
>> + &last_start);
>> + if (ret) {
>> + if (ret == 1)
>> + ret = 0;
>> + break;
>> + }
>> + }
>> +
>> + return ret;
>> +}
>> +
>> int btrfs_translate_remap(struct btrfs_fs_info *fs_info, u64 *logical,
>> u64 *length)
>> {
>> @@ -5073,6 +5591,10 @@ int btrfs_relocate_block_group(struct btrfs_fs_info *fs_info, u64 group_start,
>> }
>>
>> err = start_block_group_remapping(fs_info, path, bg);
>> + if (err)
>> + goto out;
>> +
>> + err = do_remap_tree_reloc(fs_info, path, rc->block_group);
>>
>> goto out;
>> }
>> --
>> 2.49.0
>>