diff mbox series

btrfs-progs: map-logical: fix search miss when extent is the first in a leaf

Message ID dd34707ffd1cd5a458980a209cfcc06a1817b848.1726149878.git.fdmanana@suse.com (mailing list archive)
State New
Headers show
Series btrfs-progs: map-logical: fix search miss when extent is the first in a leaf | expand

Commit Message

Filipe Manana Sept. 12, 2024, 2:05 p.m. UTC 
From: Filipe Manana <fdmanana@suse.com>

When searching the extent tree for the target extent item, we can miss it
if the extent item is the first item in a leaf and if there is a previous
leaf in the extent tree.

For example, if we call btrfs-map-logical like this:

   $ btrfs-map-logical -l 5382144 /dev/sdc

And we have the following extent tree layout:

   leaf 5386240 items 26 free space 2505 generation 7 owner EXTENT_TREE
   leaf 5386240 flags 0x1(WRITTEN) backref revision 1
   (...)
           item 25 key (5373952 METADATA_ITEM 0) itemoff 3155 itemsize 33
                   refs 1 gen 7 flags TREE_BLOCK
                   tree block skinny level 0
                   (176 0x5) tree block backref root FS_TREE

   leaf 5480448 items 56 free space 276 generation 7 owner EXTENT_TREE
   leaf 5480448 flags 0x1(WRITTEN) backref revision 1
   (...)
           item 0 key (5382144 METADATA_ITEM 0) itemoff 3962 itemsize 33
                   refs 1 gen 7 flags TREE_BLOCK
                   tree block skinny level 0
                   (176 0x7) tree block backref root CSUM_TREE
   (...)

Then the following happens:

1) We enter map_one_extent() with search_forward == 0 and
   *logical_ret == 5382144;

2) We search for the key (5382144 0 0) which leaves us with a path
   pointing to leaf 5386240 at slot 26 - one slot beyond the last item;

3) We then call:

     btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0])

   Which is not valid since there's no item at that slot, but since the
   area of the leaf where an item at that slot should be is zeroed out,
   we end up getting a key of (0 0 0);

4) We then enter the "if" statement bellow, since key.type is 0, and call
   btrfs_previous_extent_item(), which leaves at slot 25 of leaf 5386240,
   point to the extent item of the extent 5373952.

   The requested extent, 5382144, is the first item of the next leaf
   (5480448), but we totally miss it;

5) We return to the caller, the main() function, with 'cur_logical'
   pointing to the metadata extent at 5373952, and not to the requested
   one at 5382144.

   In the last while loop of main() we have 'cur_logical' == 5373952,
   which makes the loop have no iterations and therefore the local
   variable 'found' remans with a value of 0, and then the program fails
   like this:

   $ btrfs-map-logical -l 5382144 /dev/sdc
   ERROR: no extent found at range [5382144,5386240)

Fix this by never accessing beyond the last slot of a leaf. If we ever end
up at a slot beyond the last item in a leaf, just call btrfs_next_leaf()
and process the first item in the returned path.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 btrfs-map-logical.c | 5 +++++
 1 file changed, 5 insertions(+)

Comments

Qu Wenruo Sept. 12, 2024, 9:36 p.m. UTC | #1 
在 2024/9/12 23:35, fdmanana@kernel.org 写道:
> From: Filipe Manana <fdmanana@suse.com>
>
> When searching the extent tree for the target extent item, we can miss it
> if the extent item is the first item in a leaf and if there is a previous
> leaf in the extent tree.
>
> For example, if we call btrfs-map-logical like this:
>
>     $ btrfs-map-logical -l 5382144 /dev/sdc
>
> And we have the following extent tree layout:
>
>     leaf 5386240 items 26 free space 2505 generation 7 owner EXTENT_TREE
>     leaf 5386240 flags 0x1(WRITTEN) backref revision 1
>     (...)
>             item 25 key (5373952 METADATA_ITEM 0) itemoff 3155 itemsize 33
>                     refs 1 gen 7 flags TREE_BLOCK
>                     tree block skinny level 0
>                     (176 0x5) tree block backref root FS_TREE
>
>     leaf 5480448 items 56 free space 276 generation 7 owner EXTENT_TREE
>     leaf 5480448 flags 0x1(WRITTEN) backref revision 1
>     (...)
>             item 0 key (5382144 METADATA_ITEM 0) itemoff 3962 itemsize 33
>                     refs 1 gen 7 flags TREE_BLOCK
>                     tree block skinny level 0
>                     (176 0x7) tree block backref root CSUM_TREE
>     (...)
>
> Then the following happens:
>
> 1) We enter map_one_extent() with search_forward == 0 and
>     *logical_ret == 5382144;
>
> 2) We search for the key (5382144 0 0) which leaves us with a path
>     pointing to leaf 5386240 at slot 26 - one slot beyond the last item;
>
> 3) We then call:
>
>       btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0])
>
>     Which is not valid since there's no item at that slot, but since the
>     area of the leaf where an item at that slot should be is zeroed out,
>     we end up getting a key of (0 0 0);
>
> 4) We then enter the "if" statement bellow, since key.type is 0, and call
>     btrfs_previous_extent_item(), which leaves at slot 25 of leaf 5386240,
>     point to the extent item of the extent 5373952.
>
>     The requested extent, 5382144, is the first item of the next leaf
>     (5480448), but we totally miss it;
>
> 5) We return to the caller, the main() function, with 'cur_logical'
>     pointing to the metadata extent at 5373952, and not to the requested
>     one at 5382144.
>
>     In the last while loop of main() we have 'cur_logical' == 5373952,
>     which makes the loop have no iterations and therefore the local
>     variable 'found' remans with a value of 0, and then the program fails
>     like this:
>
>     $ btrfs-map-logical -l 5382144 /dev/sdc
>     ERROR: no extent found at range [5382144,5386240)
>
> Fix this by never accessing beyond the last slot of a leaf. If we ever end
> up at a slot beyond the last item in a leaf, just call btrfs_next_leaf()
> and process the first item in the returned path.
>
> Signed-off-by: Filipe Manana <fdmanana@suse.com>

Reviewed-by: Qu Wenruo <wqu@suse.com>

Thanks,
Qu

> ---
>   btrfs-map-logical.c | 5 +++++
>   1 file changed, 5 insertions(+)
>
> diff --git a/btrfs-map-logical.c b/btrfs-map-logical.c
> index 2984e645..a97afea4 100644
> --- a/btrfs-map-logical.c
> +++ b/btrfs-map-logical.c
> @@ -74,6 +74,11 @@ static int map_one_extent(struct btrfs_fs_info *fs_info,
>   	BUG_ON(ret == 0);
>   	ret = 0;
>
> +	if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
> +		ret = btrfs_next_leaf(extent_root, path);
> +		if (ret)
> +			goto out;
> +	}
>   again:
>   	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
>   	if ((search_forward && key.objectid < logical) ||
David Sterba Sept. 17, 2024, 2:19 p.m. UTC | #2 
On Thu, Sep 12, 2024 at 03:05:44PM +0100, fdmanana@kernel.org wrote:
> From: Filipe Manana <fdmanana@suse.com>
> 
> When searching the extent tree for the target extent item, we can miss it
> if the extent item is the first item in a leaf and if there is a previous
> leaf in the extent tree.
> 
> For example, if we call btrfs-map-logical like this:
> 
>    $ btrfs-map-logical -l 5382144 /dev/sdc
> 
> And we have the following extent tree layout:
> 
>    leaf 5386240 items 26 free space 2505 generation 7 owner EXTENT_TREE
>    leaf 5386240 flags 0x1(WRITTEN) backref revision 1
>    (...)
>            item 25 key (5373952 METADATA_ITEM 0) itemoff 3155 itemsize 33
>                    refs 1 gen 7 flags TREE_BLOCK
>                    tree block skinny level 0
>                    (176 0x5) tree block backref root FS_TREE
> 
>    leaf 5480448 items 56 free space 276 generation 7 owner EXTENT_TREE
>    leaf 5480448 flags 0x1(WRITTEN) backref revision 1
>    (...)
>            item 0 key (5382144 METADATA_ITEM 0) itemoff 3962 itemsize 33
>                    refs 1 gen 7 flags TREE_BLOCK
>                    tree block skinny level 0
>                    (176 0x7) tree block backref root CSUM_TREE
>    (...)
> 
> Then the following happens:
> 
> 1) We enter map_one_extent() with search_forward == 0 and
>    *logical_ret == 5382144;
> 
> 2) We search for the key (5382144 0 0) which leaves us with a path
>    pointing to leaf 5386240 at slot 26 - one slot beyond the last item;
> 
> 3) We then call:
> 
>      btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0])
> 
>    Which is not valid since there's no item at that slot, but since the
>    area of the leaf where an item at that slot should be is zeroed out,
>    we end up getting a key of (0 0 0);
> 
> 4) We then enter the "if" statement bellow, since key.type is 0, and call
>    btrfs_previous_extent_item(), which leaves at slot 25 of leaf 5386240,
>    point to the extent item of the extent 5373952.
> 
>    The requested extent, 5382144, is the first item of the next leaf
>    (5480448), but we totally miss it;
> 
> 5) We return to the caller, the main() function, with 'cur_logical'
>    pointing to the metadata extent at 5373952, and not to the requested
>    one at 5382144.
> 
>    In the last while loop of main() we have 'cur_logical' == 5373952,
>    which makes the loop have no iterations and therefore the local
>    variable 'found' remans with a value of 0, and then the program fails
>    like this:
> 
>    $ btrfs-map-logical -l 5382144 /dev/sdc
>    ERROR: no extent found at range [5382144,5386240)
> 
> Fix this by never accessing beyond the last slot of a leaf. If we ever end
> up at a slot beyond the last item in a leaf, just call btrfs_next_leaf()
> and process the first item in the returned path.
> 
> Signed-off-by: Filipe Manana <fdmanana@suse.com>

Added to devel, thanks.
diff mbox series

Patch

diff --git a/btrfs-map-logical.c b/btrfs-map-logical.c
index 2984e645..a97afea4 100644
--- a/btrfs-map-logical.c
+++ b/btrfs-map-logical.c
@@ -74,6 +74,11 @@  static int map_one_extent(struct btrfs_fs_info *fs_info,
 	BUG_ON(ret == 0);
 	ret = 0;
 
+	if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
+		ret = btrfs_next_leaf(extent_root, path);
+		if (ret)
+			goto out;
+	}
 again:
 	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 	if ((search_forward && key.objectid < logical) ||