btrfs: test if rename handles dir item collision correctly
PATCH v2 1/1 btrfs: test if rename handles dir item collision correctly
This is a regression test for the issue fixed by the kernel commit titled "btrfs: correctly calculate item size used when item key collision happens"
In this case, we'll simply rename many forged filename that cause collision under a directory to see if rename failed and filesystem is forced readonly.
---
v2:
- Add a python script to generate the forged name at run-time rather than from hardcoded names
- Fix , Btrfs->btrfs, and typo mentioned in v1
src/btrfs_crc32c_forged_name.py | 92 +++++++++++++++++++++++++++++++++ tests/btrfs/228 | 72 ++++++++++++++++++++++++++ tests/btrfs/228.out | 2 + tests/btrfs/group | 1 + 4 files changed, 167 insertions(+) create mode 100755 src/btrfs_crc32c_forged_name.py create mode 100755 tests/btrfs/228 create mode 100644 tests/btrfs/228.out
src/btrfs_crc32c_forged_name.py new file +92 -0
@@ -0,0 +1,92 @@ +# SPDX-License-Identifier: GPL-2.0 + +import struct +import sys +import os +import argparse + +class CRC32(object): + """A class to calculate and manipulate CRC32.""" + def __init__(self): + self.polynom = 0x82F63B78 + self.table, self.reverse = [0]*256, [0]*256 + self._build_tables() + + def _build_tables(self): + for i in range(256): + fwd = i + rev = i << 24 + for j in range(8, 0, -1): + # build normal table + if (fwd & 1) == 1: + fwd = (fwd >> 1) ^ self.polynom + else: + fwd >>= 1 + self.table[i] = fwd & 0xffffffff + # build reverse table =) + if rev & 0x80000000 == 0x80000000: + rev = ((rev ^ self.polynom) << 1) | 1 + else: + rev <<= 1 + rev &= 0xffffffff + self.reverse[i] = rev + + def calc(self, s): + """Calculate crc32 of a string. + Same crc32 as in (binascii.crc32)&0xffffffff. + """ + crc = 0xffffffff + for c in s: + crc = (crc >> 8) ^ self.table[(crc ^ ord(c)) & 0xff] + return crc^0xffffffff + + def forge(self, wanted_crc, s, pos=None): + """Forge crc32 of a string by adding 4 bytes at position pos.""" + if pos is None: + pos = len(s) + + # forward calculation of CRC up to pos, sets current forward CRC state + fwd_crc = 0xffffffff + for c in s[:pos]: + fwd_crc = (fwd_crc >> 8) ^ self.table[(fwd_crc ^ ord(c)) & 0xff] + + # backward calculation of CRC up to pos, sets wanted backward CRC state + bkd_crc = wanted_crc^0xffffffff + for c in s[pos:][::-1]: + bkd_crc = ((bkd_crc << 8) & 0xffffffff) ^ self.reverse[bkd_crc >> 24] + bkd_crc ^= ord(c) + + # deduce the 4 bytes we need to insert + for c in struct.pack('<L',fwd_crc)[::-1]: + bkd_crc = ((bkd_crc << 8) & 0xffffffff) ^ self.reverse[bkd_crc >> 24] + bkd_crc ^= ord(c) + + res = s[:pos] + struct.pack('<L', bkd_crc) + s[pos:] + return res + + def parse_args(self): + parser = argparse.ArgumentParser() + parser.add_argument("-d", default=os.getcwd(), dest='dir', + help="directory to generate forged names") + parser.add_argument("-c", default=1, type=int, dest='count', + help="number of forged names to create") + return parser.parse_args() + +if __name__=='__main__': + + crc = CRC32() + wanted_crc = 0x00000000 + count = 0 + args = crc.parse_args() + dirpath=args.dir + while count < args.count : + origname = os.urandom (89).encode ("hex")[:-1].strip ("\x00") + forgename = crc.forge(wanted_crc, origname, 4) + if ("/" not in forgename) and ("\x00" not in forgename): + srcpath=dirpath + '/' + str(count) + dstpath=dirpath + '/' + forgename + file (srcpath, 'a').close() + os.rename(srcpath, dstpath) + os.system('btrfs fi sync %s' % (dirpath)) + count+=1; +
tests/btrfs/228 new file +72 -0
72 lines not on this page · raw message
tests/btrfs/228.out new file +2 -0
@@ -0,0 +1,2 @@ +QA output created by 228 +FS is Read-Write Test OK
tests/btrfs/group +1 -0
@@ -228,3 +228,4 @@ 224 auto quick qgroup 225 auto quick volume seed 226 auto quick rw snapshot clone prealloc punch +228 auto quick
Signature · 1 line
2.25.1
Quoted 186 lines · ethanwu
This is a regression test for the issue fixed by the kernel commit titled "btrfs: correctly calculate item size used when item key collision happens"
In this case, we'll simply rename many forged filename that cause collision under a directory to see if rename failed and filesystem is forced readonly.
Signed-off-by ethanwu <[email protected]>---
v2:
- Add a python script to generate the forged name at run-time rather than from hardcoded names
- Fix ,Btrfs->btrfs, and typo mentioned in v1src/btrfs_crc32c_forged_name.py | 92 +++++++++++++++++++++++++++++++++ tests/btrfs/228 | 72 ++++++++++++++++++++++++++ tests/btrfs/228.out | 2 + tests/btrfs/group | 1 + 4 files changed, 167 insertions(+) create mode 100755 src/btrfs_crc32c_forged_name.py create mode 100755 tests/btrfs/228 create mode 100644 tests/btrfs/228.outsrc/btrfs_crc32c_forged_name.py new file +92
-0@@ -0,0 +1,92 @@ +# SPDX-License-Identifier: GPL-2.0 + +import struct +import sys +import os +import argparse + +class CRC32(object): + """A class to calculate and manipulate CRC32.""" + def __init__(self): + self.polynom = 0x82F63B78 + self.table, self.reverse = [0]*256, [0]*256 + self._build_tables() + + def _build_tables(self): + for i in range(256): + fwd = i + rev = i << 24 + for j in range(8, 0, -1): + # build normal table + if (fwd & 1) == 1: + fwd = (fwd >> 1) ^ self.polynom + else: + fwd >>= 1 + self.table[i] = fwd & 0xffffffff + # build reverse table =) + if rev & 0x80000000 == 0x80000000: + rev = ((rev ^ self.polynom) << 1) | 1 + else: + rev <<= 1 + rev &= 0xffffffff + self.reverse[i] = rev + + def calc(self, s): + """Calculate crc32 of a string. + Same crc32 as in (binascii.crc32)&0xffffffff. + """ + crc = 0xffffffff + for c in s: + crc = (crc >> 8) ^ self.table[(crc ^ ord(c)) & 0xff] + return crc^0xffffffff + + def forge(self, wanted_crc, s, pos=None): + """Forge crc32 of a string by adding 4 bytes at position pos.""" + if pos is None: + pos = len(s) + + # forward calculation of CRC up to pos, sets current forward CRC state + fwd_crc = 0xffffffff + for c in s[:pos]: + fwd_crc = (fwd_crc >> 8) ^ self.table[(fwd_crc ^ ord(c)) & 0xff] + + # backward calculation of CRC up to pos, sets wanted backward CRC state + bkd_crc = wanted_crc^0xffffffff + for c in s[pos:][::-1]: + bkd_crc = ((bkd_crc << 8) & 0xffffffff) ^ self.reverse[bkd_crc >> 24] + bkd_crc ^= ord(c) + + # deduce the 4 bytes we need to insert + for c in struct.pack('<L',fwd_crc)[::-1]: + bkd_crc = ((bkd_crc << 8) & 0xffffffff) ^ self.reverse[bkd_crc >> 24] + bkd_crc ^= ord(c) + + res = s[:pos] + struct.pack('<L', bkd_crc) + s[pos:] + return res + + def parse_args(self): + parser = argparse.ArgumentParser() + parser.add_argument("-d", default=os.getcwd(), dest='dir', + help="directory to generate forged names") + parser.add_argument("-c", default=1, type=int, dest='count', + help="number of forged names to create") + return parser.parse_args() + +if __name__=='__main__': + + crc = CRC32() + wanted_crc = 0x00000000 + count = 0 + args = crc.parse_args() + dirpath=args.dir + while count < args.count : + origname = os.urandom (89).encode ("hex")[:-1].strip ("\x00") + forgename = crc.forge(wanted_crc, origname, 4) + if ("/" not in forgename) and ("\x00" not in forgename): + srcpath=dirpath + '/' + str(count) + dstpath=dirpath + '/' + forgename + file (srcpath, 'a').close() + os.rename(srcpath, dstpath) + os.system('btrfs fi sync %s' % (dirpath)) + count+=1; +tests/btrfs/228 new file +59
-0@@ -0,0 +1,72 @@ +#! /bin/bash +# SPDX-License-Identifier: GPL-2.0 +# Copyright (c) 2020 Synology. All Rights Reserved. +# +# FS QA Test 228 +# +# Test if btrfs rename handle dir item collision correctly +# Without patch fix, rename will fail with EOVERFLOW, and filesystem +# is forced readonly. +# +# This bug is going to be fixed by a patch for kernel titled +# "btrfs: correctly calculate item size used when item key collision happens" +# +seq=`basename $0` +seqres=$RESULT_DIR/$seq +echo "QA output created by $seq" + +here=`pwd` +tmp=/tmp/$$ +status=1 # failure is the default! +trap "_cleanup; exit \$status" 0 1 2 3 15 + +_cleanup() +{ + cd / + rm -f $tmp.* +} + +# get standard environment, filters and checks +. ./common/rc +. ./common/filter + +# real QA test starts here + +_supported_fs btrfs +_require_scratch +_require_command $PYTHON2_PROG python2 + +rm -f $seqres.full + +# Currently in btrfs the node/leaf size can not be smaller than the page +# size (but it can be greater than the page size). So use the largest +# supported node/leaf size (64Kb) so that the test can run on any platform +# that Linux supports. +_scratch_mkfs "--nodesize 65536" >>$seqres.full 2>&1 +_scratch_mount + +# +# In the following for loop, we'll create a leaf fully occupied by +# only one dir item with many forged collision names in it. +# +# leaf 22544384 items 1 free space 0 generation 6 owner FS_TREE +# leaf 22544384 flags 0x1(WRITTEN) backref revision 1 +# fs uuid 9064ba52-3d2c-4840-8e26-35db08fa17d7 +# chunk uuid 9ba39317-3159-46c9-a75a-965ab1e94267 +# item 0 key (256 DIR_ITEM 3737737011) itemoff 25 itemsize 65410 +# ... +# +
tests/btrfs/228 line 69
Quoted 10 lines
tests/btrfs/228 new file +10
-0+$PYTHON2_PROG $here/src/btrfs_crc32c_forged_name.py -d $SCRATCH_MNT -c 310 + +ISRW=$(_fs_options $SCRATCH_DEV | grep -w "rw") +if [ -n "$ISRW" ]; then + echo "FS is Read-Write Test OK" +else + echo "FS is Read-Only. Test Failed" + status=1 + exit +fi
You don't need to print these messages. In case the test fails:
1) There's a warning stack trace in dmesg, that alone makes the test fail since fstests checks for warnings in dmesg and reports the test as failed is any exist;
2) The test script results in python dumping a stack trace, which causes a mismatch with the golden output, therefore making the test fail:
Traceback (most recent call last):
File "/home/fdmanana/git/hub/xfstests/src/btrfs_crc32c_forged_name.py",
line 89, in <module>
os.rename(srcpath, dstpath)
OSError: [Errno 75] Value too large for defined data type
Anyway, it's a minor thing, if Eryu doesn't like it, I suppose we can remove that if-then-else and just replace it with "echo Silence is golden".
Thank you very much for writing the test case Ethan!
Quoted 23 lines
tests/btrfs/228 new file +3
-0+ +# success, all done +status=0; exittests/btrfs/228.out new file +2
-0@@ -0,0 +1,2 @@ +QA output created by 228 +FS is Read-Write Test OKtests/btrfs/group +1
-1@@ -228,3 +228,4 @@ 224 auto quick qgroup 225 auto quick volume seed 226 auto quick rw snapshot clone prealloc punch +228 auto quick --2.25.1
Signature · 3 lines
Filipe David Manana, “Whether you think you can, or you think you can't — you're right.”
Quoted 213 lines · Filipe Manana
Quoted 186 lines · ethanwu
This is a regression test for the issue fixed by the kernel commit titled "btrfs: correctly calculate item size used when item key collision happens"
In this case, we'll simply rename many forged filename that cause collision under a directory to see if rename failed and filesystem is forced readonly.
Signed-off-by ethanwu <[email protected]>---
v2:
- Add a python script to generate the forged name at run-time rather than from hardcoded names
- Fix ,Btrfs->btrfs, and typo mentioned in v1src/btrfs_crc32c_forged_name.py | 92 +++++++++++++++++++++++++++++++++ tests/btrfs/228 | 72 ++++++++++++++++++++++++++ tests/btrfs/228.out | 2 + tests/btrfs/group | 1 + 4 files changed, 167 insertions(+) create mode 100755 src/btrfs_crc32c_forged_name.py create mode 100755 tests/btrfs/228 create mode 100644 tests/btrfs/228.outsrc/btrfs_crc32c_forged_name.py new file +92
-0@@ -0,0 +1,92 @@ +# SPDX-License-Identifier: GPL-2.0 + +import struct +import sys +import os +import argparse + +class CRC32(object): + """A class to calculate and manipulate CRC32.""" + def __init__(self): + self.polynom = 0x82F63B78 + self.table, self.reverse = [0]*256, [0]*256 + self._build_tables() + + def _build_tables(self): + for i in range(256): + fwd = i + rev = i << 24 + for j in range(8, 0, -1): + # build normal table + if (fwd & 1) == 1: + fwd = (fwd >> 1) ^ self.polynom + else: + fwd >>= 1 + self.table[i] = fwd & 0xffffffff + # build reverse table =) + if rev & 0x80000000 == 0x80000000: + rev = ((rev ^ self.polynom) << 1) | 1 + else: + rev <<= 1 + rev &= 0xffffffff + self.reverse[i] = rev + + def calc(self, s): + """Calculate crc32 of a string. + Same crc32 as in (binascii.crc32)&0xffffffff. + """ + crc = 0xffffffff + for c in s: + crc = (crc >> 8) ^ self.table[(crc ^ ord(c)) & 0xff] + return crc^0xffffffff + + def forge(self, wanted_crc, s, pos=None): + """Forge crc32 of a string by adding 4 bytes at position pos.""" + if pos is None: + pos = len(s) + + # forward calculation of CRC up to pos, sets current forward CRC state + fwd_crc = 0xffffffff + for c in s[:pos]: + fwd_crc = (fwd_crc >> 8) ^ self.table[(fwd_crc ^ ord(c)) & 0xff] + + # backward calculation of CRC up to pos, sets wanted backward CRC state + bkd_crc = wanted_crc^0xffffffff + for c in s[pos:][::-1]: + bkd_crc = ((bkd_crc << 8) & 0xffffffff) ^ self.reverse[bkd_crc >> 24] + bkd_crc ^= ord(c) + + # deduce the 4 bytes we need to insert + for c in struct.pack('<L',fwd_crc)[::-1]: + bkd_crc = ((bkd_crc << 8) & 0xffffffff) ^ self.reverse[bkd_crc >> 24] + bkd_crc ^= ord(c) + + res = s[:pos] + struct.pack('<L', bkd_crc) + s[pos:] + return res + + def parse_args(self): + parser = argparse.ArgumentParser() + parser.add_argument("-d", default=os.getcwd(), dest='dir', + help="directory to generate forged names") + parser.add_argument("-c", default=1, type=int, dest='count', + help="number of forged names to create") + return parser.parse_args() + +if __name__=='__main__': + + crc = CRC32() + wanted_crc = 0x00000000 + count = 0 + args = crc.parse_args() + dirpath=args.dir + while count < args.count : + origname = os.urandom (89).encode ("hex")[:-1].strip ("\x00") + forgename = crc.forge(wanted_crc, origname, 4) + if ("/" not in forgename) and ("\x00" not in forgename): + srcpath=dirpath + '/' + str(count) + dstpath=dirpath + '/' + forgename + file (srcpath, 'a').close() + os.rename(srcpath, dstpath) + os.system('btrfs fi sync %s' % (dirpath)) + count+=1; +tests/btrfs/228 new file +59
-0@@ -0,0 +1,72 @@ +#! /bin/bash +# SPDX-License-Identifier: GPL-2.0 +# Copyright (c) 2020 Synology. All Rights Reserved. +# +# FS QA Test 228 +# +# Test if btrfs rename handle dir item collision correctly +# Without patch fix, rename will fail with EOVERFLOW, and filesystem +# is forced readonly. +# +# This bug is going to be fixed by a patch for kernel titled +# "btrfs: correctly calculate item size used when item key collision happens" +# +seq=`basename $0` +seqres=$RESULT_DIR/$seq +echo "QA output created by $seq" + +here=`pwd` +tmp=/tmp/$$ +status=1 # failure is the default! +trap "_cleanup; exit \$status" 0 1 2 3 15 + +_cleanup() +{ + cd / + rm -f $tmp.* +} + +# get standard environment, filters and checks +. ./common/rc +. ./common/filter + +# real QA test starts here + +_supported_fs btrfs +_require_scratch +_require_command $PYTHON2_PROG python2 + +rm -f $seqres.full + +# Currently in btrfs the node/leaf size can not be smaller than the page +# size (but it can be greater than the page size). So use the largest +# supported node/leaf size (64Kb) so that the test can run on any platform +# that Linux supports. +_scratch_mkfs "--nodesize 65536" >>$seqres.full 2>&1 +_scratch_mount + +# +# In the following for loop, we'll create a leaf fully occupied by +# only one dir item with many forged collision names in it. +# +# leaf 22544384 items 1 free space 0 generation 6 owner FS_TREE +# leaf 22544384 flags 0x1(WRITTEN) backref revision 1 +# fs uuid 9064ba52-3d2c-4840-8e26-35db08fa17d7 +# chunk uuid 9ba39317-3159-46c9-a75a-965ab1e94267 +# item 0 key (256 DIR_ITEM 3737737011) itemoff 25 itemsize 65410 +# ... +# +tests/btrfs/228 line 69
Quoted 10 lines
tests/btrfs/228 new file +10
-0+$PYTHON2_PROG $here/src/btrfs_crc32c_forged_name.py -d $SCRATCH_MNT -c 310 + +ISRW=$(_fs_options $SCRATCH_DEV | grep -w "rw") +if [ -n "$ISRW" ]; then + echo "FS is Read-Write Test OK" +else + echo "FS is Read-Only. Test Failed" + status=1 + exit +fiYou don't need to print these messages. In case the test fails:
1) There's a warning stack trace in dmesg, that alone makes the test fail since fstests checks for warnings in dmesg and reports the test as failed is any exist;
2) The test script results in python dumping a stack trace, which causes a mismatch with the golden output, therefore making the test fail:Traceback (most recent call last):
File "/home/fdmanana/git/hub/xfstests/src/btrfs_crc32c_forged_name.py",
line 89, in <module>
os.rename(srcpath, dstpath)
OSError: [Errno 75] Value too large for defined data type
Quoted 3 lines
Anyway, it's a minor thing, if Eryu doesn't like it, I suppose we can remove that if-then-else and just replace it with "echo Silence is golden".
Updated the patch as you suggested.
Quoted 4 lines
Reviewed-by Filipe Manana <[email protected]>Thank you very much for writing the test case Ethan!
Thanks for the test and review!
Eryu
Quoted 30 lines
Quoted 24 lines
tests/btrfs/228 new file +3
-0+ +# success, all done +status=0; exittests/btrfs/228.out new file +2
-0@@ -0,0 +1,2 @@ +QA output created by 228 +FS is Read-Write Test OKtests/btrfs/group +1
-1@@ -228,3 +228,4 @@ 224 auto quick qgroup 225 auto quick volume seed 226 auto quick rw snapshot clone prealloc punch +228 auto quick --2.25.1
Signature · 3 lines
Filipe David Manana, “Whether you think you can, or you think you can't — you're right.”