Skip to contentSkip to conversation

xfs: check hash ordering in xfs_da3_node_verify

PATCH In review Yuto Ohnuki 3 participants 4 messages Apr 15 – Apr 20 XFS filesystem

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 xfs: check hash ordering in xfs_da3_node_verify

The DA node verifier checks header fields such as level and count, but it does not verify that the btree hash values are in non-decreasing order.

DA node blocks are traversed by searching the btree array for the first hash value that exceeds the lookup hash, which requires the hash values to be ordered correctly.

Add a hash order check to xfs_da3_node_verify, similar to the existing validation in xfs_dir3_leaf_check_int, so that misordered node blocks are detected as metadata corruption.

---
 fs/xfs/libxfs/xfs_da_btree.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)
fs/xfs/libxfs/xfs_da_btree.c +7 -1
index ad801b7bd2dd..ef49df22899e 100644
@@ -225,6 +225,7 @@ xfs_da3_node_verify(
 	struct xfs_da_intnode	*hdr = bp->b_addr;
 	struct xfs_da3_icnode_hdr ichdr;
 	xfs_failaddr_t		fa;
+	int			i;
 
 	xfs_da3_node_hdr_from_disk(mp, &ichdr, hdr);
 
@@ -247,7 +248,12 @@ xfs_da3_node_verify(
 	    ichdr.count > mp->m_attr_geo->node_ents)
 		return __this_address;
 
-	/* XXX: hash order check? */
+	/* Check hash value order. */
+	for (i = 0; i + 1 < ichdr.count; i++) {
+		if (be32_to_cpu(ichdr.btree[i].hashval) >
+				be32_to_cpu(ichdr.btree[i + 1].hashval))
+			return __this_address;
+	}
 
 	return NULL;
 }
Signature · 8 lines
2.50.1




Amazon Web Services EMEA SARL, 38 avenue John F. Kennedy, L-1855 Luxembourg, R.C.S. Luxembourg B186284

Amazon Web Services EMEA SARL, Irish Branch, One Burlington Plaza, Burlington Road, Dublin 4, Ireland, branch registration number 908705
#1 lore raw
Quoted 30 lines · Yuto Ohnuki

The DA node verifier checks header fields such as level and count, but it does not verify that the btree hash values are in non-decreasing order.

DA node blocks are traversed by searching the btree array for the first hash value that exceeds the lookup hash, which requires the hash values to be ordered correctly.

Add a hash order check to xfs_da3_node_verify, similar to the existing validation in xfs_dir3_leaf_check_int, so that misordered node blocks are detected as metadata corruption.

---
 fs/xfs/libxfs/xfs_da_btree.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)
fs/xfs/libxfs/xfs_da_btree.c +1 -0
index ad801b7bd2dd..ef49df22899e 100644
@@ -225,6 +225,7 @@ xfs_da3_node_verify(
 	struct xfs_da_intnode	*hdr = bp->b_addr;
 	struct xfs_da3_icnode_hdr ichdr;
 	xfs_failaddr_t		fa;
+	int			i;
 
 	xfs_da3_node_hdr_from_disk(mp, &ichdr, hdr);
 

fs/xfs/libxfs/xfs_da_btree.c xfs_da3_node_verify( · line 252

Quoted 6 lines
fs/xfs/libxfs/xfs_da_btree.c +2 -1
@@ -247,7 +248,12 @@ xfs_da3_node_verify(
 	    ichdr.count > mp->m_attr_geo->node_ents)
 		return __this_address;
 
-	/* XXX: hash order check? */
+	/* Check hash value order. */
+	for (i = 0; i + 1 < ichdr.count; i++) {

I guess that works, though I'd have iterated from i to ichdr.count and done the test on the previous element (like scrub/dir.c does).

fs/xfs/libxfs/xfs_da_btree.c xfs_da3_node_verify( · line 254

Quoted 2 lines
fs/xfs/libxfs/xfs_da_btree.c +2 -0
+		if (be32_to_cpu(ichdr.btree[i].hashval) >
+				be32_to_cpu(ichdr.btree[i + 1].hashval))

I think this might be one of the few places where doing kernel style indentation of the if test flows better:

	for (i = 1; i < ichdr.count; i++) {
		if (be32_to_cpu(ichdr.btree[i - 1].hashval) >
		    be32_to_cpu(ichdr.btree[i].hashval))

The logic is solid though.

--D

Quoted 18 lines
fs/xfs/libxfs/xfs_da_btree.c +2 -0
+			return __this_address;
+	}
 
 	return NULL;
 }
Signature · 8 lines
2.50.1




Amazon Web Services EMEA SARL, 38 avenue John F. Kennedy, L-1855 Luxembourg, R.C.S. Luxembourg B186284

Amazon Web Services EMEA SARL, Irish Branch, One Burlington Plaza, Burlington Road, Dublin 4, Ireland, branch registration number 908705
#2 lore raw
Quoted 9 lines · Darrick J. Wong
Quoted 8 lines · Yuto Ohnuki

The DA node verifier checks header fields such as level and count, but it does not verify that the btree hash values are in non-decreasing order.

DA node blocks are traversed by searching the btree array for the first hash value that exceeds the lookup hash, which requires the hash values to be ordered correctly.

Quoted 5 lines
Quoted 5 lines

Add a hash order check to xfs_da3_node_verify, similar to the existing validation in xfs_dir3_leaf_check_int, so that misordered node blocks are detected as metadata corruption.

There were good reasons why this wasn't implemented originally but marked with an 'XXX: <question>' comment. It's not because it is hard to implement, but because it is an -expensive- check and it is has never been clear that the check would ever actually find corruptions in production systems.

That is, any media level error that could corrupt a hash value will be caught by the CRCs, hence the only vector for a production system to experience an out of order hash value is a bug in the XFS kernel code.

This situation has not changed in the past 12-13 years, so....

... what's the CPU cost of doing this check? How much performance does this cost for cold cache directory traversal?

What if we have 64kB directory blocks and a full dabtree node? i.e. this will iterate 64kB of 4 byte hash values one at time, so how much does that cost?

What is the possible impacts of an out of order has entry? Lookups may not find the entry they are looking for, so files might be missing from directories. Even modifications will simply result in more out of order hash values or trip over out of order keys in path traversal which will trigger corruption reports and maybe shutdowns. I'm not sure there is anything else that can go wrong at runtime.

Hence even fuzzers like syzbot creating out of order hash entries shouldn't result in crashes or other sorts of serious failures.

In which case, how much extra protection against corruption based failures does runtime detection in production systems actually gain us? Is it worth the cost of running this verification on every directory node read and write?

If the only real issue we need to defend against is software bugs, then we should be modelling the verification on xfs_dir3_data_check(). That's runtime dir3 data block check function that is only run on DEBUG kernels. It is placed in the data block modification code to catch corruptions immediately after the broken modification code has created them. This seems like a similar situation to me.

-Dave.

Signature · 2 lines
Dave Chinner
[email protected]
#3 lore raw
Quoted 11 lines · Dave Chinner

There were good reasons why this wasn't implemented originally but marked with an 'XXX: <question>' comment. It's not because it is hard to implement, but because it is an -expensive- check and it is has never been clear that the check would ever actually find corruptions in production systems.

That is, any media level error that could corrupt a hash value will be caught by the CRCs, hence the only vector for a production system to experience an out of order hash value is a bug in the XFS kernel code.

Quoted 4 lines

This situation has not changed in the past 12-13 years, so....

... what's the CPU cost of doing this check? How much performance does this cost for cold cache directory traversal?

I confirmed that the hash order check does detect misordered entries as expected, but I have not measured the performance cost yet. Thank you for pointing that out.

Quoted 27 lines

What if we have 64kB directory blocks and a full dabtree node? i.e. this will iterate 64kB of 4 byte hash values one at time, so how much does that cost?

What is the possible impacts of an out of order has entry? Lookups may not find the entry they are looking for, so files might be missing from directories. Even modifications will simply result in more out of order hash values or trip over out of order keys in path traversal which will trigger corruption reports and maybe shutdowns. I'm not sure there is anything else that can go wrong at runtime.

Hence even fuzzers like syzbot creating out of order hash entries shouldn't result in crashes or other sorts of serious failures.

In which case, how much extra protection against corruption based failures does runtime detection in production systems actually gain us? Is it worth the cost of running this verification on every directory node read and write?

If the only real issue we need to defend against is software bugs, then we should be modelling the verification on xfs_dir3_data_check(). That's runtime dir3 data block check function that is only run on DEBUG kernels. It is placed in the data block modification code to catch corruptions immediately after the broken modification code has created them. This seems like a similar situation to me.

Quoted 4 lines

-Dave.

Signature · 2 lines
Dave Chinner
[email protected]

That makes sense. I'll rework this as a DEBUG-only check modelled on xfs_dir3_data_check(), and adopt Darrick's style suggestions as well.

Thanks for the review.

Yuto

Amazon Web Services EMEA SARL, 38 avenue John F. Kennedy, L-1855 Luxembourg, R.C.S. Luxembourg B186284

Amazon Web Services EMEA SARL, Irish Branch, One Burlington Plaza, Burlington Road, Dublin 4, Ireland, branch registration number 908705