Working with UTF-8 in the Kernel
lwn.net
lwn.net
edit to add: I don't think I ever noticed Android being case-insensitive. Always something new to learn!
A few years ago I made the mistake of formatting my Mac to use a case-sensitive filesystem, and it turned out to be a huge mistake. My thought process was "I want full compatibility with Unix-land", but this wasn't in line with the rest of the Mac conventions and just ended up causing pain.
If the main reason for this change is to make end-users lives easier then the solution requires two userspace parts.
1) When creating a new filename, check to see if it collides in a case insensitive way.
2) A 'filename validation' tool that scans for filenames that are not normalized in a desired way, and also for case insensitive collisions.
BOTH of these tasks should be OPTIONAL and entirely in userspace.
In user space you can knock yourself out with localised search applications.
Kernel space? You have to worry about reliability, and backwards compatibility, and people trying to exploit your code.
1. It’s slow – every time you want to create a file, you have to do an O(n) enumeration of every file in the current directory to see if any of them collide with your new filename. A kernel implementation can use the normalized, case-folded form of each filename for its hash in the dentry cache, and then look things up in O(1) based on that hash. You could try to maintain a similar cache in some userland daemon, but it would break if anyone changed the files without going through that daemon, creating a mismatch between the userland cache and the actual file system state. If you want to accommodate arbitrary modifications by other processes, you have to go to the kernel every time.
2. It’s inherently racy. If you (1) list the directory to check for existing colliding files, find none, and then (2) create a new file, another process might have created a file with a colliding (but not byte-equal) name in the interval between (1) and (2). That wouldn’t be an issue if we had transactional filesystems or even just better filesystem-based concurrency APIs, but in Linux like most other OSes, we can’t have such nice things. You could avoid the race by either making all filesystem accesses go through a daemon, or making up a locking protocol where you have to grab an advisory lock on a hidden file or something. But those solutions have the same flaw as the last paragraph – they only work if all processes writing to the filesystem are on board. They also add a lot of complexity.
A partial alternative is to just accept the race as a possibility; clients could check for collisions after creating a file, and if they found one, delete the file they just created. That’s arguably good enough for most use cases, but it’s sure ugly to add the edge case of a transient broken state, when the point of keeping insensitivity in userland is to avoid ugliness. And what if a process crashes between creating a colliding file and deleting it?
2.5. And of course a non-case-insensitivity-aware process could just create two conflicting files on its own. I’m not counting this as a third problem since I’ve already raised the issue of unaware processes and ugly edge cases in the first two, and you did mention there could be a validation tool. But I rather dislike the idea that accessing your files using standard Unix tools would be “risky”, in that you could accidentally create files with names that case-insensitivity-aware programs couldn’t handle. As I see it, that essentially relegates the Unix tools to being second-class citizens.
Given these issues, I think it really is best to handle case insensitivity in the kernel, no matter how ugly it seems. Either that, or make FUSE faster so you can do it in a userland filesystem without sacrificing performance…
Edited to add this paragraph: I feel I should expand on the above line. It's actually the reason why most of the post this is replying to is invalid. Outside of the single thread context __all__ caches are potentially invalid, even the in-kernel cache could be invalidated between different submissions. So all clients have to be coded to accept a 'fail' case and behave properly anyway, OR you allow for one to 'win'. This is why (man 2 open) open() has been extended over time to include the O_EXCL flag for failing in the case of a file already existing. Similarly the (man 2 rename) rename() has been extended (fairly recently) with RENAME_NOREPLACE, which fails in the case of the file already existing. Anything which might be subject to concurrency issues already requires such handling, or accepting that the results might be undefined (E.G. one version of the rename to target filename working in an 'atomic' way but no assurance about the ordering of operations from parallel threads/processes).
Anything not facing a user should already be creating filenames in it's preferred case and normalization.
Anything facing the user (accepting user input as a filename) should either be doing the same (if it's part of a sanitized filename) OR is directly part of a UI interacting with a user, which must already handle cases such as renaming an existing file to one that might also exist.
I really don't buy that anything of actual value is being gained here for use cases that seem very rare and a complexity cost in kernel that is very high.
The kernel is in a better position; since all readers and writers must go through the kernel's filesystem routines, those routines can use mutexes or other concurrency mechanisms (that they need anyway to protect their data structures) to implement higher-level atomic semantics. That's how the kernel implements regular O_EXCL, and it's how it can implement case-insensitive O_EXCL as well, without having to deal with race conditions. In fact it already does that for vfat and other case-insensitive filesystems.
(A FUSE filesystem similarly gatekeeps all accesses and thus can do the job in userspace, but FUSE is slow.)
So leave O_EXCL in the kernel in its current case-sensitive form. In userspace, implement normalization and case-folding as you see fit and pass the normalized, case-folded filename to open(). Ignore any files other programs may create with non-normalized names. Keep an xattr or lookup table with the unfolded "presentation" version of the name for directory listings.
int utf8byte(struct utf8cursor *u8c);
What's the choice behind going byte-by-byte rather than grapheme-by-grapheme? Seems like an API designed for comparisons and nothing else…
There's your answer: that's all the kernel needs to do with strings.
https://manishearth.github.io/blog/2017/01/15/breaking-our-l...
One option would to instead return (24-bit) code points, which would amortize comparison and iteration costs slightly, but may accidentally encourage people to forget about multiple-codepoint characters.
[0]: https://r12a.github.io/uniview/?charlist=%F0%9F%91%A9%E2%80%...
I take it's not possible to return a pointer into the data because normalization is being performed?
int utf8byte(char*)
utf8 iterators proved to be wrong in a myriad of previous cases, e.g. libunistring which is still not used in coreutils over this wrong design decision. You do the whole high-level API in buffers by yourself and don't do it with exposed iterators.
casefolding and normalization is only one of the expected features, the next would be identifier safety, which requires a bit more checks. left to right R2L mixups, script mixups, confusables ... The kernel deals with identifiable strings and once you open the unicode floodgates others will rush in. You really need to think the API through, not like this. At least they thought about the UNICODE_VERSION, which others didn't.
Ugh, why? I thought the general consensus was that case-insensitive filesystems were a mistake. The article linked on that line is behind a paywall, can someone summarize the rationale for this change?
Also, this article doesn't mention how the kernel developers plan to handle differences in case folding between locales (e.g. the infamous Turkish "dotted I"). I learned recently that NTFS actually stores a full case-folding table (from the current locale of the system formatting the volume) in the filesystem metadata specifically to ensure case-folding will remain consistent even if the volume is attached to a system with a different locale which seems like the only sane way to handle this.
LWN is super great, consider subscribing :-) ;-)
I remember finding the underlying reasoning fairly compelling for non-technical, or more Windows familiar, users - but my memory might be hazy...
Where did you get that idea? Case-senstivity is NEVER the right answer. Never, never. NeVer.
The following arguments for case-sensitivity come to mind:
- Different locales treat uppercasing and lowercasing differently. In Turkish, for instance, the dotted and dotless letter I are two different letters, unlike languages where dotless uppercase I corresponds to dotted lowercase i. https://en.wikipedia.org/wiki/Dotted_and_dotless_I
- There are common codebases that have files that differ only in case - for instance, the Linux kernel source tree itself has include/uapi/linux/netfilter/xt_rateest.h and include/uapi/linux/netfilter/xt_RATEEST.h with different contents.
Can you supply some arguments against case-sensitivity?
The only time that English is case-sensitive is when you want to distinguish between a proper noun and a similarly-spelled word, like rich and Rich. But that hardly ever matters for identifiers, which is what file names are.
And "never," your original claim, is not "hardly ever," your revised claim. If there are valid use cases for case-sensitive filenames, it seems like it should be allowed on robustness-principle grounds, even if they are rare, unless they impose some disproportionate cost on users of the system.
And filenames don't have to be in English, and usually aren't. "geofft" is not an English word; neither is "usr" or "etc" or "tmp," let alone "xt_RATEEST.h" or "/tmp/tmp.CGZ8Lq5f".
And even for common nouns in English, case matters - the UCC for instance requires certain text to be "conspicuous," and gives one example as "a heading in capitals equal to or greater in size than the surrounding text." It's pretty common for lawyers to write "conspicuous" text in all caps to satisfy this requirement. In these cases, you do want to distinguish between "never," "Never," and "NEVER".
$ echo asdf > Foo
$ cat foo
asdf
....
PARDON?
Besides, the point of a filesystem isn't to have opinions on right or wrong. It's to store files.
In other words, the fact that capitalization actually matters in English on occasion is a bug, not a feature.
In the comment you replied to you've just been given a critical example, and it seems like you ignored it to talk just about English.
Get a Turk and an Englishman (maybe have them walk into a bar). Show them the letter I and say, "what is the lowercase of this?" They give you different answers.
So what should your kernel do about open("I.txt", O_RDONLY), when the directory entry has it as "i.txt"? Tell the Turk ENOENT, and give the Englishman a file descriptor? What happens when the user changes languages and has a filename stored somewhere? I would argue it's not the right layer to solve the problem.
At any rate, I recognize you disagree with this, but there's something to be said for the filesystem to be a bag of bytes that doesn't care about any of this. Let higher-level, more user-facing pieces concern themselves with it. They're much more likely to know more about the end user's expectations than ext4.
No, not folded in. I don't know how I would solve the problem of identical glyphs. It's a very hard problem.
> there's something to be said for the filesystem to be a bag of bytes that doesn't care about any of this
Fair enough.
I primarily use a Mac, and I don't think I've ever taken advantage of the case insensitivity. The only time I open files is by choosing them graphically or by tab-completing their names in my terminal or my editor.
The fact that case insensitivity is implemented at the filesystem layer rather than higher up means that my shell is still case sensitive, so I can't type "m<tab>" to autocomplete "Makefile" -- I have to type "M<tab>" instead.
Things like Spotlight or my IDE, on the other hand, implement their own case-insensitive filename search that works fine regardless of whether the underlying filesystem is case-insensitive or not.
Many shells can do case-insensitive autocomplete. For example, in bash (https://askubuntu.com/a/87066):
set completion-ignore-case On
set autolist = ambiguous
set complete = enhanceIn this case, I'd argue that Unicode should provide codepoints for Turkish-specific versions of these letters (or at the very least a separate codepoint for a capitalized version of a dotless 'i', such that it can always be assumed that the Latin uppercase I is meant to be dotted and can be displayed as such when using a Turkish locale). Alternately, the Turkish alphabet should have its own Unicode codepoints entirely, thus circumventing this issue (just like how Latin A != Cyrillic А != Greek Α).
> the Linux kernel source tree itself has include/uapi/linux/netfilter/xt_rateest.h and include/uapi/linux/netfilter/xt_RATEEST.h with different contents.
That's a rather horrific code smell, and I'm surprised Linus didn't chew someone out on the LKML over it. If they have different contents, then they should have meaningfully-different names (in this case, maybe xt_rateest_target.h v. xt_rateest_match.h?). It looks like there might be other files there with the same issue, and they should be fixed, too (as should any other files that reference those headers).
Like, just because it's possible to stick the barrel of a loaded 12-gauge in your mouth doesn't mean it's a good idea to do so.
The point of software is to deal with the world as it is, not as it should be. We've got pseudocode and research papers for the world as it should be.
I'll agree though, having the filesystem do case folding according to some locale is ... bad in general. But as a rarely-enabled option on linux systems just for this purpose, maybe it's not that bad.
This also applies to games where the modding community primarily uses Windows and thus has zero concept of case consistency (I recall this being a major issue at one point - if not still - for the Linux ports of the recent Civ games).
If we add "display" and "locale" field to the directory entry my office app would write out "bob's great spreadsheet.xls" and add some extended attributes like display="Bob's Great Spreadsheet" and locale="en-US".