[PATCH 0/2] Some boundary error bugfix related to XFS fsmap.

[PATCH 0/2] Some boundary error bugfix related to XFS fsmap.

[Zizhi Wo]

Prior to this, I had already sent out a patchset related to xfs fsmap
bugfix, which mainly introduced "info->end_daddr" to fix omitted extents[1]
and Darrick had already sent out a patchbomb for merging into stable[2],
which included my previous patches.

However, I recently discovered two new fsmap problems...What follows is a
brief description of them:

Patch 1: In this scenario, fsmap lost one block count. The root cause is
that during the calculation of highkey, the calculation of start_block is
missing an increment by one, which leads to the last query missing one
This problem is resolved by adding a sentinel node.

Patch 2: In this scenario, the fsmap query for realtime deivce may display
extra intervals. This is due to an extra increase in "end_rtb". The issue
is resolved by adjusting the relevant calculations. And this patch depends
on the previous patch that introduced "info->end_daddr".

[1] https://lore.kernel.org/all/20240819005320.304211-1-wozizhi@huawei.com/
[2] https://lore.kernel.org/all/172437083728.56860.10056307551249098606.stgit@frogsfrogsfrogs/ 

Zizhi Wo (2):
  xfs: Fix missing block calculations in xfs datadev fsmap
  xfs: Fix incorrect parameter calculation in rt fsmap

 fs/xfs/libxfs/xfs_rtbitmap.c |  4 +---
 fs/xfs/xfs_fsmap.c           | 39 +++++++++++++++++++++++++++++++-----
 2 files changed, 35 insertions(+), 8 deletions(-)

-- 
2.39.2

[PATCH 1/2] xfs: Fix missing block calculations in xfs datadev fsmap

[Zizhi Wo]

In xfs datadev fsmap query, I noticed a missing block calculation problem:
[root@fedora ~]# xfs_db -r -c "sb 0" -c "p" /dev/vdb
magicnum = 0x58465342
blocksize = 4096
dblocks = 5242880
......
[root@fedora ~]# xfs_io -c 'fsmap -vvvv' /mnt
...
30: 253:16 [31457384..41943031]: free space            3  (104..10485751)    10485648

(41943031 + 1) / 8 = 5242879 != 5242880
We missed one block in our fsmap calculation!

The root cause of the problem lies in __xfs_getfsmap_datadev(), where the
calculation of "end_fsb" requires a classification discussion. If "end_fsb"
is calculated based on "eofs", we need to add an extra sentinel node for
subsequent length calculations. Otherwise, one block will be missed. If
"end_fsb" is calculated based on "keys[1]", then there is no need to add an
extra node. Because "keys[1]" itself is unreachable, it cancels out one of
the additions. The diagram below illustrates this:

|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|-----eofs
|---------------|---------------------|
a       n       b         n+1         c

Assume that eofs is 16, the start address of the previous query is block n,
sector 0, and the length is 1, so the "info->next" is at point b, sector 8.
In the last query, suppose the "rm_startblock" calculated based on
"eofs - 1" is the last block n+1 at point b. All we get is the starting
address of the block, not the end. Therefore, an additional sentinel node
needs to be added to move it to point c. After that, subtracting one from
the other will yield the remaining 1.

Although we can now calculate the exact last query using "info->end_daddr",
we will still get an incorrect value if the device at this point is not the
boundary device specified by "keys[1]", as "end_daddr" is still the initial
value. Therefore, the eofs situation here needs to be corrected. The issue
is resolved by adding a sentinel node.

Fixes: e89c041338ed ("xfs: implement the GETFSMAP ioctl")
Signed-off-by: Zizhi Wo <wozizhi@huawei.com>
---
 fs/xfs/xfs_fsmap.c | 19 +++++++++++++++++--
 1 file changed, 17 insertions(+), 2 deletions(-)

diff --git a/fs/xfs/xfs_fsmap.c b/fs/xfs/xfs_fsmap.c
index 85dbb46452ca..8a2dfe96dae7 100644
--- a/fs/xfs/xfs_fsmap.c
+++ b/fs/xfs/xfs_fsmap.c
@@ -596,12 +596,27 @@ __xfs_getfsmap_datadev(
 	xfs_agnumber_t			end_ag;
 	uint64_t			eofs;
 	int				error = 0;
+	int				sentinel = 0;
 
 	eofs = XFS_FSB_TO_BB(mp, mp->m_sb.sb_dblocks);
 	if (keys[0].fmr_physical >= eofs)
 		return 0;
 	start_fsb = XFS_DADDR_TO_FSB(mp, keys[0].fmr_physical);
-	end_fsb = XFS_DADDR_TO_FSB(mp, min(eofs - 1, keys[1].fmr_physical));
+	/*
+	 * For the case of eofs, we need to add a sentinel node;
+	 * otherwise, one block will be missed when calculating the length
+	 * in the last query.
+	 * For the case of key[1], there is no need to add a sentinel node
+	 * because it already represents a value that cannot be reached.
+	 * For the case where key[1] after shifting is within the same
+	 * block as the starting address, it is resolved using end_daddr.
+	 */
+	if (keys[1].fmr_physical > eofs - 1) {
+		sentinel = 1;
+		end_fsb = XFS_DADDR_TO_FSB(mp, eofs - 1);
+	} else {
+		end_fsb = XFS_DADDR_TO_FSB(mp, keys[1].fmr_physical);
+	}
 
 	/*
 	 * Convert the fsmap low/high keys to AG based keys.  Initialize
@@ -649,7 +664,7 @@ __xfs_getfsmap_datadev(
 		info->pag = pag;
 		if (pag->pag_agno == end_ag) {
 			info->high.rm_startblock = XFS_FSB_TO_AGBNO(mp,
-					end_fsb);
+					end_fsb) + sentinel;
 			info->high.rm_offset = XFS_BB_TO_FSBT(mp,
 					keys[1].fmr_offset);
 			error = xfs_fsmap_owner_to_rmap(&info->high, &keys[1]);
-- 
2.39.2

[PATCH 2/2] xfs: Fix incorrect parameter calculation in rt fsmap

[Zizhi Wo]

I noticed a bug related to xfs realtime device fsmap:
[root@fedora ~]# xfs_io -c 'fsmap -vvvv -r' /mnt
 EXT: DEV    BLOCK-RANGE         OWNER            FILE-OFFSET      AG AG-OFFSET          TOTAL
   0: 253:48 [0..7]:             unknown                                                     8
   1: 253:48 [8..1048575]:       free space                                            1048568
   2: 253:48 [1048576..1050623]: unknown                                                  2048
   3: 253:48 [1050624..2097151]: free space                                            1046528

Bug:
[root@fedora ~]# xfs_io -c 'fsmap -vvvv -r 1050621 1050621' /mnt
 EXT: DEV    BLOCK-RANGE         OWNER            FILE-OFFSET      AG AG-OFFSET        TOTAL
   0: 253:48 [1050621..1050623]: unknown                                                   3
   1: 253:48 [1050624..1050631]: free space                                                8
Normally, we should not get any results, but we do get two queries.

The root cause of this problem lies in the calculation of "end_rtb" in
xfs_getfsmap_rtdev_rtbitmap(), which uses XFS_BB_TO_FSB method (round up).
However, in the subsequent call to xfs_rtalloc_query_range(), "high_rec"
calculated based on "end_rtb" has a semantic meaning of being reachable
within the loop. The first round of the loop in xfs_rtalloc_query_range()
doesn't find any free extents. But after incrementing "rtstart" by 1, start
still does not exceed "high_key", and the second round of the loop entered.
It finds free extent and obtains the first unknown extent by subtracting it
from "info->next_daddr". Even though we can accurately handle it through
"info->end_daddr", two incorrect extents has already been returned before
the last query. The main call stack is as follows:

xfs_getfsmap_rtdev_rtbitmap
  // rounded up
  end_rtb = XFS_BB_TO_FSB(..., keys[1].fmr_physical)
  ahigh.ar_startext = xfs_rtb_to_rtxup(mp, end_rtb)
  xfs_rtalloc_query_range
    // high_key is calculated based on end_rtb
    high_key = min(high_rec->ar_startext, ...)
    while (rtstart <= high_key)
      // First loop, doesn't find free extent
      xfs_rtcheck_range
      rtstart = rtend + 1
      // Second loop, the free extent outside the query interval is found
      xfs_getfsmap_rtdev_rtbitmap_helper
        // unknown and free were printed out together in the second round
        xfs_getfsmap_helper

The issue is resolved by adjusting the relevant calculations. Both the loop
exit condition in the xfs_rtalloc_query_range() and the length calculation
condition (high_key - start + 1) in the xfs_rtfind_forw() reflect the open
interval semantics of "high_key". Therefore, when calculating "end_rtb",
XFS_BB_TO_FSBT is used. In addition, in order to satisfy the close interval
semantics, "key[1].fmr_physical" needs to be decremented by 1. For the
non-eofs case, there is no need to worry about over-counting because we can
accurately count the block number through "info->end_daddr".

After applying this patch, the above problem have been solved:
[root@fedora ~]# xfs_io -c 'fsmap -vvvv -r 1050621 1050621' /mnt
[root@fedora ~]#

Fixes: 4c934c7dd60c ("xfs: report realtime space information via the rtbitmap")
Signed-off-by: Zizhi Wo <wozizhi@huawei.com>
---
 fs/xfs/libxfs/xfs_rtbitmap.c |  4 +---
 fs/xfs/xfs_fsmap.c           | 20 +++++++++++++++++---
 2 files changed, 18 insertions(+), 6 deletions(-)

diff --git a/fs/xfs/libxfs/xfs_rtbitmap.c b/fs/xfs/libxfs/xfs_rtbitmap.c
index 386b672c5058..7af4e7afda7d 100644
--- a/fs/xfs/libxfs/xfs_rtbitmap.c
+++ b/fs/xfs/libxfs/xfs_rtbitmap.c
@@ -1034,8 +1034,7 @@ xfs_rtalloc_query_range(
 
 	if (low_rec->ar_startext > high_rec->ar_startext)
 		return -EINVAL;
-	if (low_rec->ar_startext >= mp->m_sb.sb_rextents ||
-	    low_rec->ar_startext == high_rec->ar_startext)
+	if (low_rec->ar_startext >= mp->m_sb.sb_rextents)
 		return 0;
 
 	high_key = min(high_rec->ar_startext, mp->m_sb.sb_rextents - 1);
@@ -1057,7 +1056,6 @@ xfs_rtalloc_query_range(
 		if (is_free) {
 			rec.ar_startext = rtstart;
 			rec.ar_extcount = rtend - rtstart + 1;
-
 			error = fn(mp, tp, &rec, priv);
 			if (error)
 				break;
diff --git a/fs/xfs/xfs_fsmap.c b/fs/xfs/xfs_fsmap.c
index 8a2dfe96dae7..42c4b94b0493 100644
--- a/fs/xfs/xfs_fsmap.c
+++ b/fs/xfs/xfs_fsmap.c
@@ -515,11 +515,20 @@ xfs_getfsmap_rtdev_rtbitmap(
 	int				error;
 
 	eofs = XFS_FSB_TO_BB(mp, xfs_rtx_to_rtb(mp, mp->m_sb.sb_rextents));
-	if (keys[0].fmr_physical >= eofs)
+	if (keys[0].fmr_physical >= eofs ||
+		keys[0].fmr_physical == keys[1].fmr_physical)
 		return 0;
 	start_rtb = XFS_BB_TO_FSBT(mp,
 				keys[0].fmr_physical + keys[0].fmr_length);
-	end_rtb = XFS_BB_TO_FSB(mp, min(eofs - 1, keys[1].fmr_physical));
+	/*
+	 * The passed keys[1] is an unreachable value, while "end_rtb" is used
+	 * to calculate "ahigh.ar_startext", serving as an input parameter for
+	 * xfs_rtalloc_query_range(), which is a value that can be reached.
+	 * Therefore, it is necessary to use "keys[1].fmr_physical - 1" here.
+	 * And because of the semantics of "end_rtb", it needs to be
+	 * supplemented by 1 in the last calculation.
+	 */
+	end_rtb = XFS_BB_TO_FSBT(mp, min(eofs - 1, keys[1].fmr_physical - 1));
 
 	info->missing_owner = XFS_FMR_OWN_UNKNOWN;
 
@@ -549,9 +558,14 @@ xfs_getfsmap_rtdev_rtbitmap(
 	/*
 	 * Report any gaps at the end of the rtbitmap by simulating a null
 	 * rmap starting at the block after the end of the query range.
+	 * For the boundary case of eofs, we need to increment the count
+	 * by 1 to prevent omission in block statistics.
+	 * For the boundary case of non-eofs, even if incrementing by 1
+	 * may lead to over-counting, it doesn't matter because it is
+	 * handled by "info->end_daddr" in this situation, not "ahigh".
 	 */
 	info->last = true;
-	ahigh.ar_startext = min(mp->m_sb.sb_rextents, ahigh.ar_startext);
+	ahigh.ar_startext = min(mp->m_sb.sb_rextents, ahigh.ar_startext + 1);
 
 	error = xfs_getfsmap_rtdev_rtbitmap_helper(mp, tp, &ahigh, info);
 	if (error)
-- 
2.39.2

Re: [PATCH 0/2] Some boundary error bugfix related to XFS fsmap.

[Zizhi Wo]

friendly ping

在 2024/8/26 11:10, Zizhi Wo 写道:
> Prior to this, I had already sent out a patchset related to xfs fsmap
> bugfix, which mainly introduced "info->end_daddr" to fix omitted extents[1]
> and Darrick had already sent out a patchbomb for merging into stable[2],
> which included my previous patches.
> 
> However, I recently discovered two new fsmap problems...What follows is a
> brief description of them:
> 
> Patch 1: In this scenario, fsmap lost one block count. The root cause is
> that during the calculation of highkey, the calculation of start_block is
> missing an increment by one, which leads to the last query missing one
> This problem is resolved by adding a sentinel node.
> 
> Patch 2: In this scenario, the fsmap query for realtime deivce may display
> extra intervals. This is due to an extra increase in "end_rtb". The issue
> is resolved by adjusting the relevant calculations. And this patch depends
> on the previous patch that introduced "info->end_daddr".
> 
> [1] https://lore.kernel.org/all/20240819005320.304211-1-wozizhi@huawei.com/
> [2] https://lore.kernel.org/all/172437083728.56860.10056307551249098606.stgit@frogsfrogsfrogs/
> 
> Zizhi Wo (2):
>    xfs: Fix missing block calculations in xfs datadev fsmap
>    xfs: Fix incorrect parameter calculation in rt fsmap
> 
>   fs/xfs/libxfs/xfs_rtbitmap.c |  4 +---
>   fs/xfs/xfs_fsmap.c           | 39 +++++++++++++++++++++++++++++++-----
>   2 files changed, 35 insertions(+), 8 deletions(-)
> 

Re: [PATCH 0/2] Some boundary error bugfix related to XFS fsmap.

[Darrick J. Wong]

On Thu, Aug 29, 2024 at 07:24:55PM +0800, Zizhi Wo wrote:
> friendly ping

Sorry, I'm not going to get to this until late September.

--D

> 在 2024/8/26 11:10, Zizhi Wo 写道:
> > Prior to this, I had already sent out a patchset related to xfs fsmap
> > bugfix, which mainly introduced "info->end_daddr" to fix omitted extents[1]
> > and Darrick had already sent out a patchbomb for merging into stable[2],
> > which included my previous patches.
> > 
> > However, I recently discovered two new fsmap problems...What follows is a
> > brief description of them:
> > 
> > Patch 1: In this scenario, fsmap lost one block count. The root cause is
> > that during the calculation of highkey, the calculation of start_block is
> > missing an increment by one, which leads to the last query missing one
> > This problem is resolved by adding a sentinel node.
> > 
> > Patch 2: In this scenario, the fsmap query for realtime deivce may display
> > extra intervals. This is due to an extra increase in "end_rtb". The issue
> > is resolved by adjusting the relevant calculations. And this patch depends
> > on the previous patch that introduced "info->end_daddr".
> > 
> > [1] https://lore.kernel.org/all/20240819005320.304211-1-wozizhi@huawei.com/
> > [2] https://lore.kernel.org/all/172437083728.56860.10056307551249098606.stgit@frogsfrogsfrogs/
> > 
> > Zizhi Wo (2):
> >    xfs: Fix missing block calculations in xfs datadev fsmap
> >    xfs: Fix incorrect parameter calculation in rt fsmap
> > 
> >   fs/xfs/libxfs/xfs_rtbitmap.c |  4 +---
> >   fs/xfs/xfs_fsmap.c           | 39 +++++++++++++++++++++++++++++++-----
> >   2 files changed, 35 insertions(+), 8 deletions(-)
> > 
> 

Re: [PATCH 0/2] Some boundary error bugfix related to XFS fsmap.

[Zizhi Wo]

在 2024/9/3 3:08, Darrick J. Wong 写道:
> On Thu, Aug 29, 2024 at 07:24:55PM +0800, Zizhi Wo wrote:
>> friendly ping
> 
> Sorry, I'm not going to get to this until late September.
> 
> --D

OK, I've got it. Have a nice holiday😀

Thanks,
Zizhi Wo

> 
>> 在 2024/8/26 11:10, Zizhi Wo 写道:
>>> Prior to this, I had already sent out a patchset related to xfs fsmap
>>> bugfix, which mainly introduced "info->end_daddr" to fix omitted extents[1]
>>> and Darrick had already sent out a patchbomb for merging into stable[2],
>>> which included my previous patches.
>>>
>>> However, I recently discovered two new fsmap problems...What follows is a
>>> brief description of them:
>>>
>>> Patch 1: In this scenario, fsmap lost one block count. The root cause is
>>> that during the calculation of highkey, the calculation of start_block is
>>> missing an increment by one, which leads to the last query missing one
>>> This problem is resolved by adding a sentinel node.
>>>
>>> Patch 2: In this scenario, the fsmap query for realtime deivce may display
>>> extra intervals. This is due to an extra increase in "end_rtb". The issue
>>> is resolved by adjusting the relevant calculations. And this patch depends
>>> on the previous patch that introduced "info->end_daddr".
>>>
>>> [1] https://lore.kernel.org/all/20240819005320.304211-1-wozizhi@huawei.com/
>>> [2] https://lore.kernel.org/all/172437083728.56860.10056307551249098606.stgit@frogsfrogsfrogs/
>>>
>>> Zizhi Wo (2):
>>>     xfs: Fix missing block calculations in xfs datadev fsmap
>>>     xfs: Fix incorrect parameter calculation in rt fsmap
>>>
>>>    fs/xfs/libxfs/xfs_rtbitmap.c |  4 +---
>>>    fs/xfs/xfs_fsmap.c           | 39 +++++++++++++++++++++++++++++++-----
>>>    2 files changed, 35 insertions(+), 8 deletions(-)
>>>
>>
> 

Re: [PATCH 0/2] Some boundary error bugfix related to XFS fsmap.

[Zizhi Wo]

Hi!

Here are two patches that address fsmap statistics errors. I sent out
this version in August, and I hope someone can take some time to review
them. So friendly ping. Thanks in advance!


在 2024/9/3 3:08, Darrick J. Wong 写道:
> On Thu, Aug 29, 2024 at 07:24:55PM +0800, Zizhi Wo wrote:
>> friendly ping
> 
> Sorry, I'm not going to get to this until late September.
> 
> --D
> 
>> 在 2024/8/26 11:10, Zizhi Wo 写道:
>>> Prior to this, I had already sent out a patchset related to xfs fsmap
>>> bugfix, which mainly introduced "info->end_daddr" to fix omitted extents[1]
>>> and Darrick had already sent out a patchbomb for merging into stable[2],
>>> which included my previous patches.
>>>
>>> However, I recently discovered two new fsmap problems...What follows is a
>>> brief description of them:
>>>
>>> Patch 1: In this scenario, fsmap lost one block count. The root cause is
>>> that during the calculation of highkey, the calculation of start_block is
>>> missing an increment by one, which leads to the last query missing one
>>> This problem is resolved by adding a sentinel node.
>>>
>>> Patch 2: In this scenario, the fsmap query for realtime deivce may display
>>> extra intervals. This is due to an extra increase in "end_rtb". The issue
>>> is resolved by adjusting the relevant calculations. And this patch depends
>>> on the previous patch that introduced "info->end_daddr".
>>>
>>> [1] https://lore.kernel.org/all/20240819005320.304211-1-wozizhi@huawei.com/
>>> [2] https://lore.kernel.org/all/172437083728.56860.10056307551249098606.stgit@frogsfrogsfrogs/
>>>
>>> Zizhi Wo (2):
>>>     xfs: Fix missing block calculations in xfs datadev fsmap
>>>     xfs: Fix incorrect parameter calculation in rt fsmap
>>>
>>>    fs/xfs/libxfs/xfs_rtbitmap.c |  4 +---
>>>    fs/xfs/xfs_fsmap.c           | 39 +++++++++++++++++++++++++++++++-----
>>>    2 files changed, 35 insertions(+), 8 deletions(-)
>>>
>>
> 

Re: [PATCH 0/2] Some boundary error bugfix related to XFS fsmap.

[Zizhi Wo]

在 2024/10/9 21:01, Zizhi Wo 写道:
> Hi!
> 
> Here are two patches that address fsmap statistics errors. I sent out
> this version in August, and I hope someone can take some time to review
> them. So friendly ping. Thanks in advance!

friendly ping again（￣。。￣）

> 
> 
> 在 2024/9/3 3:08, Darrick J. Wong 写道:
>> On Thu, Aug 29, 2024 at 07:24:55PM +0800, Zizhi Wo wrote:
>>> friendly ping
>>
>> Sorry, I'm not going to get to this until late September.
>>
>> --D
>>
>>> 在 2024/8/26 11:10, Zizhi Wo 写道:
>>>> Prior to this, I had already sent out a patchset related to xfs fsmap
>>>> bugfix, which mainly introduced "info->end_daddr" to fix omitted 
>>>> extents[1]
>>>> and Darrick had already sent out a patchbomb for merging into 
>>>> stable[2],
>>>> which included my previous patches.
>>>>
>>>> However, I recently discovered two new fsmap problems...What follows 
>>>> is a
>>>> brief description of them:
>>>>
>>>> Patch 1: In this scenario, fsmap lost one block count. The root 
>>>> cause is
>>>> that during the calculation of highkey, the calculation of 
>>>> start_block is
>>>> missing an increment by one, which leads to the last query missing one
>>>> This problem is resolved by adding a sentinel node.
>>>>
>>>> Patch 2: In this scenario, the fsmap query for realtime deivce may 
>>>> display
>>>> extra intervals. This is due to an extra increase in "end_rtb". The 
>>>> issue
>>>> is resolved by adjusting the relevant calculations. And this patch 
>>>> depends
>>>> on the previous patch that introduced "info->end_daddr".
>>>>
>>>> [1] 
>>>> https://lore.kernel.org/all/20240819005320.304211-1-wozizhi@huawei.com/
>>>> [2] 
>>>> https://lore.kernel.org/all/172437083728.56860.10056307551249098606.stgit@frogsfrogsfrogs/
>>>>
>>>> Zizhi Wo (2):
>>>>     xfs: Fix missing block calculations in xfs datadev fsmap
>>>>     xfs: Fix incorrect parameter calculation in rt fsmap
>>>>
>>>>    fs/xfs/libxfs/xfs_rtbitmap.c |  4 +---
>>>>    fs/xfs/xfs_fsmap.c           | 39 
>>>> +++++++++++++++++++++++++++++++-----
>>>>    2 files changed, 35 insertions(+), 8 deletions(-)
>>>>
>>>
>>
> 
> 

Re: [PATCH 1/2] xfs: Fix missing block calculations in xfs datadev fsmap

[Darrick J. Wong]

On Mon, Aug 26, 2024 at 11:10:04AM +0800, Zizhi Wo wrote:
> In xfs datadev fsmap query, I noticed a missing block calculation problem:
> [root@fedora ~]# xfs_db -r -c "sb 0" -c "p" /dev/vdb
> magicnum = 0x58465342
> blocksize = 4096
> dblocks = 5242880
> ......
> [root@fedora ~]# xfs_io -c 'fsmap -vvvv' /mnt
> ...
> 30: 253:16 [31457384..41943031]: free space            3  (104..10485751)    10485648
> 
> (41943031 + 1) / 8 = 5242879 != 5242880
> We missed one block in our fsmap calculation!

Eek.

> The root cause of the problem lies in __xfs_getfsmap_datadev(), where the
> calculation of "end_fsb" requires a classification discussion. If "end_fsb"
> is calculated based on "eofs", we need to add an extra sentinel node for
> subsequent length calculations. Otherwise, one block will be missed. If
> "end_fsb" is calculated based on "keys[1]", then there is no need to add an
> extra node. Because "keys[1]" itself is unreachable, it cancels out one of
> the additions. The diagram below illustrates this:
> 
> |0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|-----eofs
> |---------------|---------------------|
> a       n       b         n+1         c
> 
> Assume that eofs is 16, the start address of the previous query is block n,
> sector 0, and the length is 1, so the "info->next" is at point b, sector 8.
> In the last query, suppose the "rm_startblock" calculated based on
> "eofs - 1" is the last block n+1 at point b. All we get is the starting
> address of the block, not the end. Therefore, an additional sentinel node
> needs to be added to move it to point c. After that, subtracting one from
> the other will yield the remaining 1.
> 
> Although we can now calculate the exact last query using "info->end_daddr",
> we will still get an incorrect value if the device at this point is not the
> boundary device specified by "keys[1]", as "end_daddr" is still the initial
> value. Therefore, the eofs situation here needs to be corrected. The issue
> is resolved by adding a sentinel node.

Why don't we set end_daddr unconditionally, then?

Hmm, looking at the end_daddr usage in fsmap.c, I think it's wrong.  If
end_daddr is set at all, it's set either to the last sector for which
the user wants a mapping; or it's set to the last sector for the device.
But then look at how we use it:

	if (info->last...)
		frec->start_daddr = info->end_daddr;

	...

	/* "report the gap..."
	if (frec->start_daddr > info->next_daddr) {
		fmr.fmr_length = frec->start_daddr - info->next_daddr;
	}

This is wrong -- we're using start_daddr to compute the distance from
the last mapping that we output up to the end of the range that we want.
The "end of the range" is modeled with a phony rmap record that starts
at the first fsblock after that range.

IOWs, that assignment should have been
frec->start_daddr = info->end_daddr + 1.

Granted in August the codebase was less clear about the difference
between rec_daddr and rmap->rm_startblock.  For 6.13, hch cleaned all
that up -- rec_daddr is now called start_daddr and the fsmap code passes
rmap records with space numbers in units of daddrs via a new struct
xfs_fsmap_rec.  Unfortunately, that's all buried in the giant pile of
pull requests I sent a couple of days ago which hasn't shown up on
for-next yet.

https://lore.kernel.org/linux-xfs/173084396955.1871025.18156568347365549855.stgit@frogsfrogsfrogs/

So I think I know how to fix this against the 6.13 codebase, but I'm
going to take a slightly different approach than yours...

> Fixes: e89c041338ed ("xfs: implement the GETFSMAP ioctl")
> Signed-off-by: Zizhi Wo <wozizhi@huawei.com>
> ---
>  fs/xfs/xfs_fsmap.c | 19 +++++++++++++++++--
>  1 file changed, 17 insertions(+), 2 deletions(-)
> 
> diff --git a/fs/xfs/xfs_fsmap.c b/fs/xfs/xfs_fsmap.c
> index 85dbb46452ca..8a2dfe96dae7 100644
> --- a/fs/xfs/xfs_fsmap.c
> +++ b/fs/xfs/xfs_fsmap.c
> @@ -596,12 +596,27 @@ __xfs_getfsmap_datadev(
>  	xfs_agnumber_t			end_ag;
>  	uint64_t			eofs;
>  	int				error = 0;
> +	int				sentinel = 0;
>  
>  	eofs = XFS_FSB_TO_BB(mp, mp->m_sb.sb_dblocks);
>  	if (keys[0].fmr_physical >= eofs)
>  		return 0;
>  	start_fsb = XFS_DADDR_TO_FSB(mp, keys[0].fmr_physical);
> -	end_fsb = XFS_DADDR_TO_FSB(mp, min(eofs - 1, keys[1].fmr_physical));
> +	/*
> +	 * For the case of eofs, we need to add a sentinel node;
> +	 * otherwise, one block will be missed when calculating the length
> +	 * in the last query.
> +	 * For the case of key[1], there is no need to add a sentinel node
> +	 * because it already represents a value that cannot be reached.
> +	 * For the case where key[1] after shifting is within the same
> +	 * block as the starting address, it is resolved using end_daddr.
> +	 */
> +	if (keys[1].fmr_physical > eofs - 1) {
> +		sentinel = 1;
> +		end_fsb = XFS_DADDR_TO_FSB(mp, eofs - 1);
> +	} else {
> +		end_fsb = XFS_DADDR_TO_FSB(mp, keys[1].fmr_physical);
> +	}

...because running against djwong-wtf, I actually see the same symptoms
for the realtime device.  So I think a better solution is to change
xfs_getfsmap to set end_daddr always, and then fix the off by one error.

I also don't really like "sentinel" values because they're not
intuitive.

I will also go update xfs/273 to check that there are no gaps in the
mappings returned, and that they go to where the filesystem thinks is
the end of the device.  Thanks for reporting this, sorry I was too busy
trying to get metadir/rtgroups done to look at this until now. :(

--D

>  
>  	/*
>  	 * Convert the fsmap low/high keys to AG based keys.  Initialize
> @@ -649,7 +664,7 @@ __xfs_getfsmap_datadev(
>  		info->pag = pag;
>  		if (pag->pag_agno == end_ag) {
>  			info->high.rm_startblock = XFS_FSB_TO_AGBNO(mp,
> -					end_fsb);
> +					end_fsb) + sentinel;
>  			info->high.rm_offset = XFS_BB_TO_FSBT(mp,
>  					keys[1].fmr_offset);
>  			error = xfs_fsmap_owner_to_rmap(&info->high, &keys[1]);
> -- 
> 2.39.2
> 
> 

Re: [PATCH 2/2] xfs: Fix incorrect parameter calculation in rt fsmap

[Darrick J. Wong]

On Mon, Aug 26, 2024 at 11:10:05AM +0800, Zizhi Wo wrote:
> I noticed a bug related to xfs realtime device fsmap:
> [root@fedora ~]# xfs_io -c 'fsmap -vvvv -r' /mnt
>  EXT: DEV    BLOCK-RANGE         OWNER            FILE-OFFSET      AG AG-OFFSET          TOTAL
>    0: 253:48 [0..7]:             unknown                                                     8
>    1: 253:48 [8..1048575]:       free space                                            1048568
>    2: 253:48 [1048576..1050623]: unknown                                                  2048
>    3: 253:48 [1050624..2097151]: free space                                            1046528
> 
> Bug:
> [root@fedora ~]# xfs_io -c 'fsmap -vvvv -r 1050621 1050621' /mnt
>  EXT: DEV    BLOCK-RANGE         OWNER            FILE-OFFSET      AG AG-OFFSET        TOTAL
>    0: 253:48 [1050621..1050623]: unknown                                                   3
>    1: 253:48 [1050624..1050631]: free space                                                8
> Normally, we should not get any results, but we do get two queries.
> 
> The root cause of this problem lies in the calculation of "end_rtb" in
> xfs_getfsmap_rtdev_rtbitmap(), which uses XFS_BB_TO_FSB method (round up).
> However, in the subsequent call to xfs_rtalloc_query_range(), "high_rec"
> calculated based on "end_rtb" has a semantic meaning of being reachable
> within the loop. The first round of the loop in xfs_rtalloc_query_range()
> doesn't find any free extents. But after incrementing "rtstart" by 1, start
> still does not exceed "high_key", and the second round of the loop entered.
> It finds free extent and obtains the first unknown extent by subtracting it
> from "info->next_daddr". Even though we can accurately handle it through
> "info->end_daddr", two incorrect extents has already been returned before
> the last query. The main call stack is as follows:
> 
> xfs_getfsmap_rtdev_rtbitmap
>   // rounded up
>   end_rtb = XFS_BB_TO_FSB(..., keys[1].fmr_physical)
>   ahigh.ar_startext = xfs_rtb_to_rtxup(mp, end_rtb)
>   xfs_rtalloc_query_range
>     // high_key is calculated based on end_rtb
>     high_key = min(high_rec->ar_startext, ...)
>     while (rtstart <= high_key)
>       // First loop, doesn't find free extent
>       xfs_rtcheck_range
>       rtstart = rtend + 1
>       // Second loop, the free extent outside the query interval is found
>       xfs_getfsmap_rtdev_rtbitmap_helper
>         // unknown and free were printed out together in the second round
>         xfs_getfsmap_helper
> 
> The issue is resolved by adjusting the relevant calculations. Both the loop
> exit condition in the xfs_rtalloc_query_range() and the length calculation
> condition (high_key - start + 1) in the xfs_rtfind_forw() reflect the open
> interval semantics of "high_key". Therefore, when calculating "end_rtb",
> XFS_BB_TO_FSBT is used. In addition, in order to satisfy the close interval
> semantics, "key[1].fmr_physical" needs to be decremented by 1. For the
> non-eofs case, there is no need to worry about over-counting because we can
> accurately count the block number through "info->end_daddr".
> 
> After applying this patch, the above problem have been solved:
> [root@fedora ~]# xfs_io -c 'fsmap -vvvv -r 1050621 1050621' /mnt
> [root@fedora ~]#
> 
> Fixes: 4c934c7dd60c ("xfs: report realtime space information via the rtbitmap")
> Signed-off-by: Zizhi Wo <wozizhi@huawei.com>
> ---
>  fs/xfs/libxfs/xfs_rtbitmap.c |  4 +---
>  fs/xfs/xfs_fsmap.c           | 20 +++++++++++++++++---
>  2 files changed, 18 insertions(+), 6 deletions(-)
> 
> diff --git a/fs/xfs/libxfs/xfs_rtbitmap.c b/fs/xfs/libxfs/xfs_rtbitmap.c
> index 386b672c5058..7af4e7afda7d 100644
> --- a/fs/xfs/libxfs/xfs_rtbitmap.c
> +++ b/fs/xfs/libxfs/xfs_rtbitmap.c
> @@ -1034,8 +1034,7 @@ xfs_rtalloc_query_range(
>  
>  	if (low_rec->ar_startext > high_rec->ar_startext)
>  		return -EINVAL;
> -	if (low_rec->ar_startext >= mp->m_sb.sb_rextents ||
> -	    low_rec->ar_startext == high_rec->ar_startext)
> +	if (low_rec->ar_startext >= mp->m_sb.sb_rextents)
>  		return 0;
>  
>  	high_key = min(high_rec->ar_startext, mp->m_sb.sb_rextents - 1);
> @@ -1057,7 +1056,6 @@ xfs_rtalloc_query_range(
>  		if (is_free) {
>  			rec.ar_startext = rtstart;
>  			rec.ar_extcount = rtend - rtstart + 1;
> -
>  			error = fn(mp, tp, &rec, priv);
>  			if (error)
>  				break;

Not sure why these changes are necessary?

> diff --git a/fs/xfs/xfs_fsmap.c b/fs/xfs/xfs_fsmap.c
> index 8a2dfe96dae7..42c4b94b0493 100644
> --- a/fs/xfs/xfs_fsmap.c
> +++ b/fs/xfs/xfs_fsmap.c
> @@ -515,11 +515,20 @@ xfs_getfsmap_rtdev_rtbitmap(
>  	int				error;
>  
>  	eofs = XFS_FSB_TO_BB(mp, xfs_rtx_to_rtb(mp, mp->m_sb.sb_rextents));
> -	if (keys[0].fmr_physical >= eofs)
> +	if (keys[0].fmr_physical >= eofs ||
> +		keys[0].fmr_physical == keys[1].fmr_physical)
>  		return 0;
>  	start_rtb = XFS_BB_TO_FSBT(mp,
>  				keys[0].fmr_physical + keys[0].fmr_length);
> -	end_rtb = XFS_BB_TO_FSB(mp, min(eofs - 1, keys[1].fmr_physical));
> +	/*
> +	 * The passed keys[1] is an unreachable value, while "end_rtb" is used
> +	 * to calculate "ahigh.ar_startext", serving as an input parameter for
> +	 * xfs_rtalloc_query_range(), which is a value that can be reached.
> +	 * Therefore, it is necessary to use "keys[1].fmr_physical - 1" here.
> +	 * And because of the semantics of "end_rtb", it needs to be
> +	 * supplemented by 1 in the last calculation.
> +	 */
> +	end_rtb = XFS_BB_TO_FSBT(mp, min(eofs - 1, keys[1].fmr_physical - 1));

keys[1].fmr_physical should already be the ahigh.ar_startext value that
the user wants.  No need to subtract 1 here.

>  	info->missing_owner = XFS_FMR_OWN_UNKNOWN;
>  
> @@ -549,9 +558,14 @@ xfs_getfsmap_rtdev_rtbitmap(
>  	/*
>  	 * Report any gaps at the end of the rtbitmap by simulating a null
>  	 * rmap starting at the block after the end of the query range.
> +	 * For the boundary case of eofs, we need to increment the count
> +	 * by 1 to prevent omission in block statistics.
> +	 * For the boundary case of non-eofs, even if incrementing by 1
> +	 * may lead to over-counting, it doesn't matter because it is
> +	 * handled by "info->end_daddr" in this situation, not "ahigh".
>  	 */
>  	info->last = true;
> -	ahigh.ar_startext = min(mp->m_sb.sb_rextents, ahigh.ar_startext);
> +	ahigh.ar_startext = min(mp->m_sb.sb_rextents, ahigh.ar_startext + 1);

Ah, that.  I think hch and I accidentally fixed this in
https://lore.kernel.org/linux-xfs/173084397143.1871025.11595051287386271783.stgit@frogsfrogsfrogs/

--D

>  
>  	error = xfs_getfsmap_rtdev_rtbitmap_helper(mp, tp, &ahigh, info);
>  	if (error)
> -- 
> 2.39.2
> 
> 

Re: [PATCH 0/2] Some boundary error bugfix related to XFS fsmap.

[Darrick J. Wong]

On Thu, Nov 07, 2024 at 05:21:55PM +0800, Zizhi Wo wrote:
> 
> 
> 在 2024/10/9 21:01, Zizhi Wo 写道:
> > Hi!
> > 
> > Here are two patches that address fsmap statistics errors. I sent out
> > this version in August, and I hope someone can take some time to review
> > them. So friendly ping. Thanks in advance!
> 
> friendly ping again（￣。。￣）

Oops, sorry.  Will go reply now.

--D

> > 
> > 
> > 在 2024/9/3 3:08, Darrick J. Wong 写道:
> > > On Thu, Aug 29, 2024 at 07:24:55PM +0800, Zizhi Wo wrote:
> > > > friendly ping
> > > 
> > > Sorry, I'm not going to get to this until late September.
> > > 
> > > --D
> > > 
> > > > 在 2024/8/26 11:10, Zizhi Wo 写道:
> > > > > Prior to this, I had already sent out a patchset related to xfs fsmap
> > > > > bugfix, which mainly introduced "info->end_daddr" to fix
> > > > > omitted extents[1]
> > > > > and Darrick had already sent out a patchbomb for merging
> > > > > into stable[2],
> > > > > which included my previous patches.
> > > > > 
> > > > > However, I recently discovered two new fsmap problems...What
> > > > > follows is a
> > > > > brief description of them:
> > > > > 
> > > > > Patch 1: In this scenario, fsmap lost one block count. The
> > > > > root cause is
> > > > > that during the calculation of highkey, the calculation of
> > > > > start_block is
> > > > > missing an increment by one, which leads to the last query missing one
> > > > > This problem is resolved by adding a sentinel node.
> > > > > 
> > > > > Patch 2: In this scenario, the fsmap query for realtime
> > > > > deivce may display
> > > > > extra intervals. This is due to an extra increase in
> > > > > "end_rtb". The issue
> > > > > is resolved by adjusting the relevant calculations. And this
> > > > > patch depends
> > > > > on the previous patch that introduced "info->end_daddr".
> > > > > 
> > > > > [1] https://lore.kernel.org/all/20240819005320.304211-1-wozizhi@huawei.com/
> > > > > [2] https://lore.kernel.org/all/172437083728.56860.10056307551249098606.stgit@frogsfrogsfrogs/
> > > > > 
> > > > > Zizhi Wo (2):
> > > > >     xfs: Fix missing block calculations in xfs datadev fsmap
> > > > >     xfs: Fix incorrect parameter calculation in rt fsmap
> > > > > 
> > > > >    fs/xfs/libxfs/xfs_rtbitmap.c |  4 +---
> > > > >    fs/xfs/xfs_fsmap.c           | 39
> > > > > +++++++++++++++++++++++++++++++-----
> > > > >    2 files changed, 35 insertions(+), 8 deletions(-)
> > > > > 
> > > > 
> > > 
> > 
> > 
> 

Re: [PATCH 1/2] xfs: Fix missing block calculations in xfs datadev fsmap

[Zizhi Wo]

在 2024/11/8 7:43, Darrick J. Wong 写道:
> On Mon, Aug 26, 2024 at 11:10:04AM +0800, Zizhi Wo wrote:
>> In xfs datadev fsmap query, I noticed a missing block calculation problem:
>> [root@fedora ~]# xfs_db -r -c "sb 0" -c "p" /dev/vdb
>> magicnum = 0x58465342
>> blocksize = 4096
>> dblocks = 5242880
>> ......
>> [root@fedora ~]# xfs_io -c 'fsmap -vvvv' /mnt
>> ...
>> 30: 253:16 [31457384..41943031]: free space            3  (104..10485751)    10485648
>>
>> (41943031 + 1) / 8 = 5242879 != 5242880
>> We missed one block in our fsmap calculation!
> 
> Eek.
> 
>> The root cause of the problem lies in __xfs_getfsmap_datadev(), where the
>> calculation of "end_fsb" requires a classification discussion. If "end_fsb"
>> is calculated based on "eofs", we need to add an extra sentinel node for
>> subsequent length calculations. Otherwise, one block will be missed. If
>> "end_fsb" is calculated based on "keys[1]", then there is no need to add an
>> extra node. Because "keys[1]" itself is unreachable, it cancels out one of
>> the additions. The diagram below illustrates this:
>>
>> |0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|-----eofs
>> |---------------|---------------------|
>> a       n       b         n+1         c
>>
>> Assume that eofs is 16, the start address of the previous query is block n,
>> sector 0, and the length is 1, so the "info->next" is at point b, sector 8.
>> In the last query, suppose the "rm_startblock" calculated based on
>> "eofs - 1" is the last block n+1 at point b. All we get is the starting
>> address of the block, not the end. Therefore, an additional sentinel node
>> needs to be added to move it to point c. After that, subtracting one from
>> the other will yield the remaining 1.
>>
>> Although we can now calculate the exact last query using "info->end_daddr",
>> we will still get an incorrect value if the device at this point is not the
>> boundary device specified by "keys[1]", as "end_daddr" is still the initial
>> value. Therefore, the eofs situation here needs to be corrected. The issue
>> is resolved by adding a sentinel node.
> 
> Why don't we set end_daddr unconditionally, then?
> 
> Hmm, looking at the end_daddr usage in fsmap.c, I think it's wrong.  If
> end_daddr is set at all, it's set either to the last sector for which
> the user wants a mapping; or it's set to the last sector for the device.
> But then look at how we use it:
> 
> 	if (info->last...)
> 		frec->start_daddr = info->end_daddr;
> 
> 	...
> 
> 	/* "report the gap..."
> 	if (frec->start_daddr > info->next_daddr) {
> 		fmr.fmr_length = frec->start_daddr - info->next_daddr;
> 	}
> 
> This is wrong -- we're using start_daddr to compute the distance from
> the last mapping that we output up to the end of the range that we want.
> The "end of the range" is modeled with a phony rmap record that starts
> at the first fsblock after that range.
> 

In the current code, we set "rec_daddr = end_daddr" only when
(info->last && info->end_daddr != NULL), which should ensure that this
is the last query? Because end_daddr is set to the last device, and
info->last is set to the last query. Therefore, assigning it to
start_daddr should not cause issues in the next query?

Did I misunderstand something? Or is it because the latest code
constantly updates end_daddr, which is why this issue arises?

> IOWs, that assignment should have been
> frec->start_daddr = info->end_daddr + 1.
> 
> Granted in August the codebase was less clear about the difference
> between rec_daddr and rmap->rm_startblock.  For 6.13, hch cleaned all
> that up -- rec_daddr is now called start_daddr and the fsmap code passes
> rmap records with space numbers in units of daddrs via a new struct
> xfs_fsmap_rec.  Unfortunately, that's all buried in the giant pile of
> pull requests I sent a couple of days ago which hasn't shown up on
> for-next yet.
> 
> https://lore.kernel.org/linux-xfs/173084396955.1871025.18156568347365549855.stgit@frogsfrogsfrogs/
> 
> So I think I know how to fix this against the 6.13 codebase, but I'm
> going to take a slightly different approach than yours...
> 
>> Fixes: e89c041338ed ("xfs: implement the GETFSMAP ioctl")
>> Signed-off-by: Zizhi Wo <wozizhi@huawei.com>
>> ---
>>   fs/xfs/xfs_fsmap.c | 19 +++++++++++++++++--
>>   1 file changed, 17 insertions(+), 2 deletions(-)
>>
>> diff --git a/fs/xfs/xfs_fsmap.c b/fs/xfs/xfs_fsmap.c
>> index 85dbb46452ca..8a2dfe96dae7 100644
>> --- a/fs/xfs/xfs_fsmap.c
>> +++ b/fs/xfs/xfs_fsmap.c
>> @@ -596,12 +596,27 @@ __xfs_getfsmap_datadev(
>>   	xfs_agnumber_t			end_ag;
>>   	uint64_t			eofs;
>>   	int				error = 0;
>> +	int				sentinel = 0;
>>   
>>   	eofs = XFS_FSB_TO_BB(mp, mp->m_sb.sb_dblocks);
>>   	if (keys[0].fmr_physical >= eofs)
>>   		return 0;
>>   	start_fsb = XFS_DADDR_TO_FSB(mp, keys[0].fmr_physical);
>> -	end_fsb = XFS_DADDR_TO_FSB(mp, min(eofs - 1, keys[1].fmr_physical));
>> +	/*
>> +	 * For the case of eofs, we need to add a sentinel node;
>> +	 * otherwise, one block will be missed when calculating the length
>> +	 * in the last query.
>> +	 * For the case of key[1], there is no need to add a sentinel node
>> +	 * because it already represents a value that cannot be reached.
>> +	 * For the case where key[1] after shifting is within the same
>> +	 * block as the starting address, it is resolved using end_daddr.
>> +	 */
>> +	if (keys[1].fmr_physical > eofs - 1) {
>> +		sentinel = 1;
>> +		end_fsb = XFS_DADDR_TO_FSB(mp, eofs - 1);
>> +	} else {
>> +		end_fsb = XFS_DADDR_TO_FSB(mp, keys[1].fmr_physical);
>> +	}
> 
> ...because running against djwong-wtf, I actually see the same symptoms
> for the realtime device.  So I think a better solution is to change
> xfs_getfsmap to set end_daddr always, and then fix the off by one error.
> 

Yes, my second patch looks at this rt problem...
Thank you for your reply

Thanks,
Zizhi Wo


> I also don't really like "sentinel" values because they're not
> intuitive.
> 
> I will also go update xfs/273 to check that there are no gaps in the
> mappings returned, and that they go to where the filesystem thinks is
> the end of the device.  Thanks for reporting this, sorry I was too busy
> trying to get metadir/rtgroups done to look at this until now. :(
> 
> --D
> 



>>   
>>   	/*
>>   	 * Convert the fsmap low/high keys to AG based keys.  Initialize
>> @@ -649,7 +664,7 @@ __xfs_getfsmap_datadev(
>>   		info->pag = pag;
>>   		if (pag->pag_agno == end_ag) {
>>   			info->high.rm_startblock = XFS_FSB_TO_AGBNO(mp,
>> -					end_fsb);
>> +					end_fsb) + sentinel;
>>   			info->high.rm_offset = XFS_BB_TO_FSBT(mp,
>>   					keys[1].fmr_offset);
>>   			error = xfs_fsmap_owner_to_rmap(&info->high, &keys[1]);
>> -- 
>> 2.39.2
>>
>>

Re: [PATCH 1/2] xfs: Fix missing block calculations in xfs datadev fsmap

[Darrick J. Wong]

On Fri, Nov 08, 2024 at 10:29:08AM +0800, Zizhi Wo wrote:
> 
> 
> 在 2024/11/8 7:43, Darrick J. Wong 写道:
> > On Mon, Aug 26, 2024 at 11:10:04AM +0800, Zizhi Wo wrote:
> > > In xfs datadev fsmap query, I noticed a missing block calculation problem:
> > > [root@fedora ~]# xfs_db -r -c "sb 0" -c "p" /dev/vdb
> > > magicnum = 0x58465342
> > > blocksize = 4096
> > > dblocks = 5242880
> > > ......
> > > [root@fedora ~]# xfs_io -c 'fsmap -vvvv' /mnt
> > > ...
> > > 30: 253:16 [31457384..41943031]: free space            3  (104..10485751)    10485648
> > > 
> > > (41943031 + 1) / 8 = 5242879 != 5242880
> > > We missed one block in our fsmap calculation!
> > 
> > Eek.
> > 
> > > The root cause of the problem lies in __xfs_getfsmap_datadev(), where the
> > > calculation of "end_fsb" requires a classification discussion. If "end_fsb"
> > > is calculated based on "eofs", we need to add an extra sentinel node for
> > > subsequent length calculations. Otherwise, one block will be missed. If
> > > "end_fsb" is calculated based on "keys[1]", then there is no need to add an
> > > extra node. Because "keys[1]" itself is unreachable, it cancels out one of
> > > the additions. The diagram below illustrates this:
> > > 
> > > |0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|-----eofs
> > > |---------------|---------------------|
> > > a       n       b         n+1         c
> > > 
> > > Assume that eofs is 16, the start address of the previous query is block n,
> > > sector 0, and the length is 1, so the "info->next" is at point b, sector 8.
> > > In the last query, suppose the "rm_startblock" calculated based on
> > > "eofs - 1" is the last block n+1 at point b. All we get is the starting
> > > address of the block, not the end. Therefore, an additional sentinel node
> > > needs to be added to move it to point c. After that, subtracting one from
> > > the other will yield the remaining 1.
> > > 
> > > Although we can now calculate the exact last query using "info->end_daddr",
> > > we will still get an incorrect value if the device at this point is not the
> > > boundary device specified by "keys[1]", as "end_daddr" is still the initial
> > > value. Therefore, the eofs situation here needs to be corrected. The issue
> > > is resolved by adding a sentinel node.
> > 
> > Why don't we set end_daddr unconditionally, then?
> > 
> > Hmm, looking at the end_daddr usage in fsmap.c, I think it's wrong.  If
> > end_daddr is set at all, it's set either to the last sector for which
> > the user wants a mapping; or it's set to the last sector for the device.
> > But then look at how we use it:
> > 
> > 	if (info->last...)
> > 		frec->start_daddr = info->end_daddr;
> > 
> > 	...
> > 
> > 	/* "report the gap..."
> > 	if (frec->start_daddr > info->next_daddr) {
> > 		fmr.fmr_length = frec->start_daddr - info->next_daddr;
> > 	}
> > 
> > This is wrong -- we're using start_daddr to compute the distance from
> > the last mapping that we output up to the end of the range that we want.
> > The "end of the range" is modeled with a phony rmap record that starts
> > at the first fsblock after that range.
> > 
> 
> In the current code, we set "rec_daddr = end_daddr" only when
> (info->last && info->end_daddr != NULL), which should ensure that this
> is the last query?

Right.

> Because end_daddr is set to the last device, and
> info->last is set to the last query. Therefore, assigning it to
> start_daddr should not cause issues in the next query?

Right, the code currently sets end_daddr only for the last device, so
there won't be any issues with the next query.

That said, we reset the xfs_getfsmap_info state between each device, so
it's safe to set end_daddr for every device, not just the last time
through that loop.

> Did I misunderstand something? Or is it because the latest code
> constantly updates end_daddr, which is why this issue arises?

The 6.13 metadir/rtgroups patches didn't change when end_daddr gets set,
but my fixpatch *does* make it set end_daddr for all devices.  Will send
a patch + fstests update shortly to demonstrate. :)

> > IOWs, that assignment should have been
> > frec->start_daddr = info->end_daddr + 1.
> > 
> > Granted in August the codebase was less clear about the difference
> > between rec_daddr and rmap->rm_startblock.  For 6.13, hch cleaned all
> > that up -- rec_daddr is now called start_daddr and the fsmap code passes
> > rmap records with space numbers in units of daddrs via a new struct
> > xfs_fsmap_rec.  Unfortunately, that's all buried in the giant pile of
> > pull requests I sent a couple of days ago which hasn't shown up on
> > for-next yet.
> > 
> > https://lore.kernel.org/linux-xfs/173084396955.1871025.18156568347365549855.stgit@frogsfrogsfrogs/
> > 
> > So I think I know how to fix this against the 6.13 codebase, but I'm
> > going to take a slightly different approach than yours...
> > 
> > > Fixes: e89c041338ed ("xfs: implement the GETFSMAP ioctl")
> > > Signed-off-by: Zizhi Wo <wozizhi@huawei.com>
> > > ---
> > >   fs/xfs/xfs_fsmap.c | 19 +++++++++++++++++--
> > >   1 file changed, 17 insertions(+), 2 deletions(-)
> > > 
> > > diff --git a/fs/xfs/xfs_fsmap.c b/fs/xfs/xfs_fsmap.c
> > > index 85dbb46452ca..8a2dfe96dae7 100644
> > > --- a/fs/xfs/xfs_fsmap.c
> > > +++ b/fs/xfs/xfs_fsmap.c
> > > @@ -596,12 +596,27 @@ __xfs_getfsmap_datadev(
> > >   	xfs_agnumber_t			end_ag;
> > >   	uint64_t			eofs;
> > >   	int				error = 0;
> > > +	int				sentinel = 0;
> > >   	eofs = XFS_FSB_TO_BB(mp, mp->m_sb.sb_dblocks);
> > >   	if (keys[0].fmr_physical >= eofs)
> > >   		return 0;
> > >   	start_fsb = XFS_DADDR_TO_FSB(mp, keys[0].fmr_physical);
> > > -	end_fsb = XFS_DADDR_TO_FSB(mp, min(eofs - 1, keys[1].fmr_physical));
> > > +	/*
> > > +	 * For the case of eofs, we need to add a sentinel node;
> > > +	 * otherwise, one block will be missed when calculating the length
> > > +	 * in the last query.
> > > +	 * For the case of key[1], there is no need to add a sentinel node
> > > +	 * because it already represents a value that cannot be reached.
> > > +	 * For the case where key[1] after shifting is within the same
> > > +	 * block as the starting address, it is resolved using end_daddr.
> > > +	 */
> > > +	if (keys[1].fmr_physical > eofs - 1) {
> > > +		sentinel = 1;
> > > +		end_fsb = XFS_DADDR_TO_FSB(mp, eofs - 1);
> > > +	} else {
> > > +		end_fsb = XFS_DADDR_TO_FSB(mp, keys[1].fmr_physical);
> > > +	}
> > 
> > ...because running against djwong-wtf, I actually see the same symptoms
> > for the realtime device.  So I think a better solution is to change
> > xfs_getfsmap to set end_daddr always, and then fix the off by one error.
> > 
> 
> Yes, my second patch looks at this rt problem...
> Thank you for your reply

<nod>

--D

> Thanks,
> Zizhi Wo
> 
> 
> > I also don't really like "sentinel" values because they're not
> > intuitive.
> > 
> > I will also go update xfs/273 to check that there are no gaps in the
> > mappings returned, and that they go to where the filesystem thinks is
> > the end of the device.  Thanks for reporting this, sorry I was too busy
> > trying to get metadir/rtgroups done to look at this until now. :(
> > 
> > --D
> > 
> 
> 
> 
> > >   	/*
> > >   	 * Convert the fsmap low/high keys to AG based keys.  Initialize
> > > @@ -649,7 +664,7 @@ __xfs_getfsmap_datadev(
> > >   		info->pag = pag;
> > >   		if (pag->pag_agno == end_ag) {
> > >   			info->high.rm_startblock = XFS_FSB_TO_AGBNO(mp,
> > > -					end_fsb);
> > > +					end_fsb) + sentinel;
> > >   			info->high.rm_offset = XFS_BB_TO_FSBT(mp,
> > >   					keys[1].fmr_offset);
> > >   			error = xfs_fsmap_owner_to_rmap(&info->high, &keys[1]);
> > > -- 
> > > 2.39.2
> > > 
> > > 
> 

Re: [PATCH 1/2] xfs: Fix missing block calculations in xfs datadev fsmap

[Zizhi Wo]

在 2024/11/9 1:30, Darrick J. Wong 写道:
> On Fri, Nov 08, 2024 at 10:29:08AM +0800, Zizhi Wo wrote:
>>
>>
>> 在 2024/11/8 7:43, Darrick J. Wong 写道:
>>> On Mon, Aug 26, 2024 at 11:10:04AM +0800, Zizhi Wo wrote:
>>>> In xfs datadev fsmap query, I noticed a missing block calculation problem:
>>>> [root@fedora ~]# xfs_db -r -c "sb 0" -c "p" /dev/vdb
>>>> magicnum = 0x58465342
>>>> blocksize = 4096
>>>> dblocks = 5242880
>>>> ......
>>>> [root@fedora ~]# xfs_io -c 'fsmap -vvvv' /mnt
>>>> ...
>>>> 30: 253:16 [31457384..41943031]: free space            3  (104..10485751)    10485648
>>>>
>>>> (41943031 + 1) / 8 = 5242879 != 5242880
>>>> We missed one block in our fsmap calculation!
>>>
>>> Eek.
>>>
>>>> The root cause of the problem lies in __xfs_getfsmap_datadev(), where the
>>>> calculation of "end_fsb" requires a classification discussion. If "end_fsb"
>>>> is calculated based on "eofs", we need to add an extra sentinel node for
>>>> subsequent length calculations. Otherwise, one block will be missed. If
>>>> "end_fsb" is calculated based on "keys[1]", then there is no need to add an
>>>> extra node. Because "keys[1]" itself is unreachable, it cancels out one of
>>>> the additions. The diagram below illustrates this:
>>>>
>>>> |0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|-----eofs
>>>> |---------------|---------------------|
>>>> a       n       b         n+1         c
>>>>
>>>> Assume that eofs is 16, the start address of the previous query is block n,
>>>> sector 0, and the length is 1, so the "info->next" is at point b, sector 8.
>>>> In the last query, suppose the "rm_startblock" calculated based on
>>>> "eofs - 1" is the last block n+1 at point b. All we get is the starting
>>>> address of the block, not the end. Therefore, an additional sentinel node
>>>> needs to be added to move it to point c. After that, subtracting one from
>>>> the other will yield the remaining 1.
>>>>
>>>> Although we can now calculate the exact last query using "info->end_daddr",
>>>> we will still get an incorrect value if the device at this point is not the
>>>> boundary device specified by "keys[1]", as "end_daddr" is still the initial
>>>> value. Therefore, the eofs situation here needs to be corrected. The issue
>>>> is resolved by adding a sentinel node.
>>>
>>> Why don't we set end_daddr unconditionally, then?
>>>
>>> Hmm, looking at the end_daddr usage in fsmap.c, I think it's wrong.  If
>>> end_daddr is set at all, it's set either to the last sector for which
>>> the user wants a mapping; or it's set to the last sector for the device.
>>> But then look at how we use it:
>>>
>>> 	if (info->last...)
>>> 		frec->start_daddr = info->end_daddr;
>>>
>>> 	...
>>>
>>> 	/* "report the gap..."
>>> 	if (frec->start_daddr > info->next_daddr) {
>>> 		fmr.fmr_length = frec->start_daddr - info->next_daddr;
>>> 	}
>>>
>>> This is wrong -- we're using start_daddr to compute the distance from
>>> the last mapping that we output up to the end of the range that we want.
>>> The "end of the range" is modeled with a phony rmap record that starts
>>> at the first fsblock after that range.
>>>
>>
>> In the current code, we set "rec_daddr = end_daddr" only when
>> (info->last && info->end_daddr != NULL), which should ensure that this
>> is the last query?
> 
> Right.
> 
>> Because end_daddr is set to the last device, and
>> info->last is set to the last query. Therefore, assigning it to
>> start_daddr should not cause issues in the next query?
> 
> Right, the code currently sets end_daddr only for the last device, so
> there won't be any issues with the next query.
> 
> That said, we reset the xfs_getfsmap_info state between each device, so
> it's safe to set end_daddr for every device, not just the last time
> through that loop.
> 
>> Did I misunderstand something? Or is it because the latest code
>> constantly updates end_daddr, which is why this issue arises?
> 
> The 6.13 metadir/rtgroups patches didn't change when end_daddr gets set,
> but my fixpatch *does* make it set end_daddr for all devices.  Will send
> a patch + fstests update shortly to demonstrate. :)

OK, I got it. Thank you for your reply.

Thanks,
Zizhi Wo

> 
>>> IOWs, that assignment should have been
>>> frec->start_daddr = info->end_daddr + 1.
>>>
>>> Granted in August the codebase was less clear about the difference
>>> between rec_daddr and rmap->rm_startblock.  For 6.13, hch cleaned all
>>> that up -- rec_daddr is now called start_daddr and the fsmap code passes
>>> rmap records with space numbers in units of daddrs via a new struct
>>> xfs_fsmap_rec.  Unfortunately, that's all buried in the giant pile of
>>> pull requests I sent a couple of days ago which hasn't shown up on
>>> for-next yet.
>>>
>>> https://lore.kernel.org/linux-xfs/173084396955.1871025.18156568347365549855.stgit@frogsfrogsfrogs/
>>>
>>> So I think I know how to fix this against the 6.13 codebase, but I'm
>>> going to take a slightly different approach than yours...
>>>
>>>> Fixes: e89c041338ed ("xfs: implement the GETFSMAP ioctl")
>>>> Signed-off-by: Zizhi Wo <wozizhi@huawei.com>
>>>> ---
>>>>    fs/xfs/xfs_fsmap.c | 19 +++++++++++++++++--
>>>>    1 file changed, 17 insertions(+), 2 deletions(-)
>>>>
>>>> diff --git a/fs/xfs/xfs_fsmap.c b/fs/xfs/xfs_fsmap.c
>>>> index 85dbb46452ca..8a2dfe96dae7 100644
>>>> --- a/fs/xfs/xfs_fsmap.c
>>>> +++ b/fs/xfs/xfs_fsmap.c
>>>> @@ -596,12 +596,27 @@ __xfs_getfsmap_datadev(
>>>>    	xfs_agnumber_t			end_ag;
>>>>    	uint64_t			eofs;
>>>>    	int				error = 0;
>>>> +	int				sentinel = 0;
>>>>    	eofs = XFS_FSB_TO_BB(mp, mp->m_sb.sb_dblocks);
>>>>    	if (keys[0].fmr_physical >= eofs)
>>>>    		return 0;
>>>>    	start_fsb = XFS_DADDR_TO_FSB(mp, keys[0].fmr_physical);
>>>> -	end_fsb = XFS_DADDR_TO_FSB(mp, min(eofs - 1, keys[1].fmr_physical));
>>>> +	/*
>>>> +	 * For the case of eofs, we need to add a sentinel node;
>>>> +	 * otherwise, one block will be missed when calculating the length
>>>> +	 * in the last query.
>>>> +	 * For the case of key[1], there is no need to add a sentinel node
>>>> +	 * because it already represents a value that cannot be reached.
>>>> +	 * For the case where key[1] after shifting is within the same
>>>> +	 * block as the starting address, it is resolved using end_daddr.
>>>> +	 */
>>>> +	if (keys[1].fmr_physical > eofs - 1) {
>>>> +		sentinel = 1;
>>>> +		end_fsb = XFS_DADDR_TO_FSB(mp, eofs - 1);
>>>> +	} else {
>>>> +		end_fsb = XFS_DADDR_TO_FSB(mp, keys[1].fmr_physical);
>>>> +	}
>>>
>>> ...because running against djwong-wtf, I actually see the same symptoms
>>> for the realtime device.  So I think a better solution is to change
>>> xfs_getfsmap to set end_daddr always, and then fix the off by one error.
>>>
>>
>> Yes, my second patch looks at this rt problem...
>> Thank you for your reply
> 
> <nod>
> 
> --D
> 
>> Thanks,
>> Zizhi Wo
>>
>>
>>> I also don't really like "sentinel" values because they're not
>>> intuitive.
>>>
>>> I will also go update xfs/273 to check that there are no gaps in the
>>> mappings returned, and that they go to where the filesystem thinks is
>>> the end of the device.  Thanks for reporting this, sorry I was too busy
>>> trying to get metadir/rtgroups done to look at this until now. :(
>>>
>>> --D
>>>
>>
>>
>>
>>>>    	/*
>>>>    	 * Convert the fsmap low/high keys to AG based keys.  Initialize
>>>> @@ -649,7 +664,7 @@ __xfs_getfsmap_datadev(
>>>>    		info->pag = pag;
>>>>    		if (pag->pag_agno == end_ag) {
>>>>    			info->high.rm_startblock = XFS_FSB_TO_AGBNO(mp,
>>>> -					end_fsb);
>>>> +					end_fsb) + sentinel;
>>>>    			info->high.rm_offset = XFS_BB_TO_FSBT(mp,
>>>>    					keys[1].fmr_offset);
>>>>    			error = xfs_fsmap_owner_to_rmap(&info->high, &keys[1]);
>>>> -- 
>>>> 2.39.2
>>>>
>>>>
>>
>