Why Unix kernels have grown caches for directory entries ('name caches') | Hacker News Reader

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

utcc.utoronto.ca

73 pointspabs331 comments

(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?)

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-no... comments discuss a bit in between the dire warnings). Or maybe it's not possible on newer systems that have such a cache?

Apple allows hard linking directories (I believe it is used for Time Machine somehow): https://jameshunt.us/writings/linking-dirs-in-macos/

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.

It’s no longer possible.

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.

You can do it with FUSE I'm pretty sure

Yes. I've done that (but only on immutable filesystems, where it's not (much of?) a problem).

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.

Oh, I didn't have any cycles.

I was exposing a git repository as a DAG of directories via FUSE, and was translating git internal IDs, based on hash, straight to inodes in a one-to-one fashion. Git doesn't allow cycles (unless you break the cryptographic hash function).

That’s a good write up.

I remember back in the Solaris days there was the "link" command that would allow you to make hard links of directories. My memory's bit rotted but I believe fsck would complain about the hard linked directories; I don't remember what it did with it.

Apparently the link[1] command still exists and the man page says "this does not do any error checking"

[1]https://docs.oracle.com/cd/E26505_01/html/816-5166/link-1m.h...

Linux is not UNIX. It is a UNIX clone up to a point.

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.

What about macOS, BSD?

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).

… 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.

> 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

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.

Wtf. Is this documented or benchmarked anywhere?

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.

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).

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

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.

As someone that was a big fan of multi-threading, it is somehow ironic that we are going back to multi-process models, not only due to microservices (basically the rebranding of "The network is the computer" for newer generations), but also due to security considerations.

UNIX was designed for servers, that was what PDP-11 was good for, and even when workstations came to be, X Windows and other similar protocols, were basically an extension of server workflows anyway.

Multithreading was bolted on, and even if all UNIXes ended up converging into pthreads, there is enough stuff on POSIX that doesn't go well with threads.

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.

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.

I am a capsicum true believer who wants to use file descriptors for everything, and hardlink directories all day.

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!

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

I read through lsof source. It doesn’t provide paths for regular files. Even emailed the author to confirm.

Reply on news.ycombinator.com