[GIT PULL] bcachefs fixes for 6.15-rc4

[GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

There's a story behind the case insensitive directory fixes, and lessons
to be learned.

When I was discussing with the developer who did the implementation, I
noted that fstests should already have tests.

However, it seems I neglected to tell him to make sure the tests
actually run. So, there's a lesson here, and since inadequate testing
keeps coming up, let me state it now:

It is _not_ enough to simply rely on the automated tests.

You have to have eyes on what your code is doing. That means that until
you've thoroughly Familiarized yourself with the code you're working on
and the test suites, you need to look - with your eyes - and confirm
that the tests are doing what you think they're doing and your code is
doing what you think it's doing.

If you're not 100% sure that your code is doing what you think it's
doing, it's your responsibility to dig in and verify - add printks,
tracepoints, counters, whatever it takes.

Automated test infrastructure is a backstop because there are times when
we are all forgetful and miss things.

You have to run your code locally, and look at what it does. I've
provided good tools for this. If you're working on my code, make sure
you're using them.

The following changes since commit 9c32cda43eb78f78c73aee4aa344b777714e259b:

  Linux 6.15-rc3 (2025-04-20 13:43:47 -0700)

are available in the Git repository at:

  git://evilpiepirate.org/bcachefs.git tags/bcachefs-2025-04-24

for you to fetch changes up to d1b0f9aa73fe50ee5276708e33d77c4e7054e555:

  bcachefs: Rework fiemap transaction restart handling (2025-04-24 19:10:29 -0400)

----------------------------------------------------------------
bcachefs fixes for 6.15-rc4

- Case insensitive directories now work
- Ciemap now correctly reports on unwritten pagecache data
- bcachefs tools 1.25.1 was incorrectly picking unaligned bucket sizes;
  fix journal and write path bugs this uncovered

And assorted smaller fixes...

----------------------------------------------------------------
Brian Foster (4):
      bcachefs: drop duplicate fiemap sync flag
      bcachefs: track current fiemap offset in start variable
      bcachefs: refactor fiemap processing into extent helper and struct
      bcachefs: add fiemap delalloc extent detection

Kent Overstreet (20):
      bcachefs: Fix early startup error path
      bcachefs: Fix null ptr deref in bch2_snapshot_tree_oldest_subvol()
      bcachefs: Error ratelimiting is no longer only during fsck
      bcachefs: Stricter checks on "key allowed in this btree"
      bcachefs: Ensure journal space is block size aligned
      bcachefs: Change __journal_entry_close() assert to ERO
      bcachefs: Fix ref leak in write_super()
      bcachefs: bch2_copygc_wakeup()
      bcachefs: Refactor bch2_run_recovery_passes()
      bcachefs: Start copygc, rebalance threads earlier
      bcachefs: Allocator now copes with unaligned buckets
      bcachefs: Implement fileattr_(get|set)
      bcachefs: Casefold is now a regular opts.h option
      bcachefs: Fix casefold lookups
      bcachefs: unlink: casefold d_invalidate
      bcachefs: Print mount opts earlier
      bcachefs: Unit test fixes
      bcachefs: Make btree_iter_peek_prev() assert more precise
      bcachefs: Fix btree_iter_peek_prev() at end of inode
      bcachefs: Rework fiemap transaction restart handling

 fs/bcachefs/alloc_foreground.c |   2 +
 fs/bcachefs/alloc_foreground.h |   4 +-
 fs/bcachefs/bcachefs_format.h  |  81 +++----
 fs/bcachefs/bkey_methods.c     |  24 ++-
 fs/bcachefs/btree_iter.c       |   7 +-
 fs/bcachefs/dirent.c           |  16 +-
 fs/bcachefs/dirent.h           |  15 ++
 fs/bcachefs/error.c            |  17 +-
 fs/bcachefs/error.h            |   1 +
 fs/bcachefs/fs-ioctl.c         | 217 -------------------
 fs/bcachefs/fs-ioctl.h         |  75 -------
 fs/bcachefs/fs.c               | 469 ++++++++++++++++++++++++++++++++++-------
 fs/bcachefs/inode.h            |   8 +
 fs/bcachefs/inode_format.h     |   9 +-
 fs/bcachefs/journal.c          |  36 +++-
 fs/bcachefs/journal.h          |   7 +-
 fs/bcachefs/journal_reclaim.c  |   5 +-
 fs/bcachefs/movinggc.c         |   7 +
 fs/bcachefs/movinggc.h         |   9 +
 fs/bcachefs/namei.c            |   4 -
 fs/bcachefs/opts.h             |   5 +
 fs/bcachefs/rebalance.c        |  11 +-
 fs/bcachefs/rebalance.h        |   2 +-
 fs/bcachefs/recovery.c         |  10 +-
 fs/bcachefs/recovery_passes.c  |  70 +++---
 fs/bcachefs/snapshot.c         |   2 +-
 fs/bcachefs/str_hash.h         |   5 +-
 fs/bcachefs/super-io.c         |   3 +-
 fs/bcachefs/super.c            | 150 ++++++-------
 fs/bcachefs/sysfs.c            |   7 +-
 fs/bcachefs/tests.c            |   4 +
 fs/bcachefs/util.h             |  38 ++++
 32 files changed, 735 insertions(+), 585 deletions(-)

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Linus Torvalds]

On Thu, 24 Apr 2025 at 19:46, Kent Overstreet <kent.overstreet@linux.dev> wrote:
>
> There's a story behind the case insensitive directory fixes, and lessons
> to be learned.

No.

The only lesson to be learned is that filesystem people never learn.

Case-insensitive names are horribly wrong, and you shouldn't have done
them at all. The problem wasn't the lack of testing, the problem was
implementing it in the first place.

The problem is then compounded by "trying to do it right", and in the
process doing it horrible wrong indeed, because "right" doesn't exist,
but trying to will make random bytes have very magical meaning.

And btw, the tests are all completely broken anyway. Last I saw, they
didn't actually test for all the really interesting cases - the ones
that cause security issues in user land.

Security issues like "user space checked that the filename didn't
match some security-sensitive pattern". And then the shit-for-brains
filesystem ends up matching that pattern *anyway*, because the people
who do case insensitivity *INVARIABLY* do things like ignore
non-printing characters, so now "case insensitive" also means
"insensitive to other things too".

For examples of this, see commits

  5c26d2f1d3f5 ("unicode: Don't special case ignorable code points")

and

  231825b2e1ff ("Revert "unicode: Don't special case ignorable code points"")

and cry.

Hint: ❤ and ❤️ are two unicode characters that differ only in
ignorable code points. And guess what? The cray-cray incompetent
people who want those two to compare the same will then also have
other random - and perhaps security-sensitive - files compare the
same, just because they have ignorable code points in them.

So now every single user mode program that checks that they don't
touch special paths is basically open to being fooled into doing
things they explicitly checked they shouldn't be doing. And no, that
isn't something unusual or odd. *Lots* of programs do exactly that.

Dammit. Case sensitivity is a BUG. The fact that filesystem people
*still* think it's a feature, I cannot understand. It's like they
revere the old FAT filesystem _so_ much that they have to recreate it
- badly.

              Linus

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Thu, Apr 24, 2025 at 09:20:53PM -0700, Linus Torvalds wrote:
> On Thu, 24 Apr 2025 at 19:46, Kent Overstreet <kent.overstreet@linux.dev> wrote:
> >
> > There's a story behind the case insensitive directory fixes, and lessons
> > to be learned.
> 
> No.
> 
> The only lesson to be learned is that filesystem people never learn.
> 
> Case-insensitive names are horribly wrong, and you shouldn't have done
> them at all. The problem wasn't the lack of testing, the problem was
> implementing it in the first place.

While I agree with you in _principle_, on this specific subject -

This is all irrelevant given that the purpose of the operating system
and the filesystem is to support users and the applications they want to
run.

And the hacks for doing this in userspace don't work.

And the attitude of "I hate this, so I'm going to partition this off as
much as I can and spend as little time as I can on this" has all made
this even worse - the dcache stuff is all half baked. Stroll through the
ext4 and xfs code and find all the comments to the effect of "yeah, we
should really do this better _eventually_"...

And the security issues aren't even case insensitivy, it's just unicode.
But that ship has sailed too...

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Fri, Apr 25, 2025 at 12:52:05AM -0400, Kent Overstreet wrote:
> On Thu, Apr 24, 2025 at 09:20:53PM -0700, Linus Torvalds wrote:
> > On Thu, 24 Apr 2025 at 19:46, Kent Overstreet <kent.overstreet@linux.dev> wrote:
> > >
> > > There's a story behind the case insensitive directory fixes, and lessons
> > > to be learned.
> > 
> > No.
> > 
> > The only lesson to be learned is that filesystem people never learn.
> > 
> > Case-insensitive names are horribly wrong, and you shouldn't have done
> > them at all. The problem wasn't the lack of testing, the problem was
> > implementing it in the first place.
> 
> While I agree with you in _principle_, on this specific subject -
> 
> This is all irrelevant given that the purpose of the operating system
> and the filesystem is to support users and the applications they want to
> run.
> 
> And the hacks for doing this in userspace don't work.
> 
> And the attitude of "I hate this, so I'm going to partition this off as
> much as I can and spend as little time as I can on this" has all made
> this even worse - the dcache stuff is all half baked. Stroll through the
> ext4 and xfs code and find all the comments to the effect of "yeah, we
> should really do this better _eventually_"...

And you can always tell when this attitude comes up, because you end up
with code that's 10 times more gross than it has to be.

Quotas are the other big one. You can tell no one wants to be working on
that code, and as a result it's just horrific.

Quotas aren't my favorite thing, but if a job needs to be done, do it
right.

And we've got an established need for both quotas and case insensitive
directories.

So I don't want any whining about "bad" they are. I want them to work,
and I want the code to be clean and maintainable, and not make my eyes
bleed when I have to go and debug it.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Linus Torvalds]

On Thu, 24 Apr 2025 at 21:52, Kent Overstreet <kent.overstreet@linux.dev> wrote:
>
> And the attitude of "I hate this, so I'm going to partition this off as
> much as I can and spend as little time as I can on this" has all made
> this even worse - the dcache stuff is all half baked.

No. The dcache side is *correct*.

The thing is, you absolutely cannot make the case-insensitive lookup
be the fast case.

So it's partitioned off not because people don't want to deal with it
(which also admittedly _is_ true), but because partitioning off is a
firewall against the code generation garbage case that simply *cannot*
be done well and allows the proper cases to be properly optimized.

Now, if filesystem people were to see the light, and have a proper and
well-designed case insensitivity, that might change. But I've never
seen even a *whiff* of that. I have only seen bad code that
understands neither how UTF-8 works, nor how unicode works (or rather:
how unicode does *not* work - code that uses the unicode comparison
functions without a deeper understanding of what the implications
are).

Your comments blaming unicode is only another sign of that.

Because no, the problem with bad case folding isn't in unicode.

It's in filesystem people who didn't understand - and still don't,
after decades - that you MUST NOT just blindly follow some external
case folding table that you don't understand and that can change over
time.

The "change overr time" part is particularly vexing to me, because it
breaks one of the fundamental rules that unicode was *supposed* to
fix: no locale garbage.

And the moment you think you need "unicode versioning", you have
basically now created a locale with a different name, and you MISSED
THE WHOLE %^$*ING POINT OF IT ALL.

And yes, *those* problems come from people thinking it's "somebody
else's problem that they solved for me" without actually understanding
that no, that wasn't the case at all. Many of the unicode rules were
about *glyphs*, and simply cannot be used for filesystems or equality
comparisons.

Which isn't to say that Unicode doesn't have problems, but the real
problem is then using it without understanding the problems.

So the real issue with unicode is that it's very complicated, and it
tried to solve many different problems, and that then resulted in
people not understanding that not all of it was appropriate for
*their* use.

Part of it is the "CS disease": thinking that a generic solution is
always "better". Not so. Being overrly generic is often much much
worse than having a targeted solution to a intentionally limited
problem.

   "Everything Should Be Made as Simple as Possible, But Not Simpler".

and involving unicode in case folding is antithetical to that
fundamental concept.

What I personally strongly feel should have been done is to just limit
case folding knowingly to a very strict subset, and people should have
said "we're being backwards compatible with FAT" or something like
that. Instead of extending the problem space to the point where it
becomes a huge problem, re-introduces "locales" in a different guise,
and creates security issues because people don't understand just *how*
big they made the problem space.

Oh well. Rant over.

                Linus

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Matthew Wilcox]

On Fri, Apr 25, 2025 at 09:35:27AM -0700, Linus Torvalds wrote:
> Now, if filesystem people were to see the light, and have a proper and
> well-designed case insensitivity, that might change. But I've never
> seen even a *whiff* of that. I have only seen bad code that
> understands neither how UTF-8 works, nor how unicode works (or rather:
> how unicode does *not* work - code that uses the unicode comparison
> functions without a deeper understanding of what the implications
> are).
> 
> Your comments blaming unicode is only another sign of that.
> 
> Because no, the problem with bad case folding isn't in unicode.
> 
> It's in filesystem people who didn't understand - and still don't,
> after decades - that you MUST NOT just blindly follow some external
> case folding table that you don't understand and that can change over
> time.

I think this is something that NTFS actually got right.  Each filesystem
carries with it a 128KiB table that maps each codepoint to its
case-insensitive equivalent.  So there's no ambiguity about "which
version of the unicode standard are we using", "Does the user care
about Turkish language rules?", "Is Aachen a German or Danish word?".
The sysadmin specified all that when they created the filesystem, and it
doesn't matter what the Unicode standard changes in the future; if you
need to change how the filesystem sorts things, you can update the table.

It's not the perfect solution, but it might be the least-bad one I've
seen.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Linus Torvalds]

On Fri, 25 Apr 2025 at 12:40, Matthew Wilcox <willy@infradead.org> wrote:
>
> I think this is something that NTFS actually got right.  Each filesystem
> carries with it a 128KiB table that maps each codepoint to its
> case-insensitive equivalent.

I agree that that is indeed a technically correct way to deal with
case sensitivity at least from a filesystem standpoint.

It does have some usability issues - exactly because of that "fixed at
filesystem creation time" - but since in *practice* nobody actually
cares about the odd cases, that isn't really much of a real issue.

And the fixed translation table means that it at least gets versioning
right, and you hopefully filled the table up sanely and don't end up
with the crazy cases (ie the nonprinting characters etc) so hopefully
it contains only the completely unambiguous stuff.

That said, I really suspect that in practice, folding even just the
7-bit ASCII subset would have been ok and would have obviated even
that table. And I say that as somebody who grew up in an environment
that used a bigger character set than that.

Of course, the NTFS stuff came about because FAT had code pages for
just the 8-bit cases - and people used them, and that then caused odd
issues when moving data around.

Again - 8-bit tables were entirely sufficient in practice but actually
caused more problems than not doing it at all would have. And then
people go "we switched to 16-bit wide characters, so we need to expand
on the code table too".

Which is obviously exactly how you end up with that 128kB table.

But you have to ask yourself: do you think that the people who made
the incredibly bad choice to use a fixed 16-bit wide character set -
which caused literally decades of trouble in Windows, and still shows
up today - then made the perfect choice when dealing with case
folding? Yeah, no.

Still, I very much agree it was a better choice than "let's call
random unicode routines we don't really appreciate the complexity of".

            Linus

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Fri, Apr 25, 2025 at 08:40:35PM +0100, Matthew Wilcox wrote:
> On Fri, Apr 25, 2025 at 09:35:27AM -0700, Linus Torvalds wrote:
> > Now, if filesystem people were to see the light, and have a proper and
> > well-designed case insensitivity, that might change. But I've never
> > seen even a *whiff* of that. I have only seen bad code that
> > understands neither how UTF-8 works, nor how unicode works (or rather:
> > how unicode does *not* work - code that uses the unicode comparison
> > functions without a deeper understanding of what the implications
> > are).
> > 
> > Your comments blaming unicode is only another sign of that.
> > 
> > Because no, the problem with bad case folding isn't in unicode.
> > 
> > It's in filesystem people who didn't understand - and still don't,
> > after decades - that you MUST NOT just blindly follow some external
> > case folding table that you don't understand and that can change over
> > time.
> 
> I think this is something that NTFS actually got right.  Each filesystem
> carries with it a 128KiB table that maps each codepoint to its
> case-insensitive equivalent.  So there's no ambiguity about "which
> version of the unicode standard are we using", "Does the user care
> about Turkish language rules?", "Is Aachen a German or Danish word?".
> The sysadmin specified all that when they created the filesystem, and it
> doesn't matter what the Unicode standard changes in the future; if you
> need to change how the filesystem sorts things, you can update the table.
> 
> It's not the perfect solution, but it might be the least-bad one I've
> seen.

The thing is, that's exactly what we're doing. ext4 and bcachefs both
refer to a specific revision of the folding rules: for ext4 it's
specified in the superblock, for bcachefs it's hardcoded for the moment.

I don't think this is the ideal approach, though.

That means the folding rules are "whatever you got when you mkfs'd".
Think about what that means if you've got a fleet of machines, of
different ages, but all updated in sync: that's a really annoying way
for gremlins of the "why does this machine act differently" variety to
creep in.

What I'd prefer is for the unicode folding rules to be transparently and
automatically updated when the kernel is updated, so that behaviour
stays in sync. That would behave more the way users would expect.

But I only gave this real thought just over the past few days, and doing
this safely and correctly would require some fairly significant changes
to the way casefolding works.

We'd have to ensure that lookups via the case sensitive name always
works, even if the casefolding table the dirent was created with give
different results that the currently active casefolding table.

That would require storing two different "dirents" for each real dirent,
one normalized and one un-normalized, because we'd have to do an
un-normalized lookup if the normalized lookup fails (and vice versa).
Which should be completely fine from a performance POV, assuming we have
working negative dentries.

But, if the unicode folding rules are stable enough (and one would hope
they are), hopefully all this is a non-issue.

I'd have to gather more input from users of casefolding on other
filesystems before saying what our long term plans (if any) will be.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Eric Biggers]

On Sun, Apr 27, 2025 at 08:55:30PM -0400, Kent Overstreet wrote:
> On Fri, Apr 25, 2025 at 08:40:35PM +0100, Matthew Wilcox wrote:
> > On Fri, Apr 25, 2025 at 09:35:27AM -0700, Linus Torvalds wrote:
> > > Now, if filesystem people were to see the light, and have a proper and
> > > well-designed case insensitivity, that might change. But I've never
> > > seen even a *whiff* of that. I have only seen bad code that
> > > understands neither how UTF-8 works, nor how unicode works (or rather:
> > > how unicode does *not* work - code that uses the unicode comparison
> > > functions without a deeper understanding of what the implications
> > > are).
> > > 
> > > Your comments blaming unicode is only another sign of that.
> > > 
> > > Because no, the problem with bad case folding isn't in unicode.
> > > 
> > > It's in filesystem people who didn't understand - and still don't,
> > > after decades - that you MUST NOT just blindly follow some external
> > > case folding table that you don't understand and that can change over
> > > time.
> > 
> > I think this is something that NTFS actually got right.  Each filesystem
> > carries with it a 128KiB table that maps each codepoint to its
> > case-insensitive equivalent.  So there's no ambiguity about "which
> > version of the unicode standard are we using", "Does the user care
> > about Turkish language rules?", "Is Aachen a German or Danish word?".
> > The sysadmin specified all that when they created the filesystem, and it
> > doesn't matter what the Unicode standard changes in the future; if you
> > need to change how the filesystem sorts things, you can update the table.
> > 
> > It's not the perfect solution, but it might be the least-bad one I've
> > seen.
> 
> The thing is, that's exactly what we're doing. ext4 and bcachefs both
> refer to a specific revision of the folding rules: for ext4 it's
> specified in the superblock, for bcachefs it's hardcoded for the moment.
> 
> I don't think this is the ideal approach, though.
> 
> That means the folding rules are "whatever you got when you mkfs'd".
> Think about what that means if you've got a fleet of machines, of
> different ages, but all updated in sync: that's a really annoying way
> for gremlins of the "why does this machine act differently" variety to
> creep in.
> 
> What I'd prefer is for the unicode folding rules to be transparently and
> automatically updated when the kernel is updated, so that behaviour
> stays in sync. That would behave more the way users would expect.
> 
> But I only gave this real thought just over the past few days, and doing
> this safely and correctly would require some fairly significant changes
> to the way casefolding works.
> 
> We'd have to ensure that lookups via the case sensitive name always
> works, even if the casefolding table the dirent was created with give
> different results that the currently active casefolding table.
> 
> That would require storing two different "dirents" for each real dirent,
> one normalized and one un-normalized, because we'd have to do an
> un-normalized lookup if the normalized lookup fails (and vice versa).
> Which should be completely fine from a performance POV, assuming we have
> working negative dentries.
> 
> But, if the unicode folding rules are stable enough (and one would hope
> they are), hopefully all this is a non-issue.
> 
> I'd have to gather more input from users of casefolding on other
> filesystems before saying what our long term plans (if any) will be.

Wouldn't lookups via the case-sensitive name keep working even if the
case-insensitivity rules change?  It's lookups via a case-insensitive name that
could start producing different results.  Applications can depend on
case-insensitive lookups being done in a certain way, so changing the
case-insensitivity rules can be risky.

Regardless, the long-term plan for the case-insensitivity rules should be to
deprecate the current set of rules, which does Unicode normalization which is
way overkill.  It should be replaced with a simple version of case-insensitivity
that matches what FAT does.  And *possibly* also a version that matches what
NTFS does (a u16 upcase_table[65536] indexed by UTF-16 coding units), if someone
really needs that.

As far as I know, that was all that was really needed in the first place.

People misunderstood the problem as being about language support, rather than
about compatibility with legacy filesystems.  And as a result they incorrectly
decided they should do Unicode normalization, which is way too complex and has
all sorts of weird properties.

- Eric

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Sun, Apr 27, 2025 at 06:30:59PM -0700, Eric Biggers wrote:
> On Sun, Apr 27, 2025 at 08:55:30PM -0400, Kent Overstreet wrote:
> > The thing is, that's exactly what we're doing. ext4 and bcachefs both
> > refer to a specific revision of the folding rules: for ext4 it's
> > specified in the superblock, for bcachefs it's hardcoded for the moment.
> > 
> > I don't think this is the ideal approach, though.
> > 
> > That means the folding rules are "whatever you got when you mkfs'd".
> > Think about what that means if you've got a fleet of machines, of
> > different ages, but all updated in sync: that's a really annoying way
> > for gremlins of the "why does this machine act differently" variety to
> > creep in.
> > 
> > What I'd prefer is for the unicode folding rules to be transparently and
> > automatically updated when the kernel is updated, so that behaviour
> > stays in sync. That would behave more the way users would expect.
> > 
> > But I only gave this real thought just over the past few days, and doing
> > this safely and correctly would require some fairly significant changes
> > to the way casefolding works.
> > 
> > We'd have to ensure that lookups via the case sensitive name always
> > works, even if the casefolding table the dirent was created with give
> > different results that the currently active casefolding table.
> > 
> > That would require storing two different "dirents" for each real dirent,
> > one normalized and one un-normalized, because we'd have to do an
> > un-normalized lookup if the normalized lookup fails (and vice versa).
> > Which should be completely fine from a performance POV, assuming we have
> > working negative dentries.
> > 
> > But, if the unicode folding rules are stable enough (and one would hope
> > they are), hopefully all this is a non-issue.
> > 
> > I'd have to gather more input from users of casefolding on other
> > filesystems before saying what our long term plans (if any) will be.
> 
> Wouldn't lookups via the case-sensitive name keep working even if the
> case-insensitivity rules change?  It's lookups via a case-insensitive name that
> could start producing different results.  Applications can depend on
> case-insensitive lookups being done in a certain way, so changing the
> case-insensitivity rules can be risky.

No, because right now on a case-insensitive filesystem we _only_ do the
lookup with the normalized name.

> Regardless, the long-term plan for the case-insensitivity rules should be to
> deprecate the current set of rules, which does Unicode normalization which is
> way overkill.  It should be replaced with a simple version of case-insensitivity
> that matches what FAT does.  And *possibly* also a version that matches what
> NTFS does (a u16 upcase_table[65536] indexed by UTF-16 coding units), if someone
> really needs that.
> 
> As far as I know, that was all that was really needed in the first place.
> 
> People misunderstood the problem as being about language support, rather than
> about compatibility with legacy filesystems.  And as a result they incorrectly
> decided they should do Unicode normalization, which is way too complex and has
> all sorts of weird properties.

Believe me, I do see the appeal of that.

One of the things I should really float with e.g. Valve is the
possibility of providing tooling/auditing to make it easy to fix
userspace code that's doing lookups that only work with casefolding.

And, another thing I'd like is a way to make casefolding per-process, so
that it could be opt-in for the programs that need it - so that new code
isn't accidentally depending on casefolding.

That's something we really should have, anyways.

But, as much as we might hate it, casefolding is something that users
like and do expect in other contexts, so if casefolding is going to
exist (as more than just a compatibility thing for legacy code) - it
really ought to be unicode, and utf8 really has won at this point.

Mainly though, it's not a decision I care to revisit, I intend to stick
with casefolding that's compatible with how it's done on our other
filesystems where it's widely used.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Autumn Ashton]

On 4/28/25 2:43 AM, Kent Overstreet wrote:
> On Sun, Apr 27, 2025 at 06:30:59PM -0700, Eric Biggers wrote:
>> On Sun, Apr 27, 2025 at 08:55:30PM -0400, Kent Overstreet wrote:
>>> The thing is, that's exactly what we're doing. ext4 and bcachefs both
>>> refer to a specific revision of the folding rules: for ext4 it's
>>> specified in the superblock, for bcachefs it's hardcoded for the moment.
>>>
>>> I don't think this is the ideal approach, though.
>>>
>>> That means the folding rules are "whatever you got when you mkfs'd".
>>> Think about what that means if you've got a fleet of machines, of
>>> different ages, but all updated in sync: that's a really annoying way
>>> for gremlins of the "why does this machine act differently" variety to
>>> creep in.
>>>
>>> What I'd prefer is for the unicode folding rules to be transparently and
>>> automatically updated when the kernel is updated, so that behaviour
>>> stays in sync. That would behave more the way users would expect.
>>>
>>> But I only gave this real thought just over the past few days, and doing
>>> this safely and correctly would require some fairly significant changes
>>> to the way casefolding works.
>>>
>>> We'd have to ensure that lookups via the case sensitive name always
>>> works, even if the casefolding table the dirent was created with give
>>> different results that the currently active casefolding table.
>>>
>>> That would require storing two different "dirents" for each real dirent,
>>> one normalized and one un-normalized, because we'd have to do an
>>> un-normalized lookup if the normalized lookup fails (and vice versa).
>>> Which should be completely fine from a performance POV, assuming we have
>>> working negative dentries.
>>>
>>> But, if the unicode folding rules are stable enough (and one would hope
>>> they are), hopefully all this is a non-issue.
>>>
>>> I'd have to gather more input from users of casefolding on other
>>> filesystems before saying what our long term plans (if any) will be.
>>
>> Wouldn't lookups via the case-sensitive name keep working even if the
>> case-insensitivity rules change?  It's lookups via a case-insensitive name that
>> could start producing different results.  Applications can depend on
>> case-insensitive lookups being done in a certain way, so changing the
>> case-insensitivity rules can be risky.
> 
> No, because right now on a case-insensitive filesystem we _only_ do the
> lookup with the normalized name.
> 
>> Regardless, the long-term plan for the case-insensitivity rules should be to
>> deprecate the current set of rules, which does Unicode normalization which is
>> way overkill.  It should be replaced with a simple version of case-insensitivity
>> that matches what FAT does.  And *possibly* also a version that matches what
>> NTFS does (a u16 upcase_table[65536] indexed by UTF-16 coding units), if someone
>> really needs that.
>>
>> As far as I know, that was all that was really needed in the first place.
>>
>> People misunderstood the problem as being about language support, rather than
>> about compatibility with legacy filesystems.  And as a result they incorrectly
>> decided they should do Unicode normalization, which is way too complex and has
>> all sorts of weird properties.
> 
> Believe me, I do see the appeal of that.
> 
> One of the things I should really float with e.g. Valve is the
> possibility of providing tooling/auditing to make it easy to fix
> userspace code that's doing lookups that only work with casefolding.

This is not really about fixing userspace code that expects casefolding, 
or providing some form of stopgap there.

The main need there is Proton/Wine, which is a compat layer for Windows 
apps, which needs to pretend it's on NTFS and everything there expects 
casefolding to work.

No auditing/tooling required, we know the problem. It is unavoidable.

I agree with the calling about Unicode normalization being odd though, 
when I was implementing casefolding for bcachefs, I immediately thought 
it was a huge hammer to do full normalization for the intended purpose, 
and not just a big table...

FWIR, there is actually two forms of casefolding in unicode, full 
casefolding, C+F, (eg. ß->ss) and the simpler one, simple casefolding 
(C+S), where lengths don't change and it's glyph for glyph.

- Autumn ✨

> 
> And, another thing I'd like is a way to make casefolding per-process, so
> that it could be opt-in for the programs that need it - so that new code
> isn't accidentally depending on casefolding.
> 
> That's something we really should have, anyways.
> 
> But, as much as we might hate it, casefolding is something that users
> like and do expect in other contexts, so if casefolding is going to
> exist (as more than just a compatibility thing for legacy code) - it
> really ought to be unicode, and utf8 really has won at this point.
> 
> Mainly though, it's not a decision I care to revisit, I intend to stick
> with casefolding that's compatible with how it's done on our other
> filesystems where it's widely used.
> 

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Mon, Apr 28, 2025 at 03:05:19AM +0100, Autumn Ashton wrote:
> 
> 
> On 4/28/25 2:43 AM, Kent Overstreet wrote:
> > On Sun, Apr 27, 2025 at 06:30:59PM -0700, Eric Biggers wrote:
> > > On Sun, Apr 27, 2025 at 08:55:30PM -0400, Kent Overstreet wrote:
> > > > The thing is, that's exactly what we're doing. ext4 and bcachefs both
> > > > refer to a specific revision of the folding rules: for ext4 it's
> > > > specified in the superblock, for bcachefs it's hardcoded for the moment.
> > > > 
> > > > I don't think this is the ideal approach, though.
> > > > 
> > > > That means the folding rules are "whatever you got when you mkfs'd".
> > > > Think about what that means if you've got a fleet of machines, of
> > > > different ages, but all updated in sync: that's a really annoying way
> > > > for gremlins of the "why does this machine act differently" variety to
> > > > creep in.
> > > > 
> > > > What I'd prefer is for the unicode folding rules to be transparently and
> > > > automatically updated when the kernel is updated, so that behaviour
> > > > stays in sync. That would behave more the way users would expect.
> > > > 
> > > > But I only gave this real thought just over the past few days, and doing
> > > > this safely and correctly would require some fairly significant changes
> > > > to the way casefolding works.
> > > > 
> > > > We'd have to ensure that lookups via the case sensitive name always
> > > > works, even if the casefolding table the dirent was created with give
> > > > different results that the currently active casefolding table.
> > > > 
> > > > That would require storing two different "dirents" for each real dirent,
> > > > one normalized and one un-normalized, because we'd have to do an
> > > > un-normalized lookup if the normalized lookup fails (and vice versa).
> > > > Which should be completely fine from a performance POV, assuming we have
> > > > working negative dentries.
> > > > 
> > > > But, if the unicode folding rules are stable enough (and one would hope
> > > > they are), hopefully all this is a non-issue.
> > > > 
> > > > I'd have to gather more input from users of casefolding on other
> > > > filesystems before saying what our long term plans (if any) will be.
> > > 
> > > Wouldn't lookups via the case-sensitive name keep working even if the
> > > case-insensitivity rules change?  It's lookups via a case-insensitive name that
> > > could start producing different results.  Applications can depend on
> > > case-insensitive lookups being done in a certain way, so changing the
> > > case-insensitivity rules can be risky.
> > 
> > No, because right now on a case-insensitive filesystem we _only_ do the
> > lookup with the normalized name.
> > 
> > > Regardless, the long-term plan for the case-insensitivity rules should be to
> > > deprecate the current set of rules, which does Unicode normalization which is
> > > way overkill.  It should be replaced with a simple version of case-insensitivity
> > > that matches what FAT does.  And *possibly* also a version that matches what
> > > NTFS does (a u16 upcase_table[65536] indexed by UTF-16 coding units), if someone
> > > really needs that.
> > > 
> > > As far as I know, that was all that was really needed in the first place.
> > > 
> > > People misunderstood the problem as being about language support, rather than
> > > about compatibility with legacy filesystems.  And as a result they incorrectly
> > > decided they should do Unicode normalization, which is way too complex and has
> > > all sorts of weird properties.
> > 
> > Believe me, I do see the appeal of that.
> > 
> > One of the things I should really float with e.g. Valve is the
> > possibility of providing tooling/auditing to make it easy to fix
> > userspace code that's doing lookups that only work with casefolding.
> 
> This is not really about fixing userspace code that expects casefolding, or
> providing some form of stopgap there.
> 
> The main need there is Proton/Wine, which is a compat layer for Windows
> apps, which needs to pretend it's on NTFS and everything there expects
> casefolding to work.
> 
> No auditing/tooling required, we know the problem. It is unavoidable.

Does this boil all the way up to e.g. savegames?

I was imagining predetermined assets, where the name of the file would
be present in a compiled binary, and it's little more than a search and
replace. But would only work if it's present as a string literal.

> I agree with the calling about Unicode normalization being odd though, when
> I was implementing casefolding for bcachefs, I immediately thought it was a
> huge hammer to do full normalization for the intended purpose, and not just
> a big table...

Samba's historically wanted casefolding, and Windows casefolding is
Unicode (and it's full, not simple - mostly), so I'd expect that was the
other main driver.

I'm sure there's other odd corners besides just Samba where Windows
compatibility comes up, people cook up all kinds of strange things.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Autumn Ashton]

On 4/28/25 3:16 AM, Kent Overstreet wrote:
> On Mon, Apr 28, 2025 at 03:05:19AM +0100, Autumn Ashton wrote:
>>
>>
>> On 4/28/25 2:43 AM, Kent Overstreet wrote:
>>> On Sun, Apr 27, 2025 at 06:30:59PM -0700, Eric Biggers wrote:
>>>> On Sun, Apr 27, 2025 at 08:55:30PM -0400, Kent Overstreet wrote:
>>>>> The thing is, that's exactly what we're doing. ext4 and bcachefs both
>>>>> refer to a specific revision of the folding rules: for ext4 it's
>>>>> specified in the superblock, for bcachefs it's hardcoded for the moment.
>>>>>
>>>>> I don't think this is the ideal approach, though.
>>>>>
>>>>> That means the folding rules are "whatever you got when you mkfs'd".
>>>>> Think about what that means if you've got a fleet of machines, of
>>>>> different ages, but all updated in sync: that's a really annoying way
>>>>> for gremlins of the "why does this machine act differently" variety to
>>>>> creep in.
>>>>>
>>>>> What I'd prefer is for the unicode folding rules to be transparently and
>>>>> automatically updated when the kernel is updated, so that behaviour
>>>>> stays in sync. That would behave more the way users would expect.
>>>>>
>>>>> But I only gave this real thought just over the past few days, and doing
>>>>> this safely and correctly would require some fairly significant changes
>>>>> to the way casefolding works.
>>>>>
>>>>> We'd have to ensure that lookups via the case sensitive name always
>>>>> works, even if the casefolding table the dirent was created with give
>>>>> different results that the currently active casefolding table.
>>>>>
>>>>> That would require storing two different "dirents" for each real dirent,
>>>>> one normalized and one un-normalized, because we'd have to do an
>>>>> un-normalized lookup if the normalized lookup fails (and vice versa).
>>>>> Which should be completely fine from a performance POV, assuming we have
>>>>> working negative dentries.
>>>>>
>>>>> But, if the unicode folding rules are stable enough (and one would hope
>>>>> they are), hopefully all this is a non-issue.
>>>>>
>>>>> I'd have to gather more input from users of casefolding on other
>>>>> filesystems before saying what our long term plans (if any) will be.
>>>>
>>>> Wouldn't lookups via the case-sensitive name keep working even if the
>>>> case-insensitivity rules change?  It's lookups via a case-insensitive name that
>>>> could start producing different results.  Applications can depend on
>>>> case-insensitive lookups being done in a certain way, so changing the
>>>> case-insensitivity rules can be risky.
>>>
>>> No, because right now on a case-insensitive filesystem we _only_ do the
>>> lookup with the normalized name.
>>>
>>>> Regardless, the long-term plan for the case-insensitivity rules should be to
>>>> deprecate the current set of rules, which does Unicode normalization which is
>>>> way overkill.  It should be replaced with a simple version of case-insensitivity
>>>> that matches what FAT does.  And *possibly* also a version that matches what
>>>> NTFS does (a u16 upcase_table[65536] indexed by UTF-16 coding units), if someone
>>>> really needs that.
>>>>
>>>> As far as I know, that was all that was really needed in the first place.
>>>>
>>>> People misunderstood the problem as being about language support, rather than
>>>> about compatibility with legacy filesystems.  And as a result they incorrectly
>>>> decided they should do Unicode normalization, which is way too complex and has
>>>> all sorts of weird properties.
>>>
>>> Believe me, I do see the appeal of that.
>>>
>>> One of the things I should really float with e.g. Valve is the
>>> possibility of providing tooling/auditing to make it easy to fix
>>> userspace code that's doing lookups that only work with casefolding.
>>
>> This is not really about fixing userspace code that expects casefolding, or
>> providing some form of stopgap there.
>>
>> The main need there is Proton/Wine, which is a compat layer for Windows
>> apps, which needs to pretend it's on NTFS and everything there expects
>> casefolding to work.
>>
>> No auditing/tooling required, we know the problem. It is unavoidable.
> 
> Does this boil all the way up to e.g. savegames?

Everything, assets, save games.

You can't just patch the games... Doing that for every game on Steam 
with every way they load games would be impossible, especially with 
modern day obfuscated binaries, and anti-cheat and anti-tamper solutions.

- Autumn ✨

> 
> I was imagining predetermined assets, where the name of the file would
> be present in a compiled binary, and it's little more than a search and
> replace. But would only work if it's present as a string literal.
> 
>> I agree with the calling about Unicode normalization being odd though, when
>> I was implementing casefolding for bcachefs, I immediately thought it was a
>> huge hammer to do full normalization for the intended purpose, and not just
>> a big table...
> 
> Samba's historically wanted casefolding, and Windows casefolding is
> Unicode (and it's full, not simple - mostly), so I'd expect that was the
> other main driver.
> 
> I'm sure there's other odd corners besides just Samba where Windows
> compatibility comes up, people cook up all kinds of strange things.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Eric Biggers]

On Mon, Apr 28, 2025 at 03:05:19AM +0100, Autumn Ashton wrote:
> 
> 
> On 4/28/25 2:43 AM, Kent Overstreet wrote:
> > On Sun, Apr 27, 2025 at 06:30:59PM -0700, Eric Biggers wrote:
> > > On Sun, Apr 27, 2025 at 08:55:30PM -0400, Kent Overstreet wrote:
> > > > The thing is, that's exactly what we're doing. ext4 and bcachefs both
> > > > refer to a specific revision of the folding rules: for ext4 it's
> > > > specified in the superblock, for bcachefs it's hardcoded for the moment.
> > > > 
> > > > I don't think this is the ideal approach, though.
> > > > 
> > > > That means the folding rules are "whatever you got when you mkfs'd".
> > > > Think about what that means if you've got a fleet of machines, of
> > > > different ages, but all updated in sync: that's a really annoying way
> > > > for gremlins of the "why does this machine act differently" variety to
> > > > creep in.
> > > > 
> > > > What I'd prefer is for the unicode folding rules to be transparently and
> > > > automatically updated when the kernel is updated, so that behaviour
> > > > stays in sync. That would behave more the way users would expect.
> > > > 
> > > > But I only gave this real thought just over the past few days, and doing
> > > > this safely and correctly would require some fairly significant changes
> > > > to the way casefolding works.
> > > > 
> > > > We'd have to ensure that lookups via the case sensitive name always
> > > > works, even if the casefolding table the dirent was created with give
> > > > different results that the currently active casefolding table.
> > > > 
> > > > That would require storing two different "dirents" for each real dirent,
> > > > one normalized and one un-normalized, because we'd have to do an
> > > > un-normalized lookup if the normalized lookup fails (and vice versa).
> > > > Which should be completely fine from a performance POV, assuming we have
> > > > working negative dentries.
> > > > 
> > > > But, if the unicode folding rules are stable enough (and one would hope
> > > > they are), hopefully all this is a non-issue.
> > > > 
> > > > I'd have to gather more input from users of casefolding on other
> > > > filesystems before saying what our long term plans (if any) will be.
> > > 
> > > Wouldn't lookups via the case-sensitive name keep working even if the
> > > case-insensitivity rules change?  It's lookups via a case-insensitive name that
> > > could start producing different results.  Applications can depend on
> > > case-insensitive lookups being done in a certain way, so changing the
> > > case-insensitivity rules can be risky.
> > 
> > No, because right now on a case-insensitive filesystem we _only_ do the
> > lookup with the normalized name.
> > 
> > > Regardless, the long-term plan for the case-insensitivity rules should be to
> > > deprecate the current set of rules, which does Unicode normalization which is
> > > way overkill.  It should be replaced with a simple version of case-insensitivity
> > > that matches what FAT does.  And *possibly* also a version that matches what
> > > NTFS does (a u16 upcase_table[65536] indexed by UTF-16 coding units), if someone
> > > really needs that.
> > > 
> > > As far as I know, that was all that was really needed in the first place.
> > > 
> > > People misunderstood the problem as being about language support, rather than
> > > about compatibility with legacy filesystems.  And as a result they incorrectly
> > > decided they should do Unicode normalization, which is way too complex and has
> > > all sorts of weird properties.
> > 
> > Believe me, I do see the appeal of that.
> > 
> > One of the things I should really float with e.g. Valve is the
> > possibility of providing tooling/auditing to make it easy to fix
> > userspace code that's doing lookups that only work with casefolding.
> 
> This is not really about fixing userspace code that expects casefolding, or
> providing some form of stopgap there.
> 
> The main need there is Proton/Wine, which is a compat layer for Windows
> apps, which needs to pretend it's on NTFS and everything there expects
> casefolding to work.
> 
> No auditing/tooling required, we know the problem. It is unavoidable.
> 
> I agree with the calling about Unicode normalization being odd though, when
> I was implementing casefolding for bcachefs, I immediately thought it was a
> huge hammer to do full normalization for the intended purpose, and not just
> a big table...
> 
> FWIR, there is actually two forms of casefolding in unicode, full
> casefolding, C+F, (eg. ß->ss) and the simpler one, simple casefolding (C+S),
> where lengths don't change and it's glyph for glyph.

Yet, ext4 and f2fs's (and now bcachefs's...) "casefolding" is *not* compatible
with NTFS.

Nor is it compatible with FAT (which is what Android needed).

Nor does it actually do Unicode casefolding
(https://www.unicode.org/Public/16.0.0/ucd/CaseFolding.txt), but rather
Unicode normalization which is more complex.

I suspect that all that was really needed was case-insensitivity of ASCII a-z.
All of these versions of case-insensitivity provide that, so that is why they
may "seem" compatible...

- Eric

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Sun, Apr 27, 2025 at 07:22:40PM -0700, Eric Biggers wrote:
> Nor does it actually do Unicode casefolding
> (https://www.unicode.org/Public/16.0.0/ucd/CaseFolding.txt), but rather
> Unicode normalization which is more complex.

Do you mean to say that we invented yet another incompatible unicode
casefolding scheme?

Dear god, why?

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Linus Torvalds]

On Sun, 27 Apr 2025 at 19:34, Kent Overstreet <kent.overstreet@linux.dev> wrote:
>
> Do you mean to say that we invented yet another incompatible unicode
> casefolding scheme?
>
> Dear god, why?

Oh, Unicode itself comes with multiple "you can do this" schemes.

It's designed by committee, and meant for different situations and
different uses.  Because the rules for things like sorting names are
wildly different even for the same language, just for different
contexts.

Think of Unicode as "several decades of many different people coming
together, all having very different use cases".

So you find four different normalization forms, all with different use-cases.

And guess what? The only actual *valid* scheme for a filesystem is
none of the four. Literally. It's to say "we don't normalize".

Because the normalization forms are not meant to be some kind of "you
should do this".

They are meant as a kind of "if you are going to do X, then you can
normalize into form Y, which makes doing X easier". And often the
normalized form should only ever be an intermediate _temporary_ form
for doing comparisons, not the actual form you save things in.

Sadly, people so often get it wrong.

For example, one very typical "you got it wrong, because you didn't
understand the problem" case is to do comparisons by normalizing both
sides (in one of the normalization forms) and then doing the
comparison in that form.

And guess what? 99.9% of the time, you just wasted enormous amounts of
time, because you could have done the comparison first *without* any
normalization at all, because equality is equality even when neither
side is normalized.

And the *common* case is that you are comparing things that are in the
same form. For example, in filesystem operations, 99.999% of the time
when you do a 'stat()' the *source* of the 'stat()' is typically a
'readdir()' operation. So you are going to be using the same exact
form that the filesystem ALREADY HAD, and it's going to be an exact
match, and there will NEVER EVER be any case folding issues in those
situations.

But the "simplistic" way to do it is to always normalize - which
involves allocating temporary storage for the new form, doing a fairly
expensive transformation including case folding, and then comparing
those things.

Christ.

The pure and incompetence in case-insensitivity *hurts*.

And what is so sad is that all of this is self-inflicted damage by
filesystem people who SHOULD NOT HAVE DONE THE COMPLEXITY IN THE FIRST
PLACE!

It's a classic case of

  "Doctor, doctor, it hurts when I hit myself in the balls with this hammer"

and then people wonder why I still claim the answer still remains -
and always will remain - "Don't do that then".

               Linus

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Sun, Apr 27, 2025 at 07:53:26PM -0700, Linus Torvalds wrote:
> On Sun, 27 Apr 2025 at 19:34, Kent Overstreet <kent.overstreet@linux.dev> wrote:
> >
> > Do you mean to say that we invented yet another incompatible unicode
> > casefolding scheme?
> >
> > Dear god, why?
> 
> Oh, Unicode itself comes with multiple "you can do this" schemes.
> 
> It's designed by committee, and meant for different situations and
> different uses.  Because the rules for things like sorting names are
> wildly different even for the same language, just for different
> contexts.
> 
> Think of Unicode as "several decades of many different people coming
> together, all having very different use cases".
> 
> So you find four different normalization forms, all with different use-cases.

I'm still dying to know why we had to invent our own, though. The
proliferation of standards is just ridiculous.

> And guess what? The only actual *valid* scheme for a filesystem is
> none of the four. Literally. It's to say "we don't normalize".
> 
> Because the normalization forms are not meant to be some kind of "you
> should do this".
> 
> They are meant as a kind of "if you are going to do X, then you can
> normalize into form Y, which makes doing X easier". And often the
> normalized form should only ever be an intermediate _temporary_ form
> for doing comparisons, not the actual form you save things in.
> 
> Sadly, people so often get it wrong.
> 
> For example, one very typical "you got it wrong, because you didn't
> understand the problem" case is to do comparisons by normalizing both
> sides (in one of the normalization forms) and then doing the
> comparison in that form.
> 
> And guess what? 99.9% of the time, you just wasted enormous amounts of
> time, because you could have done the comparison first *without* any
> normalization at all, because equality is equality even when neither
> side is normalized.

Yeah, that's another point in favor of "index both the normalized and
un-normalized form".

i.e.: the normalized index is a special thing that doesn't have to
exist, and we only check it if the lookup in the un-normalized index
fails.

Case-insensitive capable filesystems could act just like normal
filesystems, unless specific pids opted into the extra "normalized
lookups" path.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Linus Torvalds]

On Sun, 27 Apr 2025 at 19:22, Eric Biggers <ebiggers@kernel.org> wrote:
>
> I suspect that all that was really needed was case-insensitivity of ASCII a-z.

Yes. That's my argument. I think anything else ends up being a
mistake. MAYBE extend it to the first 256 characters in Unicode (aka
"Latin1").

Case folding on a-z is the only thing you could really effectively
rely on in user space even in the DOS times, because different
codepages would make for different rules for the upper 128 characters
anyway, and you could be in a situation where you literally couldn't
copy files from one floppy to another, because two files that had
distinct names on one floppy would have the *same* name on another
one.

Of course, that was mostly a weird corner case that almost nobody ever
actually saw in practice, because very few people even used anything
else than the default codepage.

And the same is afaik still true on NT, although practically speaking
I suspect it went from "unusual" to "really doesn't happen EVER in
practice".

Extending those mistakes to full unicode and mixing in things like
nonprinting codes and other things have only made things worse.

And dealing with things like ß and ss and trying to make those compare
as equal is a *horrible* mistake. People who really need to do that
(usually for some legalistic local reason) tend to have very specific
rules for sorting anyway, and they are rules specific to particular
situations, not something that the filesystem should even try to work
with.

          Linus

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Sun, Apr 27, 2025 at 07:39:46PM -0700, Linus Torvalds wrote:
> On Sun, 27 Apr 2025 at 19:22, Eric Biggers <ebiggers@kernel.org> wrote:
> >
> > I suspect that all that was really needed was case-insensitivity of ASCII a-z.
> 
> Yes. That's my argument. I think anything else ends up being a
> mistake. MAYBE extend it to the first 256 characters in Unicode (aka
> "Latin1").
> 
> Case folding on a-z is the only thing you could really effectively
> rely on in user space even in the DOS times, because different
> codepages would make for different rules for the upper 128 characters
> anyway, and you could be in a situation where you literally couldn't
> copy files from one floppy to another, because two files that had
> distinct names on one floppy would have the *same* name on another
> one.
> 
> Of course, that was mostly a weird corner case that almost nobody ever
> actually saw in practice, because very few people even used anything
> else than the default codepage.
> 
> And the same is afaik still true on NT, although practically speaking
> I suspect it went from "unusual" to "really doesn't happen EVER in
> practice".

I'm having trouble finding anything authoritative, but what I'm seeing
indicates that NTFS does do Unicode casefolding (and their own
incompatible version, at that).

> Extending those mistakes to full unicode and mixing in things like
> nonprinting codes and other things have only made things worse.
> 
> And dealing with things like ß and ss and trying to make those compare
> as equal is a *horrible* mistake. People who really need to do that
> (usually for some legalistic local reason) tend to have very specific
> rules for sorting anyway, and they are rules specific to particular
> situations, not something that the filesystem should even try to work
> with.

Well, casefolding is something that's directly exposed to users. So I do
think that if casefolding is going to exist at all, there is a strong
argument for it to be unicode and handling things like ß to ss.

(Can you imagine being the user that gets used to typing in filenames
and ignoring capitalization, except whenever an accented letter is part
of the filename, and then your muscle-memeory breaks? That sort of thing
is maddening).

BUT:

I'm becoming more and more convinced that I want more separation between
casefolded lookups and non casefolded lookups, the potential for
casefolding rule changes to break case-sensitive lookups is just bad.

If we do a "casefolding version 2" in bcachefs, we'll just have a
separate btree for casefolded dirents, and casefolded directories will
have their dirents indexed twice.

That's trivially extensible to multiple versions if - god forbid - we
ever end up needing to support multiple "locales", and more importantly
it'd let us support a mode where it's only certain pids that get
casefolded lookups, so you don't e.g. get casefolding dependencies
creeping into your makefiles as can happen today.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Eric Biggers]

On Sun, Apr 27, 2025 at 11:01:20PM -0400, Kent Overstreet wrote:
> On Sun, Apr 27, 2025 at 07:39:46PM -0700, Linus Torvalds wrote:
> > On Sun, 27 Apr 2025 at 19:22, Eric Biggers <ebiggers@kernel.org> wrote:
> > >
> > > I suspect that all that was really needed was case-insensitivity of ASCII a-z.
> > 
> > Yes. That's my argument. I think anything else ends up being a
> > mistake. MAYBE extend it to the first 256 characters in Unicode (aka
> > "Latin1").
> > 
> > Case folding on a-z is the only thing you could really effectively
> > rely on in user space even in the DOS times, because different
> > codepages would make for different rules for the upper 128 characters
> > anyway, and you could be in a situation where you literally couldn't
> > copy files from one floppy to another, because two files that had
> > distinct names on one floppy would have the *same* name on another
> > one.
> > 
> > Of course, that was mostly a weird corner case that almost nobody ever
> > actually saw in practice, because very few people even used anything
> > else than the default codepage.
> > 
> > And the same is afaik still true on NT, although practically speaking
> > I suspect it went from "unusual" to "really doesn't happen EVER in
> > practice".
> 
> I'm having trouble finding anything authoritative, but what I'm seeing
> indicates that NTFS does do Unicode casefolding (and their own
> incompatible version, at that).

NTFS "just" has a 65536-entry table that maps UTF-16 coding units to their
"upper case" equivalents.  So it only does 1-to-1 codepoint mappings, and only
for U+FFFF and below.

I suspect that it's the same, or at least nearly the same, as what
https://www.unicode.org/Public/16.0.0/ucd/CaseFolding.txt calls "simple"
casefolding (as opposed to "full" casefolding), but only for U+FFFF and below.

Of course, to implement the same with Linux's UTF-8 names, we won't be able to
just do a simple table lookup like Windows does.  But it could still be
implemented -- we'd just decode the Unicode codepoints from the string and apply
the same mapping from there.  Still much simpler than normalization.

- Eric

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Linus Torvalds]

On Sun, 27 Apr 2025 at 20:01, Kent Overstreet <kent.overstreet@linux.dev> wrote:
>
> I'm having trouble finding anything authoritative, but what I'm seeing
> indicates that NTFS does do Unicode casefolding (and their own
> incompatible version, at that).

I think it's effectively a fixed table, yes.

I've never actually used NT. Back in the DOS days, you could set the
codepage on your medium, and people did. And it did cause problems,
but they were pretty rare.

People in non-US locales tended to learn to not rely on local case
folding rules for the local odd characters.

[ And I don't know if the Finnish situation was typical, but we
actually had a *7-bit* version of Finnish characters, which meant that
there were special case folding rules where '{' was the lowercase
version of '['. I know, that sounds insane, but there you are.

  Those rules never extended to the filesystem, though, but they
showed up in editors etc ]

> I'm becoming more and more convinced that I want more separation between
> casefolded lookups and non casefolded lookups, the potential for
> casefolding rule changes to break case-sensitive lookups is just bad.

Yeah. The problem is that it's just *hard*.

So when I am made Emperor and Grand Poo-Bah, I will solve all these
problems by just making case folding illegal.

But until that time, I really wish that people would at least try to
actively minimize the damage.

It would be interesting to hear from the Wine people (and Android
people) what the minimal set of case folding would be.

Because I really do suspect that there may not be any actual steam
games that rely on *anything* else than just A-Z.

That case really is much simpler to handle. You can do some really
cheap things like saying "for hashing filenames, I will just ignore
bit #5".

Of course, for *existing* setups, we're kind of screwed. The "two
different versions of the heart emoji" was from a real case,
apparently. Because those filesystems had already encoded the overly
complex rules in their hashes.

               Linus

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Eric Biggers]

On Sun, Apr 27, 2025 at 09:43:43PM -0400, Kent Overstreet wrote:
> On Sun, Apr 27, 2025 at 06:30:59PM -0700, Eric Biggers wrote:
> > On Sun, Apr 27, 2025 at 08:55:30PM -0400, Kent Overstreet wrote:
> > > The thing is, that's exactly what we're doing. ext4 and bcachefs both
> > > refer to a specific revision of the folding rules: for ext4 it's
> > > specified in the superblock, for bcachefs it's hardcoded for the moment.
> > > 
> > > I don't think this is the ideal approach, though.
> > > 
> > > That means the folding rules are "whatever you got when you mkfs'd".
> > > Think about what that means if you've got a fleet of machines, of
> > > different ages, but all updated in sync: that's a really annoying way
> > > for gremlins of the "why does this machine act differently" variety to
> > > creep in.
> > > 
> > > What I'd prefer is for the unicode folding rules to be transparently and
> > > automatically updated when the kernel is updated, so that behaviour
> > > stays in sync. That would behave more the way users would expect.
> > > 
> > > But I only gave this real thought just over the past few days, and doing
> > > this safely and correctly would require some fairly significant changes
> > > to the way casefolding works.
> > > 
> > > We'd have to ensure that lookups via the case sensitive name always
> > > works, even if the casefolding table the dirent was created with give
> > > different results that the currently active casefolding table.
> > > 
> > > That would require storing two different "dirents" for each real dirent,
> > > one normalized and one un-normalized, because we'd have to do an
> > > un-normalized lookup if the normalized lookup fails (and vice versa).
> > > Which should be completely fine from a performance POV, assuming we have
> > > working negative dentries.
> > > 
> > > But, if the unicode folding rules are stable enough (and one would hope
> > > they are), hopefully all this is a non-issue.
> > > 
> > > I'd have to gather more input from users of casefolding on other
> > > filesystems before saying what our long term plans (if any) will be.
> > 
> > Wouldn't lookups via the case-sensitive name keep working even if the
> > case-insensitivity rules change?  It's lookups via a case-insensitive name that
> > could start producing different results.  Applications can depend on
> > case-insensitive lookups being done in a certain way, so changing the
> > case-insensitivity rules can be risky.
> 
> No, because right now on a case-insensitive filesystem we _only_ do the
> lookup with the normalized name.

Well, changing the case-insensitivity rules on an existing filesystem breaks the
directory indexing, so when the filesystem does an indexed lookup in a directory
it might no longer look in the right place.  But if the dentry were to be
examined regardless, it would still match.  (Again, assuming that the lookup
uses a name that is case-sensitively the same as the name the file was created
with.  If it's not case-sensitively the same, that's another story.)  ext4 and
f2fs recently added a fallback to a linear search for dentries in "casefolded"
directories, which handle this by no longer relying solely on the directory
indexing.  See commits 9e28059d56649 and 91b587ba79e1b.

- Eric

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Sun, Apr 27, 2025 at 07:15:14PM -0700, Eric Biggers wrote:
> On Sun, Apr 27, 2025 at 09:43:43PM -0400, Kent Overstreet wrote:
> > On Sun, Apr 27, 2025 at 06:30:59PM -0700, Eric Biggers wrote:
> > > On Sun, Apr 27, 2025 at 08:55:30PM -0400, Kent Overstreet wrote:
> > > > The thing is, that's exactly what we're doing. ext4 and bcachefs both
> > > > refer to a specific revision of the folding rules: for ext4 it's
> > > > specified in the superblock, for bcachefs it's hardcoded for the moment.
> > > > 
> > > > I don't think this is the ideal approach, though.
> > > > 
> > > > That means the folding rules are "whatever you got when you mkfs'd".
> > > > Think about what that means if you've got a fleet of machines, of
> > > > different ages, but all updated in sync: that's a really annoying way
> > > > for gremlins of the "why does this machine act differently" variety to
> > > > creep in.
> > > > 
> > > > What I'd prefer is for the unicode folding rules to be transparently and
> > > > automatically updated when the kernel is updated, so that behaviour
> > > > stays in sync. That would behave more the way users would expect.
> > > > 
> > > > But I only gave this real thought just over the past few days, and doing
> > > > this safely and correctly would require some fairly significant changes
> > > > to the way casefolding works.
> > > > 
> > > > We'd have to ensure that lookups via the case sensitive name always
> > > > works, even if the casefolding table the dirent was created with give
> > > > different results that the currently active casefolding table.
> > > > 
> > > > That would require storing two different "dirents" for each real dirent,
> > > > one normalized and one un-normalized, because we'd have to do an
> > > > un-normalized lookup if the normalized lookup fails (and vice versa).
> > > > Which should be completely fine from a performance POV, assuming we have
> > > > working negative dentries.
> > > > 
> > > > But, if the unicode folding rules are stable enough (and one would hope
> > > > they are), hopefully all this is a non-issue.
> > > > 
> > > > I'd have to gather more input from users of casefolding on other
> > > > filesystems before saying what our long term plans (if any) will be.
> > > 
> > > Wouldn't lookups via the case-sensitive name keep working even if the
> > > case-insensitivity rules change?  It's lookups via a case-insensitive name that
> > > could start producing different results.  Applications can depend on
> > > case-insensitive lookups being done in a certain way, so changing the
> > > case-insensitivity rules can be risky.
> > 
> > No, because right now on a case-insensitive filesystem we _only_ do the
> > lookup with the normalized name.
> 
> Well, changing the case-insensitivity rules on an existing filesystem breaks the
> directory indexing, so when the filesystem does an indexed lookup in a directory
> it might no longer look in the right place.  But if the dentry were to be
> examined regardless, it would still match.  (Again, assuming that the lookup
> uses a name that is case-sensitively the same as the name the file was created
> with.  If it's not case-sensitively the same, that's another story.)  ext4 and
> f2fs recently added a fallback to a linear search for dentries in "casefolded"
> directories, which handle this by no longer relying solely on the directory
> indexing.  See commits 9e28059d56649 and 91b587ba79e1b.

bcachefs stores the normalized d_name, in addition to the
un-normalized version, so our low level directory indexing works just
fine if the normalization rules change.

That is, bcachefs could be changed to always load the latest unicode
normalization table, and internally everything will work completely
fine.

BUT:

If the normalization rules change for an existing dirent, then looking up
the un-normalized name with the new rules gives you a different
normalization than what's on disk and would return -ENOENT. You'd have
to look up the old normalized name, or something that normalized to the
old normalized name, to find it. Obviously, that's broken.

IOW: bcachefs doesn't have the linear search fallback, and that's not
something I'd ever add. That effectively means a silent fallback to
O(n^2) algorithms, and I don't want the bug reports that would someday
generate.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Eric Biggers]

On Sun, Apr 27, 2025 at 10:33:29PM -0400, Kent Overstreet wrote:
> On Sun, Apr 27, 2025 at 07:15:14PM -0700, Eric Biggers wrote:
> > On Sun, Apr 27, 2025 at 09:43:43PM -0400, Kent Overstreet wrote:
> > > On Sun, Apr 27, 2025 at 06:30:59PM -0700, Eric Biggers wrote:
> > > > On Sun, Apr 27, 2025 at 08:55:30PM -0400, Kent Overstreet wrote:
> > > > > The thing is, that's exactly what we're doing. ext4 and bcachefs both
> > > > > refer to a specific revision of the folding rules: for ext4 it's
> > > > > specified in the superblock, for bcachefs it's hardcoded for the moment.
> > > > > 
> > > > > I don't think this is the ideal approach, though.
> > > > > 
> > > > > That means the folding rules are "whatever you got when you mkfs'd".
> > > > > Think about what that means if you've got a fleet of machines, of
> > > > > different ages, but all updated in sync: that's a really annoying way
> > > > > for gremlins of the "why does this machine act differently" variety to
> > > > > creep in.
> > > > > 
> > > > > What I'd prefer is for the unicode folding rules to be transparently and
> > > > > automatically updated when the kernel is updated, so that behaviour
> > > > > stays in sync. That would behave more the way users would expect.
> > > > > 
> > > > > But I only gave this real thought just over the past few days, and doing
> > > > > this safely and correctly would require some fairly significant changes
> > > > > to the way casefolding works.
> > > > > 
> > > > > We'd have to ensure that lookups via the case sensitive name always
> > > > > works, even if the casefolding table the dirent was created with give
> > > > > different results that the currently active casefolding table.
> > > > > 
> > > > > That would require storing two different "dirents" for each real dirent,
> > > > > one normalized and one un-normalized, because we'd have to do an
> > > > > un-normalized lookup if the normalized lookup fails (and vice versa).
> > > > > Which should be completely fine from a performance POV, assuming we have
> > > > > working negative dentries.
> > > > > 
> > > > > But, if the unicode folding rules are stable enough (and one would hope
> > > > > they are), hopefully all this is a non-issue.
> > > > > 
> > > > > I'd have to gather more input from users of casefolding on other
> > > > > filesystems before saying what our long term plans (if any) will be.
> > > > 
> > > > Wouldn't lookups via the case-sensitive name keep working even if the
> > > > case-insensitivity rules change?  It's lookups via a case-insensitive name that
> > > > could start producing different results.  Applications can depend on
> > > > case-insensitive lookups being done in a certain way, so changing the
> > > > case-insensitivity rules can be risky.
> > > 
> > > No, because right now on a case-insensitive filesystem we _only_ do the
> > > lookup with the normalized name.
> > 
> > Well, changing the case-insensitivity rules on an existing filesystem breaks the
> > directory indexing, so when the filesystem does an indexed lookup in a directory
> > it might no longer look in the right place.  But if the dentry were to be
> > examined regardless, it would still match.  (Again, assuming that the lookup
> > uses a name that is case-sensitively the same as the name the file was created
> > with.  If it's not case-sensitively the same, that's another story.)  ext4 and
> > f2fs recently added a fallback to a linear search for dentries in "casefolded"
> > directories, which handle this by no longer relying solely on the directory
> > indexing.  See commits 9e28059d56649 and 91b587ba79e1b.
> 
> bcachefs stores the normalized d_name, in addition to the
> un-normalized version, so our low level directory indexing works just
> fine if the normalization rules change.
> 
> That is, bcachefs could be changed to always load the latest unicode
> normalization table, and internally everything will work completely
> fine.
> 
> BUT:
> 
> If the normalization rules change for an existing dirent, then looking up
> the un-normalized name with the new rules gives you a different
> normalization than what's on disk and would return -ENOENT. You'd have
> to look up the old normalized name, or something that normalized to the
> old normalized name, to find it. Obviously, that's broken.
> 
> IOW: bcachefs doesn't have the linear search fallback, and that's not
> something I'd ever add. That effectively means a silent fallback to
> O(n^2) algorithms, and I don't want the bug reports that would someday
> generate.

Is there a reason why you don't just do what ext4 and f2fs does and store (only)
the case-preserved original name on-disk?

Note that generic_ci_match() has a fast path that compares the bytes of the
on-disk name to the bytes of the user-requested name.  Only if they don't match
is the "casefolded" comparison done.  It's true that if the filesystem were to
store the "casefolded" name on-disk too, then it wouldn't have to be computed
for each "casefolded" comparison with that dentry.  But that's already the "slow
path" that is executed only when the name wasn't case-sensitively the same.

- Eric

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Sun, Apr 27, 2025 at 07:49:45PM -0700, Eric Biggers wrote:
> Is there a reason why you don't just do what ext4 and f2fs does and store (only)
> the case-preserved original name on-disk?

The rationale was performance.

In hindsight I think that made zero sense, but perhaps it will turn out
to be useful in a way - because that's what got me thinking about
compatibility more, and then "separate indexes for casefolded and non
casefolded".

I'm not sure that this is honestly pressing enough that we'll write the
code, but that is feeling like the actual correct approach here.

> 
> Note that generic_ci_match() has a fast path that compares the bytes of the
> on-disk name to the bytes of the user-requested name.  Only if they don't match
> is the "casefolded" comparison done.  It's true that if the filesystem were to
> store the "casefolded" name on-disk too, then it wouldn't have to be computed
> for each "casefolded" comparison with that dentry.  But that's already the "slow
> path" that is executed only when the name wasn't case-sensitively the same.

Yeah, and all this is only hit on dcache misses, which makes it pretty
irrelevant.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Theodore Ts'o]

The resaon why I pushed for case folding was because Android userspace
needed it, for backwards compatibiliy with previous implementationsm
(which did use FAT), and the alternative we were replacing was this
horrific wrapfs implementation which Al refused to accept because it a
mess from a locking perspective; I could trivially lock up the kernel
or cause file system corruptions using fsstress when wrapfs was in the
picture.

Another use case was Valve who wanted to support Windows games that
expcted case folding to work.  (Microsoft Windows; the gift that keeps
on giving...)  In fact the engineer who worked on case folding was
paid by Valve to do the work.

That being said, I completely agree with Linus that case insensitivity
is a nightmare, and I don't really care about performance.  The use
cases where people care about this don't have directories with a large
number of entries, and we **really** don't want to encourage more use
of case insensitive lookups.  There's a reason why spent much effort
improving the CLI tools' support for case folding.  It's good enough
that it works for Android and Valve, and that's fine.

As far as Unicode changing over time, in practice, we don't really
need to care.  Unicode has promised not to make backwards incompatible
changes; they might add new characters, for some ancient Mesopotamian
script that only some academic care about, or a new set of emoji's.
Fortunately, either the case folding tables aren't getting extended
(emoji's don't have case to be folded; the ancient sumarian script
might note have the concept of case in teh first place) or we just
don't care (even if said sumarian script did *have* case folding, it's
unlikely that a cell phone user or a Valve gamer would likely to
care).

I will readily admit that Unicode is something we didn't completely
understand; never in my worst nightmares that someone would be
silly/insane enough to add the concept of zero-width characters,
including zero-width characters that end up changing how the character
is displayed (e.g., a red heart versus a black spade differs only by
adding a zero-width selector/shift character.   Sigh....)

Perhaps if we were going to do it all over, we might have only
supported ASCII, or ISO Latin-1, and not used Unicode at all.  But
then I'm sure Valve or Android mobile handset manufacturers would be
unhappy that this might not be good enough for some country that they
want to sell into, like, say, Japan or more generally, any country
beyond US and Europe.

What we probably could do is to create our own table that didn't
support all Unicode scripts, but only the ones which are required by
Valve and Android.  But that would require someone willing to do this
work on a volunteer basis, or confinuce some company to pay to do this
work.  We could probably reduce the kernel size by doing this, and it
would probably make the code more maintainable.  I'm just not sure
anyone thinks its worthwhile to invest more into it.  In fact, I'm a
bit surprised Kent decided he wanted to add this feature into bcachefs.

Sometimes, partitioning a feature which is only needed for backwards
compatibiltiy with is in fact the right approach.  And throwing good
money after bad is rarely worth it.

Cheers,

						- Ted

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[H. Peter Anvin]

On 4/25/25 12:59, Theodore Ts'o wrote:
> 
> Another use case was Valve who wanted to support Windows games that
> expcted case folding to work.  (Microsoft Windows; the gift that keeps
> on giving...)  In fact the engineer who worked on case folding was
> paid by Valve to do the work.
> 
> That being said, I completely agree with Linus that case insensitivity
> is a nightmare, and I don't really care about performance.  The use
> cases where people care about this don't have directories with a large
> number of entries, and we **really** don't want to encourage more use
> of case insensitive lookups.  There's a reason why spent much effort
> improving the CLI tools' support for case folding.  It's good enough
> that it works for Android and Valve, and that's fine.
> 
[...]
> 
> Perhaps if we were going to do it all over, we might have only
> supported ASCII, or ISO Latin-1, and not used Unicode at all.  But
> then I'm sure Valve or Android mobile handset manufacturers would be
> unhappy that this might not be good enough for some country that they
> want to sell into, like, say, Japan or more generally, any country
> beyond US and Europe.
> 
> What we probably could do is to create our own table that didn't
> support all Unicode scripts, but only the ones which are required by
> Valve and Android.  But that would require someone willing to do this
> work on a volunteer basis, or confinuce some company to pay to do this
> work.  We could probably reduce the kernel size by doing this, and it
> would probably make the code more maintainable.  I'm just not sure
> anyone thinks its worthwhile to invest more into it.  In fact, I'm a
> bit surprised Kent decided he wanted to add this feature into bcachefs.
> 
> Sometimes, partitioning a feature which is only needed for backwards
> compatibiltiy with is in fact the right approach.  And throwing good
> money after bad is rarely worth it.
> 

[Yes, I realize I'm really late to weigh in on this discussion]

It is worth noting that Microsoft has basically declared their 
"recommended" case folding (upcase) table to be permanently frozen (for 
new filesystem instances in the case where they use an on-disk 
translation table created at format time.)  As far as I know they have 
never supported anything other than 1:1 conversion of BMP code points, 
nor normalization.

The exFAT specification enumerates the full recommended upcase table, 
although in a somewhat annoying format (basically a hex dump of 
compressed data):

https://learn.microsoft.com/en-us/windows/win32/fileio/exfat-specification

This is basically an admission that the problems involved with case 
folding are unsolvable, and just puts a tourniquet on the wound.

It also means that "legacy OS compatibility" is really a totally 
different problem than "proper Unicode normalization" and that the 
former far more limited in scope.

	-hpa

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Wed, Apr 30, 2025 at 07:48:20PM -0700, H. Peter Anvin wrote:
> On 4/25/25 12:59, Theodore Ts'o wrote:
> > 
> > Another use case was Valve who wanted to support Windows games that
> > expcted case folding to work.  (Microsoft Windows; the gift that keeps
> > on giving...)  In fact the engineer who worked on case folding was
> > paid by Valve to do the work.
> > 
> > That being said, I completely agree with Linus that case insensitivity
> > is a nightmare, and I don't really care about performance.  The use
> > cases where people care about this don't have directories with a large
> > number of entries, and we **really** don't want to encourage more use
> > of case insensitive lookups.  There's a reason why spent much effort
> > improving the CLI tools' support for case folding.  It's good enough
> > that it works for Android and Valve, and that's fine.
> > 
> [...]
> > 
> > Perhaps if we were going to do it all over, we might have only
> > supported ASCII, or ISO Latin-1, and not used Unicode at all.  But
> > then I'm sure Valve or Android mobile handset manufacturers would be
> > unhappy that this might not be good enough for some country that they
> > want to sell into, like, say, Japan or more generally, any country
> > beyond US and Europe.
> > 
> > What we probably could do is to create our own table that didn't
> > support all Unicode scripts, but only the ones which are required by
> > Valve and Android.  But that would require someone willing to do this
> > work on a volunteer basis, or confinuce some company to pay to do this
> > work.  We could probably reduce the kernel size by doing this, and it
> > would probably make the code more maintainable.  I'm just not sure
> > anyone thinks its worthwhile to invest more into it.  In fact, I'm a
> > bit surprised Kent decided he wanted to add this feature into bcachefs.
> > 
> > Sometimes, partitioning a feature which is only needed for backwards
> > compatibiltiy with is in fact the right approach.  And throwing good
> > money after bad is rarely worth it.
> > 
> 
> [Yes, I realize I'm really late to weigh in on this discussion]
> 
> It is worth noting that Microsoft has basically declared their "recommended"
> case folding (upcase) table to be permanently frozen (for new filesystem
> instances in the case where they use an on-disk translation table created at
> format time.)  As far as I know they have never supported anything other
> than 1:1 conversion of BMP code points, nor normalization.
> 
> The exFAT specification enumerates the full recommended upcase table,
> although in a somewhat annoying format (basically a hex dump of compressed
> data):
> 
> https://learn.microsoft.com/en-us/windows/win32/fileio/exfat-specification

Thanks, I'm adding this to Documentation/filesystems/bcachefs/casefolding.rst

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Linus Torvalds]

On Wed, 30 Apr 2025 at 19:48, H. Peter Anvin <hpa@zytor.com> wrote:
>
> It is worth noting that Microsoft has basically declared their
> "recommended" case folding (upcase) table to be permanently frozen (for
> new filesystem instances in the case where they use an on-disk
> translation table created at format time.)  As far as I know they have
> never supported anything other than 1:1 conversion of BMP code points,
> nor normalization.

So no crazy 'ß' matches 'ss' kind of thing? (And yes, afaik that's
technically wrong even in German, but afaik at least sorts the same in
some locales).

Because yes, if MS basically does a 1:1 unicode translation with a
fixed table, that is not only "simpler", I think it's what we should
strive for.

Because I think the *only* valid reason for case insensitive
filesystems is "backwards compatibility", and given that, it's
_particularly_ stupid to then do anything more complicated and broken
than the thing you're trying to be compatible with.

I hope to everything holy that nobody ever wants to be compatible with
the absolute garbage that is the OSX HFS model.

Because the whole "let's actively corrupt names into something that is
almost, but not exactly, NFD" stuff is just some next-level evil
stuff.

            Linus

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[H. Peter Anvin]

On April 30, 2025 8:12:20 PM PDT, Linus Torvalds <torvalds@linux-foundation.org> wrote:
>On Wed, 30 Apr 2025 at 19:48, H. Peter Anvin <hpa@zytor.com> wrote:
>>
>> It is worth noting that Microsoft has basically declared their
>> "recommended" case folding (upcase) table to be permanently frozen (for
>> new filesystem instances in the case where they use an on-disk
>> translation table created at format time.)  As far as I know they have
>> never supported anything other than 1:1 conversion of BMP code points,
>> nor normalization.
>
>So no crazy 'ß' matches 'ss' kind of thing? (And yes, afaik that's
>technically wrong even in German, but afaik at least sorts the same in
>some locales).
>
>Because yes, if MS basically does a 1:1 unicode translation with a
>fixed table, that is not only "simpler", I think it's what we should
>strive for.
>
>Because I think the *only* valid reason for case insensitive
>filesystems is "backwards compatibility", and given that, it's
>_particularly_ stupid to then do anything more complicated and broken
>than the thing you're trying to be compatible with.
>
>I hope to everything holy that nobody ever wants to be compatible with
>the absolute garbage that is the OSX HFS model.
>
>Because the whole "let's actively corrupt names into something that is
>almost, but not exactly, NFD" stuff is just some next-level evil
>stuff.
>
>            Linus
>

I suspect the NFD bit in HFS comes from the use of decomposed characters in the 8-bit character systems of MacOS Classic.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Carl E. Thompson]

Here's a probably silly question from someone who isn't a kernel developer: What's the point of all this effort to do case-folding at the Linux kernel level anyway?

Linux and UNIX applications don't need it. Certainly nothing performance critical uses it.

If certain Windows games and applications need case-folding and Wine wants to let Linux users run those applications then let Wine handle case-folding at *their* layer since they have to implement Microsoft's filesystem APIs / ABIs anyway.

Or implement loop-device namespaces and let users mount their own exFAT images for the Wine case and contain the evilness to *that* driver.

I can think of no *good* reason why a modern *Linux* filesystem needs case-folding. (I don't consider it being a challenging problem to "solve" to be a good reason. Neither is because someone is paying you to help their narrow use case if it means making more common cases less optimal or more complex.)

I do very much agree with a point that I think Kent was making that humans beings expect case-folding in their interactions with computers. That's true. But the human interaction case doesn't need to be handled in the kernel, does it? When I click "Open" in my editor and start typing to find a file it *already* case folds for me and it does it without filesystem support. Same thing for my file browser. Same thing for the 'ls' command in my configuration. We already have tons of options in user space for this.

Thanks,
Carl

PS: And as long as folks are opining on the causes and history of this problem maybe go right to the origin: whomever first made the idiotic decision that computers should internally represent an uppercase 'A' with a different code than a lowercase 'a'. Sure that probably made writing routines to display a limited set of glyphs on ancient OSs a little easier but logically it makes no sense. *It's the same letter!* I guess I can be thankful they didn't add separate codes for italics, bold and serif versions of the letters too. (But at least one company *did* add reversed foreground/background letters to there version of ASCII.) There should only be one code for each letter and everything else should be up to user space. 


> On 2025-04-30 8:32 PM PDT H. Peter Anvin <hpa@zytor.com> wrote:
> 
>  
> On April 30, 2025 8:12:20 PM PDT, Linus Torvalds <torvalds@linux-foundation.org> wrote:
> >On Wed, 30 Apr 2025 at 19:48, H. Peter Anvin <hpa@zytor.com> wrote:
> >>
> >> It is worth noting that Microsoft has basically declared their
> >> "recommended" case folding (upcase) table to be permanently frozen (for
> >> new filesystem instances in the case where they use an on-disk
> >> translation table created at format time.)  As far as I know they have
> >> never supported anything other than 1:1 conversion of BMP code points,
> >> nor normalization.
> >
> >So no crazy 'ß' matches 'ss' kind of thing? (And yes, afaik that's
> >technically wrong even in German, but afaik at least sorts the same in
> >some locales).
> >
> >Because yes, if MS basically does a 1:1 unicode translation with a
> >fixed table, that is not only "simpler", I think it's what we should
> >strive for.
> >
> >Because I think the *only* valid reason for case insensitive
> >filesystems is "backwards compatibility", and given that, it's
> >_particularly_ stupid to then do anything more complicated and broken
> >than the thing you're trying to be compatible with.
> >
> >I hope to everything holy that nobody ever wants to be compatible with
> >the absolute garbage that is the OSX HFS model.
> >
> >Because the whole "let's actively corrupt names into something that is
> >almost, but not exactly, NFD" stuff is just some next-level evil
> >stuff.
> >
> >            Linus
> >
> 
> I suspect the NFD bit in HFS comes from the use of decomposed characters in the 8-bit character systems of MacOS Classic.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[H. Peter Anvin]

On April 30, 2025 8:12:20 PM PDT, Linus Torvalds <torvalds@linux-foundation.org> wrote:
>On Wed, 30 Apr 2025 at 19:48, H. Peter Anvin <hpa@zytor.com> wrote:
>>
>> It is worth noting that Microsoft has basically declared their
>> "recommended" case folding (upcase) table to be permanently frozen (for
>> new filesystem instances in the case where they use an on-disk
>> translation table created at format time.)  As far as I know they have
>> never supported anything other than 1:1 conversion of BMP code points,
>> nor normalization.
>
>So no crazy 'ß' matches 'ss' kind of thing? (And yes, afaik that's
>technically wrong even in German, but afaik at least sorts the same in
>some locales).
>
>Because yes, if MS basically does a 1:1 unicode translation with a
>fixed table, that is not only "simpler", I think it's what we should
>strive for.
>
>Because I think the *only* valid reason for case insensitive
>filesystems is "backwards compatibility", and given that, it's
>_particularly_ stupid to then do anything more complicated and broken
>than the thing you're trying to be compatible with.
>
>I hope to everything holy that nobody ever wants to be compatible with
>the absolute garbage that is the OSX HFS model.
>
>Because the whole "let's actively corrupt names into something that is
>almost, but not exactly, NFD" stuff is just some next-level evil
>stuff.
>
>            Linus
>

Yeah, collation order is highly localized, and had never made the assumption of being expected to be used as a unique lookup key.

It's also completely inconsistent, even between neighboring locales, like how in Swedish and Finnish Å sorts before Ä/Æ and Ö/Ø whereas as Danish and Norwegian sort Å after; even though everyone agrees Ä/Æ and Ö/Ø are the same letter and are to be sorted the same. Icelandic doesn't have Å but sorts it as Danish after Ä and Ø(!) but stuffs Þ after Z instead of with or after T. Swedish, and I believe the other Nordic languages, sort Ü as Y, but in German Ä, Ö, and Ü are sorted as A, O and U.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Fri, Apr 25, 2025 at 09:35:27AM -0700, Linus Torvalds wrote:
> On Thu, 24 Apr 2025 at 21:52, Kent Overstreet <kent.overstreet@linux.dev> wrote:
> >
> > And the attitude of "I hate this, so I'm going to partition this off as
> > much as I can and spend as little time as I can on this" has all made
> > this even worse - the dcache stuff is all half baked.
> 
> No. The dcache side is *correct*.
> 
> The thing is, you absolutely cannot make the case-insensitive lookup
> be the fast case.

That's precisely what the dcache code does, and is the source of the
preblems.

Case insensitivy in the dcache caches the case sensitive name the lookup
was done with, not the case insensitive name we do the comparison
against.

That means we end up with extra aliases - and potentially an _unbounded_
number of aliases if someone is screwing around. Given the problems
we've had with negative dentries, that sounds like a DOS attack waiting
to happen.

It also introduces tricky corner cases into the filesystem code; last
bug I was chasing last night was one where without calling
d_prune_aliases(), those aliases would stick around and end up pointing
to an old version of the vfs inode when the file was deleted and
recreated, which was only caught by bcachefs assertions in our
write_inode method. Eesh.

And that's to say nothing of the complications w.r.t. negative dentries.

I would've rather had the dcache itself do normalization in pathwalk,
and only cache the _normalized_ dirent name.

That would've made lookups a tiny bit slower - but like you said, who
cares; we don't need case insensitive lookups to be the fastpath. RCU
pathwalks would've still worked, it wouldn't have been huge.

Maybe the samba people cared, I haven't looked up the original
discussions. But it seems more likely the determining factor was keeping
case insensitivity out of the dcache code.

> Now, if filesystem people were to see the light, and have a proper and
> well-designed case insensitivity, that might change. But I've never
> seen even a *whiff* of that. I have only seen bad code that
> understands neither how UTF-8 works, nor how unicode works (or rather:
> how unicode does *not* work - code that uses the unicode comparison
> functions without a deeper understanding of what the implications
> are).

Since you're not saying anything about how you think filesystems get
this wrong, this is just trash talking. I haven't seen anything that
looks broken about how case insensitivy is handled.

And honestly I don't think the security "concerns" are real concerns
anymore, since we're actively getting away from directories shared by
different users - /tmp - because that's caused _so_ many problems all on
its own.

(But unicode does create problems with e.g. all the different space
characters, because if you do have a shared directory you can now do
sneaky things like drop in a file that appears to have the same name as
another file, and try to get a unsuspecting user to click on the wrong
one. I don't think that's something the filesystem needs to be getting
involved in - that's a "don't use shared directories, idiot" problem,
i.e. your permissions model is broken if you're affected by that.)

> It's in filesystem people who didn't understand - and still don't,
> after decades - that you MUST NOT just blindly follow some external
> case folding table that you don't understand and that can change over
> time.
> 
> The "change overr time" part is particularly vexing to me, because it
> breaks one of the fundamental rules that unicode was *supposed* to
> fix: no locale garbage.

First off, since the unicode folding rules are referenced by the on disk
formats, they are _not_ changing without review by filesystem folks.

Actually - not in the case of bcachefs, since we store both the
normalized and unnormalized d_name.

Like Ted said, updates that simply add folding rules for new unicode
charecters are totally fine. Aside from that, everyone agrees with you
that we don't want locale garbage, literally no one is asking for that.

So I don't know where yuo're getting that from.

In filesystem land, we version things because you'd be BLOODY STUPID not
to - not because we plan on making changes willy-nilly.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Linus Torvalds]

On Fri, 25 Apr 2025 at 18:38, Kent Overstreet <kent.overstreet@linux.dev> wrote:
>
> On Fri, Apr 25, 2025 at 09:35:27AM -0700, Linus Torvalds wrote:
> >
> > The thing is, you absolutely cannot make the case-insensitive lookup
> > be the fast case.
>
> That's precisely what the dcache code does, and is the source of the
> problems.

I think you're confused, and don't know what you are talking about.
You'd better go learn how the dcache actually works.

            Linus

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Fri, Apr 25, 2025 at 07:47:09PM -0700, Linus Torvalds wrote:
> On Fri, 25 Apr 2025 at 18:38, Kent Overstreet <kent.overstreet@linux.dev> wrote:
> >
> > On Fri, Apr 25, 2025 at 09:35:27AM -0700, Linus Torvalds wrote:
> > >
> > > The thing is, you absolutely cannot make the case-insensitive lookup
> > > be the fast case.
> >
> > That's precisely what the dcache code does, and is the source of the
> > problems.
> 
> I think you're confused, and don't know what you are talking about.
> You'd better go learn how the dcache actually works.

No, what I wrote is exactly how CI lookups work with the dcache. Go have
a look.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Linus Torvalds]

On Fri, 25 Apr 2025 at 20:00, Kent Overstreet <kent.overstreet@linux.dev> wrote:
>
> No, what I wrote is exactly how CI lookups work with the dcache. Go have
> a look.

Kent, I literally wrote most of that code, and you are claiming that
the CI case is trying to be the fast case.

Not so. Get a clue. The CI case is the "nobody cares" case. It goes
off and does nasty stuff. It's very much designed to *not* affect the
sane case.

The things you complain about may be exactly those things. You just
don't understand the design.

             Linus

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Fri, Apr 25, 2025 at 08:04:08PM -0700, Linus Torvalds wrote:
> On Fri, 25 Apr 2025 at 20:00, Kent Overstreet <kent.overstreet@linux.dev> wrote:
> >
> > No, what I wrote is exactly how CI lookups work with the dcache. Go have
> > a look.
> 
> Kent, I literally wrote most of that code,

The subject is CI lookups, and I'll eat my shoe if you wrote that.

> and you are claiming that the CI case is trying to be the fast case.

Are you being obtuse on purpose?

I'm saying the CI case is a combination of overoptimized and poorly
designed. I'm not saying the CI case is trying to be the fast path
relative to case-sensitive lookups, that would be insane.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Linus Torvalds]

On Fri, 25 Apr 2025 at 20:09, Kent Overstreet <kent.overstreet@linux.dev> wrote:
>
> The subject is CI lookups, and I'll eat my shoe if you wrote that.

Start chomping. That nasty code with d_compare and d_hash goes way back.

From a quick look, it's from '97, and got merged in in 2.1.50. It was
added (obviously) for FAT. Back then, that was the only case that
wanted it.

I don't have any archives from that time, and I'm sure others were
involved, but that whole init_name_hash / partial_name_hash /
end_name_hash pattern in 2.1.50 looks like code I remember. So I was
at least part of it.

The design, if you haven't figured it out yet, is that filesystems
that have case-independent name comparisons can do their own hash
functions and their own name comparison functions, exactly so that one
dentry can match multiple different strings (and different strings can
hash to the same bucket).

If you get dentry aliases, you may be doing something wrong.

Also, originally this was all in the same core dcache lookup path. So
the whole "we have to check if the filesystem has its own hash
function" ended up slowing down the normal case. It's obviously been
massively modified since 1997 ("No, really?"), and now the code is
very much set up so that the straight-line normal case is all the
non-CI cases, and then case idnependence ends up out-of-line with its
own dcache hash lookup loops so that it doesn't affect the normal good
case.

            Linus

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Fri, Apr 25, 2025 at 08:40:48PM -0700, Linus Torvalds wrote:
> On Fri, 25 Apr 2025 at 20:09, Kent Overstreet <kent.overstreet@linux.dev> wrote:
> >
> > The subject is CI lookups, and I'll eat my shoe if you wrote that.
> 
> Start chomping. That nasty code with d_compare and d_hash goes way back.
> 
> From a quick look, it's from '97, and got merged in in 2.1.50. It was
> added (obviously) for FAT. Back then, that was the only case that
> wanted it.
> 
> I don't have any archives from that time, and I'm sure others were
> involved, but that whole init_name_hash / partial_name_hash /
> end_name_hash pattern in 2.1.50 looks like code I remember. So I was
> at least part of it.
> 
> The design, if you haven't figured it out yet, is that filesystems
> that have case-independent name comparisons can do their own hash
> functions and their own name comparison functions, exactly so that one
> dentry can match multiple different strings (and different strings can
> hash to the same bucket).
> 
> If you get dentry aliases, you may be doing something wrong.

Yeah, Al just pointed me at generic_set_sb_d_ops().

Which is a perverse way to hide an ops struct. Bloody hell...

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Linus Torvalds]

On Fri, 25 Apr 2025 at 20:59, Kent Overstreet <kent.overstreet@linux.dev> wrote:
>
> Yeah, Al just pointed me at generic_set_sb_d_ops().
>
> Which is a perverse way to hide an ops struct. Bloody hell...

Kent, it's that perverse thing EXACTLY FOR THE REASONS I TOLD YOU.

The common case will never even *look* at the dentry ops, because
that's way too damn expensive, and the common case wants nothing at
all to do with case insensitivity.

So guess why that odd specialized function exists?

Exactly because the dcache makes damn sure that the irrelevant CI case
is never in the hot path. So when you set those special dentry
operations to say that you want the CI slow-paths, the VFS layer then
sets magic bits in the dentry itself that makes it go to there.

That way the dentry code doesn't do the extra check for "do I have
special dentry operations for hashing on bad filesystems?" IOW, in
order to avoid two pointer dereferences, we set one bit in the dentry
flags instead, and now we have that information right there.

So yes, people who want to use case-insensitive lookups need to go to
some extra effort, exactly because we do NOT want that garbage to
affect the well-behaved paths.

And no, I'm not surprised that you didn't get it all right. The VFS
layer is complicated, and the dentry cache is some of the more complex
parts of it.

And a lot of that complexity comes from all the performance tuning -
and a small part of it has very much been about getting this CI crap
out of the way.

A much bigger part has admittedly been all the locking complexity, the
RCU lookup, and the whole extra 'struct path' layer that allows us to
share the same dentry across multiple mounts.

The credit for almost all of *that* complexity goes to Al. Because
some of that code scares even me, and I'm supposed to know that part
of the kernel better than most.

             Linus

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Fri, Apr 25, 2025 at 09:11:18PM -0700, Linus Torvalds wrote:
> On Fri, 25 Apr 2025 at 20:59, Kent Overstreet <kent.overstreet@linux.dev> wrote:
> >
> > Yeah, Al just pointed me at generic_set_sb_d_ops().
> >
> > Which is a perverse way to hide an ops struct. Bloody hell...
> 
> Kent, it's that perverse thing EXACTLY FOR THE REASONS I TOLD YOU.

And you never noticed that the complaints I had about the dcache bits
didn't make sense and how I said it should work was how it actually does
work? Heh.

We were talking past each other because everywhere else in filesystem
land you define your ops structs, which means you can read through them,
but when the ops struct is behind a helper that can be called from
anywhere (the ext4 init code is what, 400 lines ballpark last I check) -
good luck...

> The common case will never even *look* at the dentry ops, because
> that's way too damn expensive, and the common case wants nothing at
> all to do with case insensitivity.
> 
> So guess why that odd specialized function exists?
> 
> Exactly because the dcache makes damn sure that the irrelevant CI case
> is never in the hot path. So when you set those special dentry
> operations to say that you want the CI slow-paths, the VFS layer then
> sets magic bits in the dentry itself that makes it go to there.
> 
> That way the dentry code doesn't do the extra check for "do I have
> special dentry operations for hashing on bad filesystems?" IOW, in
> order to avoid two pointer dereferences, we set one bit in the dentry
> flags instead, and now we have that information right there.

Well, that's d_set_op(), for the "flags to skip hitting the ops struct"
bits. That's perfectly sane, sensible thing to do; you could still pass
a d_ops to it that was defined within that specific filesystem.

generic_set_sb_d_ops() just hides the fact that a d_operations exists.
That's where the confusion came from, because if any of the other major
local filesystems defined one I'd have seen it.

> So yes, people who want to use case-insensitive lookups need to go to
> some extra effort, exactly because we do NOT want that garbage to
> affect the well-behaved paths.
> 
> And no, I'm not surprised that you didn't get it all right. The VFS
> layer is complicated, and the dentry cache is some of the more complex
> parts of it.

I think the more hilarious part is that CI lookups without the special
d_ops seems to actually work - passes tests and I got a report today
that the code I finished last night "works now, please don't change it".

So, yeah. Fun times.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Linus Torvalds]

On Fri, 25 Apr 2025 at 21:49, Kent Overstreet <kent.overstreet@linux.dev> wrote:
>
> And you never noticed that the complaints I had about the dcache bits
> didn't make sense and how I said it should work was how it actually does
> work? Heh.

That's a funny way of saying

  "Oh, Linus, you were right in the first place when you called me out
on my bullshit"

Here's a clue, Kent. I told you you were wrong and full of shit. Let
me quote that for you again:

  "I think you're confused, and don't know what you are talking about.
   You'd better go learn how the dcache actually works"

You doubled down and tried to tell me otherwise.

You were wrong. Again.

I'm really tired of your constant attitude where you think you
absolutely know best, and then EVEN WHEN YOU ARE WRONG you try to make
it be about somebody else.

Now you are trying to make it about *me* somehow not noticing YOUR
ABSOLUTE BULLSHIT.

Just walk away, Kent. Because I'm very close to being done with this
constant aggravation.

                Linus

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Fri, Apr 25, 2025 at 10:01:20PM -0700, Linus Torvalds wrote:
> On Fri, 25 Apr 2025 at 21:49, Kent Overstreet <kent.overstreet@linux.dev> wrote:
> >
> > And you never noticed that the complaints I had about the dcache bits
> > didn't make sense and how I said it should work was how it actually does
> > work? Heh.
> 
> That's a funny way of saying
> 
>   "Oh, Linus, you were right in the first place when you called me out
> on my bullshit"

You started out going off about how filesystem developers don't know how
Unicode works, and when I brought up the dcache all you had to say was
how wrong I was.

Sorry, I'm not going to give you credit for being "right" when you're
just trying to play gotcha.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Patrick Donnelly]

Hello,

I'm one of the maintainers of the Ceph file system (CephFS). I
recently introduced case-insensitive directory trees into CephFS to
support performance improvements for Samba. Perhaps my experience
would add to this timely discussion.

[

A brief context/background on that effort for those interested:

CephFS has an inherited (at mkdir) metadata on directories which adds
"normalization" (string: unicode normalization type) or
"casesensitive" (bool) which permanently affects how dentries are
looked up. The directory must be empty and free of snapshots to change
this metadata ("charmap").

Clients with support for this feature will perform a mapping [1] from
the application (userspace libcephfs or ceph-fuse) path namespace to
the MDS (metadata server) path namespace during a path walk or lookup.
For affected directories, the MDS namespace is the normalized and
possibly case-folded name for each dentry. The MDS also stores an
uninterpreted "alternate_name" with each dentry that is the original
name from the application namespace used to create the dentry. The
alternate_name is **only** visible via file system operations that
expose dentry names to the application, readdir/getcwd [2].

Benefits I identified for this approach were:

- The core file system (mainly: MDS) paths were virtually unchanged.
The MDS does not care about case sensitivity or normalization. It uses
what the client gave it for the dentry name.
- It's the client's job to perform any namespace mapping and store
metadata in alternate_name to reverse the mapping (i.e. get the
original dentry name used to create the dentry).
- The Client's cache uses the same file system namespace as the MDS:
dentry names are normalized/case-folded. The transformation is only
applied during path walk / lookup with user-supplied paths/names.

We use libicu (indirectly through boost) for actually doing the
normalization / casefolding. It's simple [3]. It works. Despite your
(Linus) objections to this in prior postings, I do not see this as
problematic. There are backwards compatibility guarantees in the
standard [4].  Does that mean mistakes can't happen? No. Certainly
there could be a backwards-compatibility breakage where we have two
physical dentries with names that should be equivalent: one dentry
shadows the other for some clients with upgraded Unicode tables. Even
so, I do not see this as significant barrier to adopting the Unicode
routines. In my opinion, the real danger is a file system person
foolishly thinking they know best by rolling their own mapping table
and discovering why that's a terrible idea. I think this thread
illustrates that in several places.

]

On Fri, Apr 25, 2025 at 11:41 PM Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> On Fri, 25 Apr 2025 at 20:09, Kent Overstreet <kent.overstreet@linux.dev> wrote:
> >
> > The subject is CI lookups, and I'll eat my shoe if you wrote that.
>
> Start chomping. That nasty code with d_compare and d_hash goes way back.
>
> From a quick look, it's from '97, and got merged in in 2.1.50. It was
> added (obviously) for FAT. Back then, that was the only case that
> wanted it.
>
> I don't have any archives from that time, and I'm sure others were
> involved, but that whole init_name_hash / partial_name_hash /
> end_name_hash pattern in 2.1.50 looks like code I remember. So I was
> at least part of it.
>
> The design, if you haven't figured it out yet, is that filesystems
> that have case-independent name comparisons can do their own hash
> functions and their own name comparison functions, exactly so that one
> dentry can match multiple different strings (and different strings can
> hash to the same bucket).
>
> If you get dentry aliases, you may be doing something wrong.

I would not consider myself a kernel developer but I assume this
terminology (dentry aliases) refers to multiple dentries in the dcache
referring to the same physical dentry on the backing file system?

If so, I can't convince myself that's a real problem. Wouldn't this be
beneficial because each application/process may utilize a different
name for the backing file system dentry? This keeps the cache hot with
relevant names without any need to do transformations on the dentry
names. Happy to learn otherwise because I expected this situation to
occur in practice with ceph-fuse. I just tested and the dcache entries
(/proc/sys/fs/dentry-state) increases as expected when performing case
permutations on a case-insensitive file name. I didn't observe any
cache inconsistencies when editing/removing these dentries. The danger
perhaps is cache pollution and some kind of DoS? That should be a
solvable problem but perhaps I misunderstand some complexity.

> Also, originally this was all in the same core dcache lookup path. So
> the whole "we have to check if the filesystem has its own hash
> function" ended up slowing down the normal case. It's obviously been
> massively modified since 1997 ("No, really?"), and now the code is
> very much set up so that the straight-line normal case is all the
> non-CI cases, and then case idnependence ends up out-of-line with its
> own dcache hash lookup loops so that it doesn't affect the normal good
> case.

It's seems to me this is a good argument for keeping case-sensitivity
awareness out of the dcache. Let the fs do the namespace mapping and
accept that you may have dentry aliases.

FWIW, I also wish we didn't have to deal with case-sensitivity but we
have users/protocols to support (as usual).

[1] https://github.com/ceph/ceph/blob/ebb2f72bfc37577d5389809ba0c16fca032acd8a/src/client/Client.cc#L7732-L7735
[2] https://github.com/ceph/ceph/blob/ebb2f72bfc37577d5389809ba0c16fca032acd8a/src/client/Client.cc#L1353
[3] https://github.com/ceph/ceph/blob/ebb2f72bfc37577d5389809ba0c16fca032acd8a/src/client/Client.cc#L1299-L1340
[4] https://unicode.org/reports/tr15/#Versioning

Kind regards,

--
Patrick Donnelly

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Kent Overstreet]

On Tue, Apr 29, 2025 at 11:36:44AM -0400, Patrick Donnelly wrote:
> I would not consider myself a kernel developer but I assume this
> terminology (dentry aliases) refers to multiple dentries in the dcache
> referring to the same physical dentry on the backing file system?

This issue turned out to be my own pebcak; I'd missed the
dentry_operations that do normalized lookups (to be fair, they were
rather hidden) and I'd just pulled a 14 hour day so was a tad bitchy
about it on the list.

> If so, I can't convince myself that's a real problem. Wouldn't this be
> beneficial because each application/process may utilize a different
> name for the backing file system dentry? This keeps the cache hot with
> relevant names without any need to do transformations on the dentry
> names. Happy to learn otherwise because I expected this situation to
> occur in practice with ceph-fuse. I just tested and the dcache entries
> (/proc/sys/fs/dentry-state) increases as expected when performing case
> permutations on a case-insensitive file name. I didn't observe any
> cache inconsistencies when editing/removing these dentries. The danger
> perhaps is cache pollution and some kind of DoS? That should be a
> solvable problem but perhaps I misunderstand some complexity.

Dentry aliases are fine when they're intended, they're properly
supported by the dcache.

The issue with caching an alias for the un-normalized lookup name is
(as you note) that by permuting the different combinations of upper and
lower case characters in a filename, userspace would be able to create
an unbounded (technically, exponential bound in the length of the
filename) number of aliases, and that's not what we want.

(e.g. d_prune_aliases processes the whole list of aliases for an inode
under a spinlock, so it's an easy way to produce unbounded latencies).

So it sounds like you probably didn't find the dentry_operations for
normalized lookups, same as me.

Have a look at generic_set_sb_d_ops().

> > Also, originally this was all in the same core dcache lookup path. So
> > the whole "we have to check if the filesystem has its own hash
> > function" ended up slowing down the normal case. It's obviously been
> > massively modified since 1997 ("No, really?"), and now the code is
> > very much set up so that the straight-line normal case is all the
> > non-CI cases, and then case idnependence ends up out-of-line with its
> > own dcache hash lookup loops so that it doesn't affect the normal good
> > case.
> 
> It's seems to me this is a good argument for keeping case-sensitivity
> awareness out of the dcache. Let the fs do the namespace mapping and
> accept that you may have dentry aliases.
> 
> FWIW, I also wish we didn't have to deal with case-sensitivity but we
> have users/protocols to support (as usual).

The next issue I'm looking at is that the "keep d_ops out of the
fastpath" only works if case sensitivity isn't enabled on the filesystem
as a whole - i.e. if case sensitivity is enabled on even a single
directory, we'll be flagging all the dentries to hit the d_ops methods.

dcache.c doesn't check IS_CASEFOLD(inode) - d_init can probably be used
for this, but we need to be careful when flipping casefolding on and off
on an (empty) directory, there might still be cached negative dentries.

ext4 has a filesystem wide flag for "case sensitive directories are
allowed", so that enables/disables that optimization. But bcachefs
doesn't have that kind of filesystem level flag, and I'm not going to
add one - that sort of "you have to enable this option to have access to
this other option" is a pita for end users.

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[Patrick Donnelly]

On Tue, Apr 29, 2025 at 12:21 PM Kent Overstreet
<kent.overstreet@linux.dev> wrote:
>
> On Tue, Apr 29, 2025 at 11:36:44AM -0400, Patrick Donnelly wrote:
> > I would not consider myself a kernel developer but I assume this
> > terminology (dentry aliases) refers to multiple dentries in the dcache
> > referring to the same physical dentry on the backing file system?
>
> This issue turned out to be my own pebcak; I'd missed the
> dentry_operations that do normalized lookups (to be fair, they were
> rather hidden) and I'd just pulled a 14 hour day so was a tad bitchy
> about it on the list.
>
> > If so, I can't convince myself that's a real problem. Wouldn't this be
> > beneficial because each application/process may utilize a different
> > name for the backing file system dentry? This keeps the cache hot with
> > relevant names without any need to do transformations on the dentry
> > names. Happy to learn otherwise because I expected this situation to
> > occur in practice with ceph-fuse. I just tested and the dcache entries
> > (/proc/sys/fs/dentry-state) increases as expected when performing case
> > permutations on a case-insensitive file name. I didn't observe any
> > cache inconsistencies when editing/removing these dentries. The danger
> > perhaps is cache pollution and some kind of DoS? That should be a
> > solvable problem but perhaps I misunderstand some complexity.
>
> Dentry aliases are fine when they're intended, they're properly
> supported by the dcache.
>
> The issue with caching an alias for the un-normalized lookup name is
> (as you note) that by permuting the different combinations of upper and
> lower case characters in a filename, userspace would be able to create
> an unbounded (technically, exponential bound in the length of the
> filename) number of aliases, and that's not what we want.
>
> (e.g. d_prune_aliases processes the whole list of aliases for an inode
> under a spinlock, so it's an easy way to produce unbounded latencies).

Well, if aliases are "supported" by the dcache, that seems like a bug to me.

> So it sounds like you probably didn't find the dentry_operations for
> normalized lookups, same as me.

I didn't look to begin with. :)

> Have a look at generic_set_sb_d_ops().
>
> > > Also, originally this was all in the same core dcache lookup path. So
> > > the whole "we have to check if the filesystem has its own hash
> > > function" ended up slowing down the normal case. It's obviously been
> > > massively modified since 1997 ("No, really?"), and now the code is
> > > very much set up so that the straight-line normal case is all the
> > > non-CI cases, and then case idnependence ends up out-of-line with its
> > > own dcache hash lookup loops so that it doesn't affect the normal good
> > > case.
> >
> > It's seems to me this is a good argument for keeping case-sensitivity
> > awareness out of the dcache. Let the fs do the namespace mapping and
> > accept that you may have dentry aliases.
> >
> > FWIW, I also wish we didn't have to deal with case-sensitivity but we
> > have users/protocols to support (as usual).
>
> The next issue I'm looking at is that the "keep d_ops out of the
> fastpath" only works if case sensitivity isn't enabled on the filesystem
> as a whole - i.e. if case sensitivity is enabled on even a single
> directory, we'll be flagging all the dentries to hit the d_ops methods.
>
> dcache.c doesn't check IS_CASEFOLD(inode) - d_init can probably be used
> for this, but we need to be careful when flipping casefolding on and off
> on an (empty) directory, there might still be cached negative dentries.
>
> ext4 has a filesystem wide flag for "case sensitive directories are
> allowed", so that enables/disables that optimization. But bcachefs
> doesn't have that kind of filesystem level flag, and I'm not going to
> add one - that sort of "you have to enable this option to have access to
> this other option" is a pita for end users.

In CephFS it's as simple as setting an extended attribute on a
directory, by admins.

-- 
Patrick Donnelly

Re: [GIT PULL] bcachefs fixes for 6.15-rc4

[pr-tracker-bot]

The pull request you sent on Thu, 24 Apr 2025 22:46:40 -0400:

> git://evilpiepirate.org/bcachefs.git tags/bcachefs-2025-04-24

has been merged into torvalds/linux.git:
https://git.kernel.org/torvalds/c/eef0dc0bd432885b2bd4fc7f410ed039bf028e37

Thank you!

-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/prtracker.html