5 ms·

Why Unix kernels have grown caches for directory entries ('name caches')

73 points by pabs3 3y ago

deathanatos 3y ago
(Note that everything in the sidebar is about "conventional Unix".) > A directory in a conventional Unix filesystem has either one name or no name (if it's been removed). Because of this, the kernel's name cache can always know the directory's current name if it has one. If it wants to, the name cache can go further and provide the last name that the directory was known by before it was deleted, along with a mark that it was deleted. In Linux, you can end up with directories having different names via bind-mounting one path to another, or via two processes having different mount namespaces. IDK if you count inside/outside a chroot as "different" or not. > A file can have no name (if it's been removed since it was opened or mmap()'d), it can have one name, or it can have several names because there are several hardlinks to it. Because of this the kernel name cache may not necessarily know the current name of an open file. If it started out having multiple hardlinks, was opened through one hardlink, and then that hardlink was removed, the name cache may not know the name of the other remaining hardlink(s). It can also have no name if it was simply never given one; on Linux you can open a file without ever linking it, essentially. (See open(2), the O_TMPFILE flag.) Usually for the same semantics as the deleted tempfile (hence the name), just atomic. I sort of wish it was in there from the beginning, as it is what I think the atomic rename to write a file pattern should really look like in the common case: 1. create the file via open(2) with no name. 2. write the contents 3. atomically link the file with rename's atomic replace semantics That avoids the ugliness of the file needing some temporary name at all. (Note that these files are disk-backed: the open call takes a directory which essentially becomes the backing FS for the data.) There's also memfd_create(2), which is like the in-memory version of the above. You can't link those. (Yet…? if you had an in-memory FS … IDK, maybe it could make sense…? how much do you like plan9?)
- yjftsjthsd-h 3y ago
  I wonder what happens if you violate the 0 xor 1 rule by hard linking a directory - it is strongly discouraged for very good reasons but was at least historically possible ( https://askubuntu.com/questions/210741/why-are-hard-links-not-allowed-for-directories https://askubuntu.com/questions/210741/why-are-hard-links-no... comments discuss a bit in between the dire warnings). Or maybe it's not possible on newer systems that have such a cache?
  - bombcar 3y ago
    Apple allows hard linking directories (I believe it is used for Time Machine somehow): https://jameshunt.us/writings/linking-dirs-in-macos/ https://jameshunt.us/writings/linking-dirs-in-macos/
    - stouset 3y ago
      Is that true on APFS? I know they added it to HFS+ for Time Machine, but I’d assumed it’s no longer necessary (or possible) with the newer filesystem that allows for real snapshots.
      - comex 3y ago
        It’s no longer possible.
    - trws 3y ago
      I miss this in the days of APFS actually. As much as it’s potentially dangerous, in a system without bind mounts readily available it really was sometimes the best solution to a problem. Mainly used it to allow various directories that couldn’t be moved to be re-homed, looking at you OneDrive.
  - Ericson2314 3y ago
    You can do it with FUSE I'm pretty sure
    - eru 3y ago
      Yes. I've done that (but only on immutable filesystems, where it's not (much of?) a problem).
      - yjftsjthsd-h 3y ago
        Being ro helps with deleting directories (by preventing it, but w/e), but cyclical links would be bad regardless. Granted, it's the kind of thing that's probably okay if you know what you're doing well enough to avoid the footguns... but I have no experience, so can't say for sure.
- DeathArrow 3y ago
  Linux is not UNIX. It is a UNIX clone up to a point.
  - deathanatos 3y ago
    … which is why I led the comment with, > (Note that everything in the sidebar is about "conventional Unix".) The OP isn't wrong (AFAIK), but most people are also not using OG Unix.
  - dfox 3y ago
    While Linux is not derived from the original Unix codebase it is probably the nearest thing to UNIX in the sense of Single UNIX Specification that you can find.
    - DeathArrow 3y ago
      What about macOS, BSD?
      - dfox 3y ago
        There are various (albeit notionally optional) parts of POSIX that are either not implemented at all or implemented in surprising ways on BSD derived systems. For example, macOS does not implement sem_init() at all, while OpenBSD sem_init(3) man page stilll says that "This is perhaps a stretch of the intention of POSIX, but is compliant, with the caveat that sem_init() always reports a permissions error when an attempt to create a shared semaphore is made." (that wording was at one time present in most BSDs, but both current NetBSD and FreeBSD seem to not have that limitation).
tedunangst 3y ago
There may also be a 31 character limit on cached names, so spamming stat("long-uuid-unicorn-happy-fun-zone") could be slower than expected.
- NavinF 3y ago
  Wtf. Is this documented or benchmarked anywhere?
Ericson2314 3y ago
This seems to be conflating caching the contents of directories and caching the names of files. One is perfectly fine. One relies on sketchy invariants that I fine distasteful.
- cryptonector 3y ago
  Yes. There's the-kernel-knows-open-files'-names and the-kernel-has-a-cache-of-absolute-paths and the-kernel-has-a-cache-for-in-core-directories. There's a large variety of ways to do this with one or multiple caches.
  - Ericson2314 3y ago
    I am a capsicum true believer who wants to use file descriptors for everything, and hardlink directories all day.
jmmv 3y ago
> Because of this the kernel name cache may not necessarily know the current name of an open file. If it started out having multiple hardlinks, was opened through one hardlink, and then that hardlink was removed, the name cache may not know the name of the other remaining hardlink(s). I found this the hard way when implementing a FUSE file system for macOS that required knowing the “real path” of a file and that faked “hard links” for performance reasons. It was super hard to diagnose and I’m still not sure if there is a solution to the problem I faced. If you are curious, the details of the story are here: https://jmmv.dev/2020/01/osxfuse-hardlinks-dladdr.html https://jmmv.dev/2020/01/osxfuse-hardlinks-dladdr.html
the8472 3y ago
Which is also one of the reasons why WSL1 was so slow. Windows lacks this cache so programs doing unixy filesystem access patterns perform poorly there.
- dspillett 3y ago
  The biggest reason for that for many complex processes is that creating a new process (and tearing one down after use) is relatively expensive under Windows. Under Linux (and Unix-a-like OSs generally) creating a process isn't much slower that creating a thread in an existing process, so child processes tend to get used with relative abandon – when an application or script running this way get used under WSL1 (or other wrapping layers over Windows like Cygwin) they were much slower than in their more native environments. It goes hand-in-hand with unix-y filesystem access patterns: creating temporary files and named pipes all over the place as the cost is relatively low. This is also why Unix targetted servers tended to use multi-process models rather than threaded ones: if there is little performance advantage in creating threads, and you don't need the more performant IPC that they offer (not actually IPC: they offer in-process data sharing), the relative simplicity of spawning process makes them more attractive. This has changed a bit over time though: the ubiquity of multi-core CPUs and changes in scheduling practices & such to take better advantage of them has made threads a bit more attractive than they once were under Unix-a-likes too (even when you still don't need the in-process data sharing).
  - aseipp 3y ago
    WSL1 did not use the NT codepath in order to spawn processes. WSL1 had its own direct support in the kernel for its own process type ("nanoprocess" is what they called it IIRC) managed independently from NT processes; and it even supported features/APIs for them that NT ones did not have, such as a compatible fork() call
    - dspillett 3y ago
      IIRC that support was still noticeably heavier than starting a thread. Much faster than the unix-y fork() emulation in cygwin/msys/similar, or in things more directly ported to Windows that use native fork equivalents directly, but still not closing the thread/process efficiency difference to that seen away from Windows. This performance difference was one of the reasons (though I think a minor one) that they switched to a managed VM instead of an emulation layer for WSL2.
mackman 3y ago
I’ve been doing development on AIX recently and the lack of such a cache has proven a real pain necessitating implementing our own disk scan and cache. Not knowing the path to an open file or process in constant time is terrible. If anyone here happens to be an expert on AIX and has suggestions please speak up!
- pi-e-sigma 3y ago
  AIX kernel has an inode cache, stat cache and directory name caches though. There's procfiles command to show inodes open by a given process and istat command that can link the i-nodes back to the file names. There is also available lsof command ported from linux. You could also trace system calls of these tools to see what exactly they are doing and replicate it in your app
  - mackman 3y ago
    I read through lsof source. It doesn’t provide paths for regular files. Even emailed the author to confirm.

73 points by pabs3 3y ago

(Note that everything in the sidebar is about "conventional Unix".) > A directory in a conventional Unix filesystem has either one name or no name (if it's been removed). Because of this, the kernel's name cache can always know the directory's current name if it has one. If it wants to, the name cache can go further and provide the last name that the directory was known by before it was deleted, along with a mark that it was deleted. In Linux, you can end up with directories having different names via bind-mounting one path to another, or via two processes having different mount namespaces. IDK if you count inside/outside a chroot as "different" or not. > A file can have no name (if it's been removed since it was opened or mmap()'d), it can have one name, or it can have several names because there are several hardlinks to it. Because of this the kernel name cache may not necessarily know the current name of an open file. If it started out having multiple hardlinks, was opened through one hardlink, and then that hardlink was removed, the name cache may not know the name of the other remaining hardlink(s). It can also have no name if it was simply never given one; on Linux you can open a file without ever linking it, essentially. (See open(2), the O_TMPFILE flag.) Usually for the same semantics as the deleted tempfile (hence the name), just atomic. I sort of wish it was in there from the beginning, as it is what I think the atomic rename to write a file pattern should really look like in the common case: 1. create the file via open(2) with no name. 2. write the contents 3. atomically link the file with rename's atomic replace semantics That avoids the ugliness of the file needing some temporary name at all. (Note that these files are disk-backed: the open call takes a directory which essentially becomes the backing FS for the data.) There's also memfd_create(2), which is like the in-memory version of the above. You can't link those. (Yet…? if you had an in-memory FS … IDK, maybe it could make sense…? how much do you like plan9?)

yjftsjthsd-h 3y ago
I wonder what happens if you violate the 0 xor 1 rule by hard linking a directory - it is strongly discouraged for very good reasons but was at least historically possible ( https://askubuntu.com/questions/210741/why-are-hard-links-not-allowed-for-directories https://askubuntu.com/questions/210741/why-are-hard-links-no... comments discuss a bit in between the dire warnings). Or maybe it's not possible on newer systems that have such a cache?
- bombcar 3y ago
  Apple allows hard linking directories (I believe it is used for Time Machine somehow): https://jameshunt.us/writings/linking-dirs-in-macos/ https://jameshunt.us/writings/linking-dirs-in-macos/
  - stouset 3y ago
    Is that true on APFS? I know they added it to HFS+ for Time Machine, but I’d assumed it’s no longer necessary (or possible) with the newer filesystem that allows for real snapshots.
    - comex 3y ago
      It’s no longer possible.
  - trws 3y ago
    I miss this in the days of APFS actually. As much as it’s potentially dangerous, in a system without bind mounts readily available it really was sometimes the best solution to a problem. Mainly used it to allow various directories that couldn’t be moved to be re-homed, looking at you OneDrive.
- Ericson2314 3y ago
  You can do it with FUSE I'm pretty sure
  - eru 3y ago
    Yes. I've done that (but only on immutable filesystems, where it's not (much of?) a problem).
    - yjftsjthsd-h 3y ago
      Being ro helps with deleting directories (by preventing it, but w/e), but cyclical links would be bad regardless. Granted, it's the kind of thing that's probably okay if you know what you're doing well enough to avoid the footguns... but I have no experience, so can't say for sure.
DeathArrow 3y ago
Linux is not UNIX. It is a UNIX clone up to a point.
- deathanatos 3y ago
  … which is why I led the comment with, > (Note that everything in the sidebar is about "conventional Unix".) The OP isn't wrong (AFAIK), but most people are also not using OG Unix.
- dfox 3y ago
  While Linux is not derived from the original Unix codebase it is probably the nearest thing to UNIX in the sense of Single UNIX Specification that you can find.
  - DeathArrow 3y ago
    What about macOS, BSD?
    - dfox 3y ago
      There are various (albeit notionally optional) parts of POSIX that are either not implemented at all or implemented in surprising ways on BSD derived systems. For example, macOS does not implement sem_init() at all, while OpenBSD sem_init(3) man page stilll says that "This is perhaps a stretch of the intention of POSIX, but is compliant, with the caveat that sem_init() always reports a permissions error when an attempt to create a shared semaphore is made." (that wording was at one time present in most BSDs, but both current NetBSD and FreeBSD seem to not have that limitation).

tedunangst 3y ago

There may also be a 31 character limit on cached names, so spamming stat("long-uuid-unicorn-happy-fun-zone") could be slower than expected.

NavinF 3y ago
Wtf. Is this documented or benchmarked anywhere?

Ericson2314 3y ago

This seems to be conflating caching the contents of directories and caching the names of files. One is perfectly fine. One relies on sketchy invariants that I fine distasteful.

cryptonector 3y ago
Yes. There's the-kernel-knows-open-files'-names and the-kernel-has-a-cache-of-absolute-paths and the-kernel-has-a-cache-for-in-core-directories. There's a large variety of ways to do this with one or multiple caches.
- Ericson2314 3y ago
  I am a capsicum true believer who wants to use file descriptors for everything, and hardlink directories all day.

jmmv 3y ago

> Because of this the kernel name cache may not necessarily know the current name of an open file. If it started out having multiple hardlinks, was opened through one hardlink, and then that hardlink was removed, the name cache may not know the name of the other remaining hardlink(s). I found this the hard way when implementing a FUSE file system for macOS that required knowing the “real path” of a file and that faked “hard links” for performance reasons. It was super hard to diagnose and I’m still not sure if there is a solution to the problem I faced. If you are curious, the details of the story are here: https://jmmv.dev/2020/01/osxfuse-hardlinks-dladdr.html https://jmmv.dev/2020/01/osxfuse-hardlinks-dladdr.html

the8472 3y ago

Which is also one of the reasons why WSL1 was so slow. Windows lacks this cache so programs doing unixy filesystem access patterns perform poorly there.

dspillett 3y ago
The biggest reason for that for many complex processes is that creating a new process (and tearing one down after use) is relatively expensive under Windows. Under Linux (and Unix-a-like OSs generally) creating a process isn't much slower that creating a thread in an existing process, so child processes tend to get used with relative abandon – when an application or script running this way get used under WSL1 (or other wrapping layers over Windows like Cygwin) they were much slower than in their more native environments. It goes hand-in-hand with unix-y filesystem access patterns: creating temporary files and named pipes all over the place as the cost is relatively low. This is also why Unix targetted servers tended to use multi-process models rather than threaded ones: if there is little performance advantage in creating threads, and you don't need the more performant IPC that they offer (not actually IPC: they offer in-process data sharing), the relative simplicity of spawning process makes them more attractive. This has changed a bit over time though: the ubiquity of multi-core CPUs and changes in scheduling practices & such to take better advantage of them has made threads a bit more attractive than they once were under Unix-a-likes too (even when you still don't need the in-process data sharing).
- aseipp 3y ago
  WSL1 did not use the NT codepath in order to spawn processes. WSL1 had its own direct support in the kernel for its own process type ("nanoprocess" is what they called it IIRC) managed independently from NT processes; and it even supported features/APIs for them that NT ones did not have, such as a compatible fork() call
  - dspillett 3y ago
    IIRC that support was still noticeably heavier than starting a thread. Much faster than the unix-y fork() emulation in cygwin/msys/similar, or in things more directly ported to Windows that use native fork equivalents directly, but still not closing the thread/process efficiency difference to that seen away from Windows. This performance difference was one of the reasons (though I think a minor one) that they switched to a managed VM instead of an emulation layer for WSL2.

mackman 3y ago

I’ve been doing development on AIX recently and the lack of such a cache has proven a real pain necessitating implementing our own disk scan and cache. Not knowing the path to an open file or process in constant time is terrible. If anyone here happens to be an expert on AIX and has suggestions please speak up!

pi-e-sigma 3y ago
AIX kernel has an inode cache, stat cache and directory name caches though. There's procfiles command to show inodes open by a given process and istat command that can link the i-nodes back to the file names. There is also available lsof command ported from linux. You could also trace system calls of these tools to see what exactly they are doing and replicate it in your app
- mackman 3y ago
  I read through lsof source. It doesn’t provide paths for regular files. Even emailed the author to confirm.