3 ms·
Checking for collisions in userspace is what Samba does, and maybe Android as well (I know they currently use something based on wrapfs based on FUSE, but not s
by comex 8y ago
Checking for collisions in userspace is what Samba does, and maybe Android as well (I know they currently use something based on wrapfs based on FUSE, but not sure how exactly it works). It has two big problems:
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…
- jakeogh 8y agoWhy make concessions for bad decisions on the Android and Windows side?
- comex 8y agoAnd just not have case insensitivity? Fine by me. I'm only arguing about where case insensitivity should be implemented in the case that you do want it.
- mjevans 8y agoFor a multi-threaded system I don't actually see how any of that is solved by moving things that SHOULD NOT belong in the kernel to the kernel. 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.
- comex 8y agoO_EXCL and RENAME_NOREPLACE are examples of why you want case insensitivity to be in the kernel. They're atomic operations: if you use O_EXCL, you could get a successful file creation, or you could get EEXIST, but not something in between. But you can't implement a case insensitive version of O_EXCL in userland. As I said, the best you can do is scan first to see whether a conflicting file already exists, but that doesn't help if a conflicting file is created in between the scan and when you create your file. 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.)