Re: [PATCH] xfs: Verify DA node btree hash order

[Charalampos Mitrodimas <charmitro@posteo.net>]

"Darrick J. Wong" <djwong@kernel.org> writes:

> On Wed, Apr 30, 2025 at 11:23:57AM +0200, Carlos Maiolino wrote:
>> On Sat, Apr 12, 2025 at 08:03:57PM +0000, Charalampos Mitrodimas wrote:
>> > The xfs_da3_node_verify() function checks the integrity of directory
>> > and attribute B-tree node blocks. However, it was missing a check to
>> > ensure that the hash values of the btree entries within the node are
>> > strictly increasing, as required by the B-tree structure.
>> > 
>> > Add a loop to iterate through the btree entries and verify that each
>> > entry's hash value is greater than the previous one. If an
>> > out-of-order hash value is detected, return failure to indicate
>> > corruption.
>> > 
>> > This addresses the "XXX: hash order check?" comment and improves
>> > corruption detection for DA node blocks.
>> > 
>> > Signed-off-by: Charalampos Mitrodimas <charmitro@posteo.net>
>> > ---
>> >  fs/xfs/libxfs/xfs_da_btree.c | 11 ++++++++++-
>> >  1 file changed, 10 insertions(+), 1 deletion(-)
>> > 
>> > diff --git a/fs/xfs/libxfs/xfs_da_btree.c b/fs/xfs/libxfs/xfs_da_btree.c
>> > index 17d9e6154f1978ce5a5cb82176eea4d6b9cd768d..6c748911e54619c3ceae9b81f55cf61da6735f01 100644
>> > --- a/fs/xfs/libxfs/xfs_da_btree.c
>> > +++ b/fs/xfs/libxfs/xfs_da_btree.c
>> > @@ -247,7 +247,16 @@ xfs_da3_node_verify(
>> >  	    ichdr.count > mp->m_attr_geo->node_ents)
>> >  		return __this_address;
>> > 
>> > -	/* XXX: hash order check? */
>> > +	/* Check hash order */
>> > +	uint32_t prev_hash = be32_to_cpu(ichdr.btree[0].hashval);
>> > +
>> > +	for (int i = 1; i < ichdr.count; i++) {
>> > +		uint32_t curr_hash = be32_to_cpu(ichdr.btree[i].hashval);
>> > +
>> > +		if (curr_hash <= prev_hash)
>> > +			return __this_address;
>> > +		prev_hash = curr_hash;
>> > +	}
>> 
>> Hmmm. Do you have any numbers related to the performance impact of this patch?
>> 
>> IIRC for very populated directories we can end up having many entries here. It's
>> not uncommon to have filesystems with millions of entries in a single directory.
>> Now we'll be looping over all those entries here during verification, which could
>> scale to many interactions on this loop.
>> I'm not sure if I'm right here, but this seems to add a big performance penalty
>> for directory writes, so I'm curious about the performance implications of this
>> patch.
>
> It's only a single dabtree block, which will likely be warm in cache
> due to the crc32c validation.

I ran a 60-second fio test that creates directories. Performance was not
significantly changed:

Before: read: IOPS=4809k, BW=18.3GiB/s (19.7GB/s)(1101GiB/60001msec)
After: read: IOPS=5121k, BW=19.5GiB/s (20.0GB/s)(1172GiB/60000msec)

But I'd welcome input on more targeted benchmarks if these aren't
representative.

>
> But if memory serves, one can create a large enough dir (or xattr)
> structure such that a dabtree node gets written out with a bunch of
> entries with the same hashval.  That was the subject of the correction
> made in commit b7b81f336ac02f ("xfs_repair: fix incorrect dabtree
> hashval comparison") so I've been wondering if this passes the xfs/599
> test?  Or am I just being dumb?

I've tested the patch with xfs/599 as you suggested, and found the
issue. The test fails with:

  if (curr_hash <= prev_hash)
      return __this_address;

But passes with:

  if (curr_hash < prev_hash)
      return __this_address;

XFS supports entries with identical hash values. This aligns with commit
b7b81f336ac02f ("xfs_repair: fix incorrect dabtree hashval comparison").

I'll send a v2 that checks for non-decreasing hash values (allowing
equality), rather than strictly increasing ones.

>
> --D
>
>> > 
>> >  	return NULL;
>> >  }
>> > 
>> > ---
>> > base-commit: ecd5d67ad602c2c12e8709762717112ef0958767
>> > change-id: 20250412-xfs-hash-check-be7397881a2c
>> > 
>> > Best regards,
>> > --
>> > Charalampos Mitrodimas <charmitro@posteo.net>
>> > 
>>