xfs: Verify DA node btree hash order
PATCH 1/1 xfs: Verify DA node btree hash order
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.
--- fs/xfs/libxfs/xfs_da_btree.c | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-)
fs/xfs/libxfs/xfs_da_btree.c +10 -1
@@ -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; + }return NULL ; }
---
base-commit: ecd5d67ad602c2c12e8709762717112ef0958767
change-id: 20250412-xfs-hash-check-be7397881a2c
Best regards,
Signature · 1 line
Charalampos Mitrodimas <[email protected]>
Quoted 24 lines · Charalampos Mitrodimas
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 <[email protected]>--- fs/xfs/libxfs/xfs_da_btree.c | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-)fs/xfs/libxfs/xfs_da_btree.c +0
-0@@ -247,7 +247,16 @@ xfs_da3_node_verify( ichdr.count > mp->m_attr_geo->node_ents)
fs/xfs/libxfs/xfs_da_btree.c xfs_da3_node_verify( · line 256
Quoted 10 lines
fs/xfs/libxfs/xfs_da_btree.c +7
-1return __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)
Does XFS support a directory with two names that hash to the same value?
--D
Quoted 16 lines
fs/xfs/libxfs/xfs_da_btree.c +3
-1+return __this_address; + prev_hash = curr_hash; + }return NULL ; } ---base-commit:
ecd5d67ad602c2c12e8709762717112ef0958767
change-id: 20250412-xfs-hash-check-be7397881a2cBest regards,
Signature · 1 line
Charalampos Mitrodimas <[email protected]>
Quoted 27 lines · Darrick J. Wong
Quoted 26 lines · Charalampos Mitrodimas
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 <[email protected]>--- fs/xfs/libxfs/xfs_da_btree.c | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-)fs/xfs/libxfs/xfs_da_btree.c +0
-0@@ -247,7 +247,16 @@ xfs_da3_node_verify( ichdr.count > mp->m_attr_geo->node_ents)return __this_address;
Quoted 9 lines
fs/xfs/libxfs/xfs_da_btree.c xfs_da3_node_verify( · line 256
Quoted 8 lines
fs/xfs/libxfs/xfs_da_btree.c +7
-1-/* 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)Does XFS support a directory with two names that hash to the same value?
Hi Darrick,
I believe so, yes. These are handled at the leaf level by comparing the actual names. This adds a check which ensures the intermediate node's internal B-tree entries are strictly ordered by hash.
C. Mitrodimas
Quoted 19 lines
--D
Quoted 16 lines
fs/xfs/libxfs/xfs_da_btree.c +3
-1+return __this_address; + prev_hash = curr_hash; + }return NULL ; } ---base-commit:
ecd5d67ad602c2c12e8709762717112ef0958767
change-id: 20250412-xfs-hash-check-be7397881a2cBest regards,
Signature · 1 line
Charalampos Mitrodimas <[email protected]>
Carlos Maiolino
maintainerQuoted 27 lines · Charalampos Mitrodimas
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 <[email protected]>--- fs/xfs/libxfs/xfs_da_btree.c | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-)fs/xfs/libxfs/xfs_da_btree.c +0
-1@@ -247,7 +247,16 @@ xfs_da3_node_verify( ichdr.count > mp->m_attr_geo->node_ents)return __this_address; -/* XXX: hash order check? */
fs/xfs/libxfs/xfs_da_btree.c xfs_da3_node_verify( · line 259
Quoted 10 lines
fs/xfs/libxfs/xfs_da_btree.c +10
-0+/* 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.
Quoted 12 lines
fs/xfs/libxfs/xfs_da_btree.c +0
-1return NULL ; } ---base-commit:
ecd5d67ad602c2c12e8709762717112ef0958767
change-id: 20250412-xfs-hash-check-be7397881a2cBest regards,
--
Charalampos Mitrodimas <[email protected]>
Quoted 41 lines · Carlos Maiolino
Quoted 27 lines · Charalampos Mitrodimas
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 <[email protected]>--- fs/xfs/libxfs/xfs_da_btree.c | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-)fs/xfs/libxfs/xfs_da_btree.c +0
-1@@ -247,7 +247,16 @@ xfs_da3_node_verify( ichdr.count > mp->m_attr_geo->node_ents)return __this_address; -/* XXX: hash order check? */ fs/xfs/libxfs/xfs_da_btree.c xfs_da3_node_verify( · line 259
Quoted 10 lines
fs/xfs/libxfs/xfs_da_btree.c +10
-0+/* 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?
Quoted 7 lines
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.
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?
--D
Quoted 13 lines
Quoted 12 lines
fs/xfs/libxfs/xfs_da_btree.c +0
-1return NULL ; } ---base-commit:
ecd5d67ad602c2c12e8709762717112ef0958767
change-id: 20250412-xfs-hash-check-be7397881a2cBest regards,
--
Charalampos Mitrodimas <[email protected]>
Quoted 50 lines · Darrick J. Wong
Quoted 41 lines · Carlos Maiolino
Quoted 27 lines · Charalampos Mitrodimas
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 <[email protected]>--- fs/xfs/libxfs/xfs_da_btree.c | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-)fs/xfs/libxfs/xfs_da_btree.c +0
-1@@ -247,7 +247,16 @@ xfs_da3_node_verify( ichdr.count > mp->m_attr_geo->node_ents)return __this_address; -/* XXX: hash order check? */ fs/xfs/libxfs/xfs_da_btree.c xfs_da3_node_verify( · line 259
Quoted 10 lines
fs/xfs/libxfs/xfs_da_btree.c +10
-0+/* 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?
Quoted 7 lines
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.
Quoted 2 lines
It's only a single dabtree block, which will likely be warm in cache due to the crc32c validation.
Regardless, what is a good method of measuring the penalty, if any?
Quoted 7 lines
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'll rebase (in case) give it a try over the next weekend and reach back. AFAIR all tests where okay, but might gives us a hint if it is failing now.
Thanks for the review Darrick and Carlos.
C. Mitrodimas
Quoted 16 lines
--D
Quoted 13 lines
Quoted 12 lines
fs/xfs/libxfs/xfs_da_btree.c +0
-1return NULL ; } ---base-commit:
ecd5d67ad602c2c12e8709762717112ef0958767
change-id: 20250412-xfs-hash-check-be7397881a2cBest regards,
--
Charalampos Mitrodimas <[email protected]>
Quoted 50 lines · Darrick J. Wong
Quoted 41 lines · Carlos Maiolino
Quoted 27 lines · Charalampos Mitrodimas
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 <[email protected]>--- fs/xfs/libxfs/xfs_da_btree.c | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-)fs/xfs/libxfs/xfs_da_btree.c +0
-1@@ -247,7 +247,16 @@ xfs_da3_node_verify( ichdr.count > mp->m_attr_geo->node_ents)return __this_address; -/* XXX: hash order check? */ fs/xfs/libxfs/xfs_da_btree.c xfs_da3_node_verify( · line 259
Quoted 10 lines
fs/xfs/libxfs/xfs_da_btree.c +10
-0+/* 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?
Quoted 7 lines
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.
Quoted 2 lines
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.
Quoted 7 lines
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.
Quoted 16 lines
--D
Quoted 13 lines
Quoted 12 lines
fs/xfs/libxfs/xfs_da_btree.c +0
-1return NULL ; } ---base-commit:
ecd5d67ad602c2c12e8709762717112ef0958767
change-id: 20250412-xfs-hash-check-be7397881a2cBest regards,
--
Charalampos Mitrodimas <[email protected]>
Carlos Maiolino
maintainerQuoted 50 lines · Darrick J. Wong
Quoted 41 lines · Carlos Maiolino
Quoted 27 lines · Charalampos Mitrodimas
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 <[email protected]>--- fs/xfs/libxfs/xfs_da_btree.c | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-)fs/xfs/libxfs/xfs_da_btree.c +0
-1@@ -247,7 +247,16 @@ xfs_da3_node_verify( ichdr.count > mp->m_attr_geo->node_ents)return __this_address; -/* XXX: hash order check? */ fs/xfs/libxfs/xfs_da_btree.c xfs_da3_node_verify( · line 259
Quoted 10 lines
fs/xfs/libxfs/xfs_da_btree.c +10
-0+/* 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?
Quoted 7 lines
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.
Quoted 2 lines
It's only a single dabtree block, which will likely be warm in cache due to the crc32c validation.
I assumed this could be called to verify a leaf block, a look at the code seems that's not the case, so, this is perhaps harmless related to performance.
Quoted 23 lines
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?--D
Quoted 13 lines
Quoted 12 lines
fs/xfs/libxfs/xfs_da_btree.c +0
-1return NULL ; } ---base-commit:
ecd5d67ad602c2c12e8709762717112ef0958767
change-id: 20250412-xfs-hash-check-be7397881a2cBest regards,
--
Charalampos Mitrodimas <[email protected]>