Message-Id: <E33408BD-68CC-49E4-9B32-EC06DB057509@dilger.ca>
Date:   Fri, 4 Nov 2016 10:14:03 -0600
From:   Andreas Dilger <adilger@...ger.ca>
To:     Theodore Ts'o <tytso@....edu>
Cc:     Ext4 Developers List <linux-ext4@...r.kernel.org>, guy@...ux.com,
        jra@...gle.com, drosen@...gle.com
Subject: Re: [RFC] A proposal for adding case insensitive lookups to ext4

On Nov 3, 2016, at 11:28 AM, Theodore Ts'o <tytso@....edu> wrote:
> 
> HTML version (which will get updated in response to comments):
> 
>     https://thunk.org/tytso/casei-fs.html
> 
> 
> # A proposal for adding case insensitive lookups to ext4
> 
> ## Theodore Ts'o
> ## Version 0.10
> 
> ### Introduction
> 
> Over the years there has been a desire to add case insensitive lookups
> to ext 2/3/4.  The reason why this hasn't happened is doing it right
> is hard.  Unfortunately, the workarounds that people have been using
> in the absense of first class support for case insensitive lookups are
> slow, and evade all of the problems that make this problem hard
> anyway.
> 
> Hence, I think it's worthwhile to outline what could be done to allow
> ext4 to support case insensitive that would be more efficient and less
> hacky than some other solutions (e.g., slow FUSE file systems and
> hacky wrapfs-based solutions that are subject to crashes when run
> under fsstress).
> 
> This proposal does not make any on-disk format changes, but rather
> adds a mount option which causes lookups to be case insensitive, while
> case would be preserved in the directory entries when they are created
> and returned via readdir().
> 
> ### Changes to be made to ext4
> 
> 1.  If case-insensitivity is enabled, override the default dcache hash
> and compare operations to ones that are case insensitive in ext4's
> dcache_operations structure.
> 
> 2.  In ext4_lookup(), if case insensitivity is enabled, and the
> directory lookup does not succeed, fall back to a linear search of the
> directory using using a case insensitive compare.  (This is slow, but
> it's faster compared to doing this in userspace).

Does it make sense to flag directories with whether entries are inserted
with the case-insensitive hash?  That allows the common case of having
case insensitivity always enabled or disabled working optimally.  Falling
back to linear search for every negative lookup would be prohibitive for
large directories.

Depending on the filename length and the size of the directory, it may
still be faster to do 2^name_length lookups with the different case
combinations than a full linear search for each lookup (i.e. when
(1 << name_length < dir_blocks) this repeated lookup is more efficient).
Avoiding linear searching is most important for large directories, and
this becomes worthwhile for increasingly long filenames.

> ### Limitations
> 
> 1.  Like all of the FUSE and in-kernel searches, case insensitivity
> will be implemented using strcasecmp and tolower().  This implies that
> only ASCII case folding will be accepted.  One of the problems of
> using Unicode is that it is not a fixed target.  The case folding
> algorithm is changing as new scripts are added; if someone wants to
> add support for Unicode case folding, it should be added to the
> kernel, with someone assigned with the headache of updating the case
> folding algorithm when new versions of Unicode are issued.

What happens if filenames that collide after case folding are already
existing in the filesystem (e.g. include/uapi/linux/netfilter/xt_*.h
and net/netfilter/xt_*.c are examples of this, and it is a bit sad this
was exposed as part of uapi instead of giving the files useful names)?
Presumably that would prevent one of the filenames from being looked
up, or would it still be able to find both if the correct case was used?

> 2.  If the lookup is done using the filename as it is stored in the
> directory, lookups will be O(1) if the dir_index (htree) ext4 file
> system feature is enabled (which is the default).  It might be
> possible to use a case insensitive hash for the htree feature.
> However, if we do this, then the hash could be broken by changes to
> use Unicode, and if we do implement this with Unicode 8.0.0 support,
> the on-disk format could be broken by future Unicode updates.  So
> adding support for case O(1) lookups when case is not preserved by the
> filename provided by the user is highly unlikely.  (I will note that
> none of the kludges commonly in use support Unicode anyway, so this
> proposal is no worse than those kludges, and my personal approach is
> to exert a very strong Somebody Else's Problem field and hope someone
> else comes up with a solution for us.)

Is this conflating the htree ASCII case folding problem with Unicode?
It would still be possible to insert names into the htree using the hash
of the ASCII-folded names, regardless of what is done for Unicode folding.
Changing the folding method would make the filesystem slow with large
directories (possibly unusable for very large directories), but that could
be fixed by running "e2fsck -fD" on the filesystem to reindex directories.

The filesystem would remain functional even if the folding method changed,
and even without running "e2fsck -fD" it would eventually get better as
new files are added with the right hash and old files are deleted.

Cheers, Andreas

> 3.  Some of the hacky alternatives are also trying to support
> Android's "unique" file permissions scheme.  Support for this is out
> of scope for this proposal, although I do acknowledge we will need to
> come up with a clean way of implementing those permissions-related
> requirements before we have a complete, clean, bug-free, upstreamable
> solution for Android.
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to majordomo@...r.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html


Cheers, Andreas






Download attachment "signature.asc" of type "application/pgp-signature" (834 bytes)

Powered by blists - more mailing lists