Re: f2fs: Introduce linear search for dentries

["Theodore Ts'o" <tytso@mit.edu>]

[-- Attachment #1: Type: text/plain, Size: 1058 bytes --]

On Mon, Feb 03, 2025 at 03:07:10PM -0800, Daniel Rosenberg wrote:
> On Sat, Feb 1, 2025 at 9:06 AM Todd Kjos <tkjos@google.com> wrote:
> >
> > Before we can bring back the reverted patch, we need the same fix for
> > ext4. Daniel, is there progress on that?
> >
> Last I knew, Ted had a prototype patch for that, not sure what the
> current status of it is. I'm also not sure whether the unicode patch
> is being relanded, or if there's a different fix in the works there.

Between travel and an emergency at work, I haven't had time to create
the script to create a test file system to verify the prototype patch.
It turns out this is quite diffisult!

I finally managed to create a script which demonstrates why the revert
was necessary, but it wasn't enough to demonstrate why a further patch
is needed.  I think I know what I need to do, but it's a mess and I've
already wasted hours and hours in this.

Do you have a relible script to generate a test file system.  This is
what I have so far, but as I said, it's not quite good enough...

					- Ted


[-- Attachment #2: unicode-hijinks --]
[-- Type: text/plain, Size: 2295 bytes --]

#!/bin/bash
#
# Generate a test file system to verify the handling of mess with
# Uniode insanity known as "inorable code points".
#
# I - ignore/no-ignore invisible "evil" Unicode characters
# E -encrypt/no-encrypt
# H - htree/no-htree
# F - case-fold/no-casefold
#
# Run this with first with a kernel new to include the commit
# 231825b2e1ff ("Revert "unicode: Don't special case ignorable code
# points".  Then boot a kernel checked out to commit 5c26d2f1d3f5
# ("unicode: Don't special case ignorable code points") and run this
# script with the -I option.
#
# To test the file system, boot the kernel you want to test, and copy
# the test file system imge to /tmp/foo.img, and then run the commands:
#
#    unicode-hijinks -m
#    unicode-hijinks -l

FS=/tmp/foo.img
I=no-I

TEST_RAW_KEY=
for i in {1..64}; do
	TEST_RAW_KEY+="\\x$(printf "%02x" $i)"
done
# Key identifier: HKDF-SHA512(key=$TEST_RAW_KEY, salt="", info="fscrypt\0\x01")
TEST_KEY_IDENTIFIER="69b2f6edeee720cce0577937eb8a6751"

case "$1" in
    -I)
	I=I
	;;
    -m)
	mount /tmp/foo.img /mnt
	echo -ne "$TEST_RAW_KEY" | xfs_io -c add_enckey /mnt
	exit 0
	;;
    -l)
	for i in I no-I ; do
	    for e in E no-E ; do
		for f in F no-F ; do
		    for h in H no-H ; do
			ls -il /mnt/$i/$e/$f/$h/❤️
			ls -il /mnt/$i/$e/$f/$h/❤
		    done
		done
	    done
	done
	exit 0
	;;
    "") :
	;;
    *)
	echo "usage: unicode-hijinks -I|-m|-l"
	exit 1
esac

function gen_files ()
{
    echo "red heart" > ❤️
    echo "black heart" > ❤
}

function mk_htree ()
{
    seq 1 1000 | xargs -I Z touch XXXXXXXXXXXXXXXXXXX-Z
}

function mk_casefold ()
{
    chattr +F .
}

function mk_htree_set ()
{
    mkdir no-H ; cd no-H ; gen_files ; cd ..
    mkdir H ; cd H ; mk_htree ; gen_files ; cd ..
}

function mk_htree_and_casefold ()
{
    mkdir no-F; cd no-F; mk_htree_set ; cd ..
    mkdir F; cd F ; mk_casefold ; mk_htree_set ; cd ..
}


if [ "$I" = "no-I" ] ; then
    mke2fs -t ext4 -Fq -b 1024 -N 8192 -O casefold,encrypt $FS 4M
fi
mount $FS /mnt

echo -ne "$TEST_RAW_KEY" | xfs_io -c add_enckey /mnt
xfs_io -c "enckey_status $TEST_KEY_IDENTIFIER" /mnt
cd /mnt
mkdir $I
cd $I
mkdir no-E
cd no-E
mk_htree_and_casefold
cd /mnt
cd $I
mkdir E
xfs_io -c "set_encpolicy $TEST_KEY_IDENTIFIER" E
cd E
mk_htree_and_casefold
cd /
umount /mnt