Re: [v4 3/3] bcachefs: Implement casefolding

Joshua Ashton
2023-08-14T21:34:41Z

On 8/14/23 22:18, Joshua Ashton wrote:
>
>
> On 8/14/23 17:34, Gabriel Krisman Bertazi wrote:
>> Joshua Ashton <joshua@froggi.es> writes:
>>
>>> This patch implements support for case-insensitive file name lookups
>>> in bcachefs.
>>>
>>> The implementation uses the same UTF-8 lowering and normalization that
>>> ext4 and f2fs is using.
>>>
>>> More information is provided in Documentation/bcachefs/casefolding.rst
>>>
>>> Signed-off-by: Joshua Ashton <joshua@froggi.es>
>>
>> Please, cc the entire thread as i don't think I even got the cover
>> letter.
>
> Thanks, I will for v5.
>
>>
>> Did you test this against fstests generic/556?  it checks all sorts of
>> common pitfalls and corner-cases in case-insensitive filesystems.
>
> No, I wrote my own casefolding test that tests a bunch of edgecases.
>
> I was not aware there were any casefolding tests in fstests -- I really
> really wish they had better names. :/
>
> Grepping the test right now I already know we will fail the
> `test_casefold_flag_removal` test as we don't support toggling the flag
> on non-empty directories as it would require rehashing and thus
> restructuring the btree.
>
> There's a lot of edgecases to handle there (such as hash collisions)
> which are pretty gnarly to solve when doing something like that.
>
> I diiiid try and implement something that did that, but it really did
> not end well... ^^;; So planning to defer this for now.
>
>>
>>> --- /dev/null
>>> +++ b/Documentation/filesystems/bcachefs/casefolding.rst
>>> @@ -0,0 +1,73 @@
>>> +.. SPDX-License-Identifier: GPL-2.0
>>> +
>>> +Casefolding
>>> +===========
>>> +
>>> +bcachefs has support for case-insensitive file and directory
>>> +lookups using the regular `chattr +F` (`S_CASEFOLD`, `FS_CASEFOLD_FL`)
>>> +casefolding attributes.
>>> +
>>> +The main usecase for casefolding is compatibility with software written
>>> +against other filesystems that rely on casefolded lookups
>>> +(eg. NTFS and Wine/Proton).
>>> +Taking advantage of file-system level casefolding can lead to great
>>> +loading time gains in many applications and games.
>>> +
>>> +Casefolding support requires a kernel with the `CONFIG_UNICODE`
>>> enabled.
>>> +Once a directory has been flagged for casefolding, a feature bit
>>> +is enabled on the superblock which marks the filesystem as using
>>> +casefolding.
>>> +When the feature bit for casefolding is enabled, it is no longer
>>> possible
>>> +to mount that filesystem on kernels without `CONFIG_UNICODE` enabled.
>>> +
>>> +On the lookup/query side: casefolding is implemented by allocating a
>>> new
>>> +string of `BCH_NAME_MAX` length using the `utf8_casefold` function to
>>> +casefold the query string.
>>> +
>>> +On the dirent side: casefolding is implemented by ensuring the `bkey`'s
>>> +hash is made from the casefolded string and storing the cached
>>> casefolded
>>> +name with the regular name in the dirent.
>>> +
>>> +The structure looks like this:
>>> +
>>> +Regular:    [dirent data][regular name][nul][nul]...
>>> +Casefolded: [dirent data][reg len][cf len][regular name][casefolded
>>> name][nul][nul]...
>>> +
>>> +(Do note, the number of `NUL`s here is merely for illustration, they
>>> count can vary
>>> + per-key, and they may not even be present if the key is aligned to
>>> `sizeof(u64)`.)
>>> +
>>> +This is efficient as it means that for all file lookups that require
>>> casefolding,
>>> +it has identical performance to a regular lookup:
>>> +a hash comparison and a `memcmp` of the name.
>>> +
>>> +Rationale
>>> +---------
>>> +
>>> +Several designs were considered for this system:
>>> +One was to introduce a dirent_v2, however that would be painful
>>> especially as
>>> +the hash system only has support for a single key type. This would
>>> also need
>>> +`BCH_NAME_MAX` to change between versions, and a new feature bit.
>>> +
>>> +Another option was to store without the two lengths, and just take
>>> the length of
>>> +the regular name and casefolded name contiguously / 2 as the length.
>>> This would
>>> +assume that the regular length == casefolded length, but that could
>>> potentially
>>> +not be true, if the uppercase unicode glyph had a different UTF-8
>>> encoding than
>>> +the lowercase unicode glyph.
>>
>> Why do you want to store the casefolded name?  In ext4, we just store
>> the case-exact name that was created, and do a code-point by code-point
>> comparison with the name under lookup through utf8_strncasecmp, which is
>> optimized to compare two not casefolded strings.  We just modify the
>> filename hash to be case-insensitive, so we know which dirent to look
>> for during lookup.  Finally, we use d_compare/d_hash to leverage the
>> dcache into finding negative dentries.
>
> Yeah, am aware of how ext4 does it, I just wanted it to have basically
> the exact same performance characteristics as as regular lookup.
>
> The utf8 cursor stuff in utf8_strncasecmp is still super expensive
> compared to a straight memcmp in some local benching.
>
>>
>> Sure, if you have both, dirent and dentry->d_name casefolded, then it is
>> just a regular memcmp, but at least you don't have to change the disk
>> format and your implementation becomes simpler.
>>
>
> Given we have the opportunity to have support for this in the dirent
> format for bcachefs, I think it makes sense to take it right now.
>
>>
>>
>>> +It would be possible to disregard the casefold cache for those
>>> cases, but it was
>>> +decided to simply encode the two string lengths in the key to avoid
>>> random
>>> +performance issues if this edgecase was ever hit.
>>> +
>>> +The option settled on was to use a free-bit in d_type to mark a
>>> dirent as having
>>> +a casefold cache, and then treat the first 4 bytes the name block as
>>> lengths.
>>> +You can see this in the `d_cf_name_block` member of union in
>>> `bch_dirent`.
>>> +
>>> +The feature bit was used to allow casefolding support to be enabled
>>> for the majority
>>> +of users, but some allow users who have no need for the feature to
>>> still use bcachefs as
>>> +`CONFIG_UNICODE` can increase the kernel side a significant amount
>>> due to the tables used,
>>> +which may be decider between using bcachefs for eg. embedded platforms.
>>> +
>>> +Other filesystems like ext4 and f2fs have a super-block level option
>>> for casefolding
>>> +encoding, but bcachefs currently does not provide this. ext4 and
>>> f2fs do not expose
>>> +any encodings than a single UTF-8 version. When future encodings are
>>> desirable,
>>> +they will be added trivially using the opts mechanism.
>>> +
>>> diff --git a/fs/bcachefs/bcachefs.h b/fs/bcachefs/bcachefs.h
>>> index 30b3d7b9f9dc..0e1facdc7876 100644
>>> --- a/fs/bcachefs/bcachefs.h
>>> +++ b/fs/bcachefs/bcachefs.h
>>> @@ -202,6 +202,7 @@
>>>   #include <linux/types.h>
>>>   #include <linux/workqueue.h>
>>>   #include <linux/zstd.h>
>>> +#include <linux/unicode.h>
>>>   #include "bcachefs_format.h"
>>>   #include "errcode.h"
>>> @@ -657,6 +658,8 @@ enum bch_write_ref {
>>>       BCH_WRITE_REF_NR,
>>>   };
>>> +#define BCH_FS_DEFAULT_UTF8_ENCODING UNICODE_AGE(12, 1, 0)
>>> +
>>>   struct bch_fs {
>>>       struct closure        cl;
>>> @@ -723,6 +726,9 @@ struct bch_fs {
>>>           u64        compat;
>>>       }            sb;
>>> +#if IS_ENABLED(CONFIG_UNICODE)
>>> +    struct unicode_map     *cf_encoding;
>>> +#endif
>>
>> This goes in struct super_block.
>
> The code in libfs.c that uses the s_encoding in the super_block is never
> used for bcachefs as it defines its own inode_operations and doesn't use
> any of the libfs common code for lookups/hashes there (ie. the
> dentry_operations).
>
> One thing we wanted to do down the line was to use the bcachefs options
> system to be able to pick the encoding on a per-inode basis.
>
> Currently I am storing it in the struct bch_fs as currently there is no
> need for other encodings right now and it is convenient, so there can
> only be one -- but that could change at some point with an opt attached
> to the inode.
>
> I am happy to bung it in the vfs super_block for now though -- but I
> need to look at how that all works out with mounting and the multiple
> drives situation. Just be aware that at some point, it will likely be
> moved back again to our code.
>
>>
>>
>>> @@ -13,8 +13,39 @@
>>>   #include <linux/dcache.h>
>>> -static inline unsigned dirent_val_u64s(unsigned len)
>>> +static inline int bch2_casefold(struct btree_trans *trans, const
>>> struct bch_hash_info *info,
>>> +                const struct qstr *str, struct qstr *out_cf)
>>>   {
>>> +#if IS_ENABLED(CONFIG_UNICODE)
>>> +    unsigned char *buf = NULL;
>>> +    int ret;
>>> +
>>> +    *out_cf = (struct qstr) QSTR_INIT(NULL, 0);
>>> +
>>> +    buf = bch2_trans_kmalloc(trans, BCH_NAME_MAX + 1);
>>> +    ret = PTR_ERR_OR_ZERO(buf);
>>> +    if (ret)
>>> +        return ret;
>>> +
>>> +    ret = utf8_casefold(info->cf_encoding, str, buf, BCH_NAME_MAX + 1);
>>> +    if (ret <= 0)
>>> +        return ret;
>>
>> The error path leaks buf.
>
> trans_kmalloc does not need to be freed.
>
>>
>>> @@ -472,6 +600,7 @@ int __bch2_dirent_lookup_trans(struct btree_trans
>>> *trans,
>>>                      const struct qstr *name, subvol_inum *inum,
>>>                      unsigned flags)
>>>   {
>>> +    struct qstr lookup_name = *name;
>>>       struct bkey_s_c k;
>>>       struct bkey_s_c_dirent d;
>>>       u32 snapshot;
>>> @@ -481,8 +610,14 @@ int __bch2_dirent_lookup_trans(struct
>>> btree_trans *trans,
>>>       if (ret)
>>>           return ret;
>>> +    ret = hash_info->cf_encoding
>>> +        ? bch2_casefold(trans, hash_info, name, &lookup_name)
>>> +        : 0;
>>> +    if (ret)
>>> +        return ret;
>>> +
>>>       ret = bch2_hash_lookup(trans, iter, bch2_dirent_hash_desc,
>>> -                   hash_info, dir, name, flags);
>>> +                   hash_info, dir, &lookup_name, flags);
>>>       if (ret)
>>>           return ret;
>>
>>
>> (Skipping the bcachefs-specific bits that I'm not qualified to review)
>>
>> I don't get your model for the dcache.  I don't see any handling
>> anywhere in the patch.  Also, I fetched the code and it seems bcachefs
>> will just do d_splice_alias at the end of the lookup. So, when someone
>> lookups FOO, ->lookup will be called and the dentry FOO will be created.
>> Then, when FOo is looked up, the dcache won't find the previous dentry
>> and ->lookup will be called again (perhaps creating another dentry?)
>>
>> There are two ways around it. Rely on the libfs' generic handlers for
>> d_hash/d_compare and soon d_revalidate, or use d_add_ci to search for
>> case-insensitive aliases at lookup time, but then you don't benefit much
>> from the dcache if looking up for different cases.
>
> Thanks for the heads-up on this.
>
> It seems like I may have potentially hit a foot-gun there if we are
> making vfs dentry's for each lookup.
>
> I will investigate and validate that we are doing the right thing here
> for the next revision.
>
> I will not lie, I know veeery little about the vfs or dcache side, so
> huge thanks for pointing this out to me. :)
>
> I had a quick look at what f2fs does here, and it seems like it also
> just does d_splice_alias, but it has the following caveat.
>
> [f2fs code]
> #if IS_ENABLED(CONFIG_UNICODE)
>     if (!inode && IS_CASEFOLDED(dir)) {
>         /* Eventually we want to call d_add_ci(dentry, NULL)
>          * for negative dentries in the encoding case as
>          * well.  For now, prevent the negative dentry
>          * from being cached.
>          */
>         trace_f2fs_lookup_end(dir, dentry, ino, err);
>         return NULL;
>     }
> #endif
>     new = d_splice_alias(inode, dentry);
>
> I won't even pretend that I understand what a negative dentry is right
> now... :D

I am guessing we probably want something like:

bch2_dirent_lookup -> returns feedback to a `struct qstr real_name` with
the actual name if it was not identical to the dentry lookup name.

if (real_name.len) {
d_add_ci(dentry, vinode, &real_name);
return dentry;
} else {
return d_splice_alias(vinode, dentry);
}

Is my line of thinking correct here?

- Joshie 🐸✨

>
>>
>>
>>> @@ -54,6 +54,28 @@ static int bch2_inode_flags_set(struct btree_trans
>>> *trans,
>>>           (newflags & (BCH_INODE_NODUMP|BCH_INODE_NOATIME)) != newflags)
>>>           return -EINVAL;
>>> +    if ((newflags ^ oldflags) & BCH_INODE_CASEFOLDED) {
>>> +#if IS_ENABLED(CONFIG_UNICODE)
>>> +        int ret = 0;
>>> +        /* Not supported on individual files. */
>>> +        if (!S_ISDIR(bi->bi_mode))
>>> +            return -EOPNOTSUPP;
>>> +
>>> +        /*
>>> +         * Make sure the dir is empty, as otherwise we'd need to
>>> +         * rehash everything and update the dirent keys.
>>> +         */
>>> +        ret = bch2_empty_dir_trans(trans, inode_inum(inode));
>>> +        if (ret < 0)
>>> +            return ret;
>>> +
>>> +        bch2_check_set_feature(c, BCH_FEATURE_casefolding);
>>
>> fwiw, we use _CASEFOLD in other filesystems, not _casefolding.
>
> bcachefs features are always lowercase, but I can change the name of it
> to _casefold.
>
> - Joshie 🐸✨
>
>>
>> Thanks,
>>
>