Skip to contentSkip to conversation

btrfs: a couple fixes for extent map merging and defrag

PATCH In review [email protected] 3 participants 6 messages Oct 29, 2024 – Oct 30, 2024 Btrfs file system

lore
Share & tools
lore
#0 lore raw

cover btrfs: a couple fixes for extent map merging and defrag

From: Filipe Manana <[email protected]>

Some fixes for extent map merging not happened when it should (which avoids saving some memory) and defrag not merging contiguous extents when it should due to merged extent maps. Details in the change logs.

Filipe Manana (2):
btrfs: fix extent map merging not happening for adjacent extents
btrfs: fix defrag not merging contiguous extents due to merged extent maps

 fs/btrfs/defrag.c     | 10 +++++-----
 fs/btrfs/extent_map.c |  7 ++++++-
 2 files changed, 11 insertions(+), 6 deletions(-)
Signature · 1 line
2.45.2
#1 lore raw

PATCH 1/2 btrfs: fix extent map merging not happening for adjacent extents

From: Filipe Manana <[email protected]>

If we have 3 or more adjacent extents in a file, that is, consecutive file extent items pointing to adjacent extents, within a contiguous file range and compatible flags, we end up not merging all the extents into a single extent map.

For example:

  $ mkfs.btrfs -f /dev/sdc
  $ mount /dev/sdc /mnt/sdc
  $ xfs_io -f -d -c "pwrite -b 64K 0 64K" \
                 -c "pwrite -b 64K 64K 64K" \
                 -c "pwrite -b 64K 128K 64K" \
                 -c "pwrite -b 64K 192K 64K" \
                 /mnt/sdc/foo

After all the ordered extents complete we unpin the extent maps and try to merge them, but instead of getting a single extent map we get two because:

1) When the first ordered extent completes (file range [0, 64K)) we unpin its extent map and attempt to merge it with the extent map for the range [64K, 128K), but we can't because that extent map is still pinned;

2) When the second ordered extent completes (file range [64K, 128K)), we unpin its extent map and merge it with the previous extent map, for file range [0, 64K), but we can't merge with the next extent map, for the file range [128K, 192K), because this one is still pinned.

The merged extent map for the file range [0, 128K) gets the flag EXTENT_MAP_MERGED set;

3) When the third ordered extent completes (file range [128K, 192K)), we unpin its exent map and attempt to merge it with the previous extent map, for file range [0, 128K), but we can't because that extent map has the flag EXTENT_MAP_MERGED set (mergeable_maps() returns false due to different flags) while the extent map for the range [128K, 192K) doesn't have that flag set.

We also can't merge it with the next extent map, for file range [192K, 256K), because that one is still pinned.

At this moment we have 3 extent maps:

One for file range [0, 128K), with the flag EXTENT_MAP_MERGED set. One for file range [128K, 192K).
One for file range [192K, 256K) which is still pinned;

4) When the fourth and final extent completes (file range [192K, 256K)), we unpin its extent map and attempt to merge it with the previous extent map, for file range [128K, 192K), which succeeds since none of these extent maps have the EXTENT_MAP_MERGED flag set.

So we end up with 2 extent maps:

One for file range [0, 128K), with the flag EXTENT_MAP_MERGED set. One for file range [128K, 256K), with the flag EXTENT_MAP_MERGED set.

Since after merging extent maps we don't attempt to merge again, that is, merge the resulting extent map with the one that is now preceding it (and the one following it), we end up with those two extent maps, when we could have had a single extent map to represent the whole file.

Fix this by making mergeable_maps() ignore the EXTENT_MAP_MERGED flag. While this doesn't present any functional issue, it prevents the merging of extent maps which allows to save memory, and can make defrag not merging extents too (that will be addressed in the next patch).

Fixes 199257a78bb0 ("btrfs: defrag: don't use merged extent map for their generation check")
---
 fs/btrfs/extent_map.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
fs/btrfs/extent_map.c +6 -1
index 1f85b54c8f0c..67ce85ff0ae2 100644
@@ -233,7 +233,12 @@ static bool mergeable_maps(const struct extent_map *prev, const struct extent_ma
 	if (extent_map_end(prev) != next->start)
 		return false;
 
-	if (prev->flags != next->flags)
+	/*
+	 * The merged flag is not an on-disk flag, it just indicates we had the
+	 * extent maps of 2 (or more) adjacent extents merged, so factor it out.
+	 */
+	if ((prev->flags & ~EXTENT_FLAG_MERGED) !=
+	    (next->flags & ~EXTENT_FLAG_MERGED))
 		return false;
 
 	if (next->disk_bytenr < EXTENT_MAP_LAST_BYTE - 1)
Signature · 1 line
2.45.2
#4 lore raw

PATCH 2/2 btrfs: fix defrag not merging contiguous extents due to merged extent maps

In reply to [email protected]

From: Filipe Manana <[email protected]>

When running defrag (manual defrag) against a file that has extents that are contiguous and we already have the respective extent maps loaded and merged, we end up not defragging the range covered by those contiguous extents. This happens when we have an extent map that was the result of merging multiple extent maps for contiguous extents and the length of the merged extent map is greater than or equals to the defrag threshold length.

The script below reproduces this scenario:

   $ cat test.sh
   #!/bin/bash

DEV=/dev/sdi
MNT=/mnt/sdi

mkfs.btrfs -f $DEV
mount $DEV $MNT

   # Create a 256K file with 4 extents of 64K each.
   xfs_io -f -c "falloc 0 64K" \
             -c "pwrite 0 64K" \
             -c "falloc 64K 64K" \
             -c "pwrite 64K 64K" \
             -c "falloc 128K 64K" \
             -c "pwrite 128K 64K" \
             -c "falloc 192K 64K" \
             -c "pwrite 192K 64K" \
             $MNT/foo

umount $MNT
echo -n "Initial number of file extent items: "
btrfs inspect-internal dump-tree -t 5 $DEV | grep EXTENT_DATA | wc -l

mount $DEV $MNT
# Read the whole file in order to load and merge extent maps. cat $MNT/foo > /dev/null

btrfs filesystem defragment -t 128K $MNT/foo
umount $MNT
echo -n "Number of file extent items after defrag with 128K threshold: " btrfs inspect-internal dump-tree -t 5 $DEV | grep EXTENT_DATA | wc -l

mount $DEV $MNT
# Read the whole file in order to load and merge extent maps. cat $MNT/foo > /dev/null

btrfs filesystem defragment -t 256K $MNT/foo
umount $MNT
echo -n "Number of file extent items after defrag with 256K threshold: " btrfs inspect-internal dump-tree -t 5 $DEV | grep EXTENT_DATA | wc -l

Running it:

   $ ./test.sh
   Initial number of file extent items: 4
   Number of file extent items after defrag with 128K threshold: 4
   Number of file extent items after defrag with 256K threshold: 4

The 4 extents don't get merged because we have an extent map with a size of 256K that is the result of merging the indiviual extent maps for each of the four 64K extents and at defrag_lookup_extent() we have a value of zero for the generation threshold ('newer_than' argument) since this is a manual defrag. As a consequence we don't call defrag_get_extent() to get an extent map representing a single file extent item in the inode's subvolume tree, so we end up using the merged extent map at defrag_collect_targets() and decide not to defrag.

Fix this by updating defrag_lookup_extent() to always discard extent maps that were merged and call defrag_get_extent() regardless of the minimum generation threshold ('newer_than' argument).

A test case for fstests will be sent along soon.

Fixes 199257a78bb0 ("btrfs: defrag: don't use merged extent map for their generation check")
---
 fs/btrfs/defrag.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)
fs/btrfs/defrag.c +5 -5
index b95ef44c326b..968dae953948 100644
@@ -763,12 +763,12 @@ static struct extent_map *defrag_lookup_extent(struct inode *inode, u64 start,
 	 * We can get a merged extent, in that case, we need to re-search
 	 * tree to get the original em for defrag.
 	 *
-	 * If @newer_than is 0 or em::generation < newer_than, we can trust
-	 * this em, as either we don't care about the generation, or the
-	 * merged extent map will be rejected anyway.
+	 * This is because even if we have adjacent extents that are contiguous
+	 * and compatible (same type and flags), we still want to defrag them
+	 * so that we use less metadata (extent items in the extent tree and
+	 * file extent items in the inode's subvolume tree).
 	 */
-	if (em && (em->flags & EXTENT_FLAG_MERGED) &&
-	    newer_than && em->generation >= newer_than) {
+	if (em && (em->flags & EXTENT_FLAG_MERGED)) {
 		free_extent_map(em);
 		em = NULL;
 	}
Signature · 1 line
2.45.2
#2 lore raw

Re: [PATCH 1/2] btrfs: fix extent map merging not happening for adjacent extents

In reply to [email protected]
Quoted 66 lines · On 30/10/24 01:22, [email protected] wrote:

From: Filipe Manana <[email protected]>

If we have 3 or more adjacent extents in a file, that is, consecutive file extent items pointing to adjacent extents, within a contiguous file range and compatible flags, we end up not merging all the extents into a single extent map.

For example:

   $ mkfs.btrfs -f /dev/sdc
   $ mount /dev/sdc /mnt/sdc
   $ xfs_io -f -d -c "pwrite -b 64K 0 64K" \
                  -c "pwrite -b 64K 64K 64K" \
                  -c "pwrite -b 64K 128K 64K" \
                  -c "pwrite -b 64K 192K 64K" \
                  /mnt/sdc/foo

After all the ordered extents complete we unpin the extent maps and try to merge them, but instead of getting a single extent map we get two because:

1) When the first ordered extent completes (file range [0, 64K)) we unpin its extent map and attempt to merge it with the extent map for the range [64K, 128K), but we can't because that extent map is still pinned;

2) When the second ordered extent completes (file range [64K, 128K)), we unpin its extent map and merge it with the previous extent map, for file range [0, 64K), but we can't merge with the next extent map, for the file range [128K, 192K), because this one is still pinned.

The merged extent map for the file range [0, 128K) gets the flag EXTENT_MAP_MERGED set;

3) When the third ordered extent completes (file range [128K, 192K)), we unpin its exent map and attempt to merge it with the previous extent map, for file range [0, 128K), but we can't because that extent map has the flag EXTENT_MAP_MERGED set (mergeable_maps() returns false due to different flags) while the extent map for the range [128K, 192K) doesn't have that flag set.

We also can't merge it with the next extent map, for file range [192K, 256K), because that one is still pinned.

At this moment we have 3 extent maps:

One for file range [0, 128K), with the flag EXTENT_MAP_MERGED set. One for file range [128K, 192K).
One for file range [192K, 256K) which is still pinned;

4) When the fourth and final extent completes (file range [192K, 256K)), we unpin its extent map and attempt to merge it with the previous extent map, for file range [128K, 192K), which succeeds since none of these extent maps have the EXTENT_MAP_MERGED flag set.

So we end up with 2 extent maps:

One for file range [0, 128K), with the flag EXTENT_MAP_MERGED set. One for file range [128K, 256K), with the flag EXTENT_MAP_MERGED set.

Since after merging extent maps we don't attempt to merge again, that is, merge the resulting extent map with the one that is now preceding it (and the one following it), we end up with those two extent maps, when we could have had a single extent map to represent the whole file.

Quoted 5 lines

Fix this by making mergeable_maps() ignore the EXTENT_MAP_MERGED flag. While this doesn't present any functional issue, it prevents the merging of extent maps which allows to save memory, and can make defrag not merging extents too (that will be addressed in the next patch).

Why don’t the extents merge, even after mount-recycles and multiple manual defrag runs, without this fix?

Thanks, Anand

Quoted 24 lines
Fixes 199257a78bb0 ("btrfs: defrag: don't use merged extent map for their generation check")
---
  fs/btrfs/extent_map.c | 7 ++++++-
  1 file changed, 6 insertions(+), 1 deletion(-)
fs/btrfs/extent_map.c +6 -1
index 1f85b54c8f0c..67ce85ff0ae2 100644
@@ -233,7 +233,12 @@ static bool mergeable_maps(const struct extent_map *prev, const struct extent_ma
  	if (extent_map_end(prev) != next->start)
  		return false;
 
-	if (prev->flags != next->flags)
+	/*
+	 * The merged flag is not an on-disk flag, it just indicates we had the
+	 * extent maps of 2 (or more) adjacent extents merged, so factor it out.
+	 */
+	if ((prev->flags & ~EXTENT_FLAG_MERGED) !=
+	    (next->flags & ~EXTENT_FLAG_MERGED))
  		return false;
 
  	if (next->disk_bytenr < EXTENT_MAP_LAST_BYTE - 1)
#3 lore raw

Re: [PATCH 1/2] btrfs: fix extent map merging not happening for adjacent extents

Quoted 68 lines · Anand Jain
Quoted 66 lines · On 30/10/24 01:22, [email protected] wrote:

From: Filipe Manana <[email protected]>

If we have 3 or more adjacent extents in a file, that is, consecutive file extent items pointing to adjacent extents, within a contiguous file range and compatible flags, we end up not merging all the extents into a single extent map.

For example:

   $ mkfs.btrfs -f /dev/sdc
   $ mount /dev/sdc /mnt/sdc
   $ xfs_io -f -d -c "pwrite -b 64K 0 64K" \
                  -c "pwrite -b 64K 64K 64K" \
                  -c "pwrite -b 64K 128K 64K" \
                  -c "pwrite -b 64K 192K 64K" \
                  /mnt/sdc/foo

After all the ordered extents complete we unpin the extent maps and try to merge them, but instead of getting a single extent map we get two because:

1) When the first ordered extent completes (file range [0, 64K)) we unpin its extent map and attempt to merge it with the extent map for the range [64K, 128K), but we can't because that extent map is still pinned;

2) When the second ordered extent completes (file range [64K, 128K)), we unpin its extent map and merge it with the previous extent map, for file range [0, 64K), but we can't merge with the next extent map, for the file range [128K, 192K), because this one is still pinned.

The merged extent map for the file range [0, 128K) gets the flag EXTENT_MAP_MERGED set;

3) When the third ordered extent completes (file range [128K, 192K)), we unpin its exent map and attempt to merge it with the previous extent map, for file range [0, 128K), but we can't because that extent map has the flag EXTENT_MAP_MERGED set (mergeable_maps() returns false due to different flags) while the extent map for the range [128K, 192K) doesn't have that flag set.

We also can't merge it with the next extent map, for file range [192K, 256K), because that one is still pinned.

At this moment we have 3 extent maps:

One for file range [0, 128K), with the flag EXTENT_MAP_MERGED set. One for file range [128K, 192K).
One for file range [192K, 256K) which is still pinned;

4) When the fourth and final extent completes (file range [192K, 256K)), we unpin its extent map and attempt to merge it with the previous extent map, for file range [128K, 192K), which succeeds since none of these extent maps have the EXTENT_MAP_MERGED flag set.

So we end up with 2 extent maps:

One for file range [0, 128K), with the flag EXTENT_MAP_MERGED set. One for file range [128K, 256K), with the flag EXTENT_MAP_MERGED set.

Since after merging extent maps we don't attempt to merge again, that is, merge the resulting extent map with the one that is now preceding it (and the one following it), we end up with those two extent maps, when we could have had a single extent map to represent the whole file.

Quoted 8 lines
Quoted 5 lines

Fix this by making mergeable_maps() ignore the EXTENT_MAP_MERGED flag. While this doesn't present any functional issue, it prevents the merging of extent maps which allows to save memory, and can make defrag not merging extents too (that will be addressed in the next patch).

Why don’t the extents merge, even after mount-recycles and multiple manual defrag runs, without this fix?

Why do you think mount recycles would make any difference? Whenever extent maps are merged they get the merge flag set.
As for defrag and merged extent maps, that's explained in the next patch.

Quoted 29 lines

Thanks, Anand

Quoted 24 lines
Fixes 199257a78bb0 ("btrfs: defrag: don't use merged extent map for their generation check")
---
  fs/btrfs/extent_map.c | 7 ++++++-
  1 file changed, 6 insertions(+), 1 deletion(-)
fs/btrfs/extent_map.c +6 -1
index 1f85b54c8f0c..67ce85ff0ae2 100644
@@ -233,7 +233,12 @@ static bool mergeable_maps(const struct extent_map *prev, const struct extent_ma
      if (extent_map_end(prev) != next->start)
              return false;
 
-     if (prev->flags != next->flags)
+     /*
+      * The merged flag is not an on-disk flag, it just indicates we had the
+      * extent maps of 2 (or more) adjacent extents merged, so factor it out.
+      */
+     if ((prev->flags & ~EXTENT_FLAG_MERGED) !=
+         (next->flags & ~EXTENT_FLAG_MERGED))
              return false;
 
      if (next->disk_bytenr < EXTENT_MAP_LAST_BYTE - 1)
Reviewed-by on the v1 series
#5 lore raw
In reply to [email protected]
Quoted 9 lines · 在 2024/10/30 03:52, [email protected] 写道:

From: Filipe Manana <[email protected]>

Some fixes for extent map merging not happened when it should (which avoids saving some memory) and defrag not merging contiguous extents when it should due to merged extent maps. Details in the change logs.

Filipe Manana (2):
btrfs: fix extent map merging not happening for adjacent extents
btrfs: fix defrag not merging contiguous extents due to merged extent maps

Thanks,
Qu

Quoted 5 lines
  fs/btrfs/defrag.c     | 10 +++++-----
  fs/btrfs/extent_map.c |  7 ++++++-
  2 files changed, 11 insertions(+), 6 deletions(-)