4 ms·

One thing I’ve never understood about Linux filesystems: given how small and bounded the sets of directories and directory entries are, why is filesystem traver

One thing I’ve never understood about Linux filesystems: given how small and bounded the sets of directories and directory entries are, why is filesystem traversal not instantaneous?

spicybright 5y ago
Lack of caches I'd assume. Not because it's not easy, but because no one has taken the time to implement it.
- toxik 5y ago
  They say there are two hard problems in computer science: cache invalidation, naming, and off-by-one errors.
  - spicybright 5y ago
    Hehe. You're right, I forgot one of the golden rules. There's probably a better reason why no one has implemented it.
amelius 5y ago
Also, why can tab-completion in Bash hang my shell?
- chrsig 5y ago
  This is actually an incredibly frustrating thing -- when doing disk i/o, the process goes into an uninterruptible sleep state[0]. So if your shell is doing some tab completion that goes into an uninterruptible sleep, there's no escape sequence you can send it to cancel that operation. Where I've seen this be the most vexing is in AWS if an EBS volume dies (surprisingly more frequent of an occurrence than you'd think!). It effectively prevents the machine from cleanly shutting down, and you wind up having to wait for the instance to be forcefully terminated. [0] https://eklitzke.org/uninterruptible-sleep https://eklitzke.org/uninterruptible-sleep
  - amelius 5y ago
    This is indeed nasty. Imagine you have a server built using asyncio style multitasking, and one of the tasks tries to do disk i/o ... This basically throws the entire asyncio style programming out of the window.
    - chrsig 5y ago
      indeed. this is one of the benefits of a concurrent sequential processing model with a scheduler. e.g., in Go, blocking syscalls get put on their own thread in a thread pool, so that processing can continue while waiting. I'm sure you can do something similar in a raw event loop, but I don't think the machinery is generally baked in to the io interfaces to do so.
- kelnos 5y ago
  Because tab completion often has to do i/o, which can put the shell into an uninterruptible sleep state. I personally see this most when I've left home but I still have an NFS mount (to my NAS at home) under my home directory.
m000 5y ago
What you describe is an over-specialized optimization that very few users would benefit from, but would still introduce significant complexity. Linux already transparently caches filesystem metadata. You already get a good speedup if you attempt the same directory walk twice, and not much have changed in the filesystem.
- gorgoiler 5y ago
  My desktop has ~2MB of basenames on it. Memory isn’t free, and there’s more to an inode than a filename, but it seems odd that this data that’s the size of a cat photo doesn’t get special treatment over other vm cache data.
  - thanatos519 5y ago
    That's tunable, and apparently the default is reasonable: https://sysctl-explorer.net/vm/vfs_cache_pressure/ https://sysctl-explorer.net/vm/vfs_cache_pressure/ My workstation has 64GB of RAM and only ~7M directory entries so I have 'vm.vfs_cache_pressure = 1' in /etc/sysctl.conf and cache everything with a full directory traversal via find. The first time it takes 52s; subsequent times take 5s. It has never given me memory problems.
    - spicybright 5y ago
      I'm assuming the cache isn't kept on disk tho, right? As in 52s the first time since boot, 5+ for subsequent runs (incorporating time for changed files/directories)
topspin 5y ago
> why is filesystem traversal not instantaneous Because a mounted file system isn't a simple indexed list of paths. File systems are shared, mutable state. The mechanism you're asking about is called the dentry cache[1] and a decent narrative of its operation is found here[2]. It has the fabulously complex job of atomically brokering the state of an arbitrary number of local and remote file systems between an arbitrary number of processes using arbitrary access patterns without consuming all available RAM. Expecting the dentry cache to yield 'instantaneous' results is unreasonable. Comparing its performance to that of an VCS index is naïve. [1] https://www.kernel.org/doc/Documentation/filesystems/vfs.txt https://www.kernel.org/doc/Documentation/filesystems/vfs.txt [2] https://www.halolinux.us/kernel-reference/the-dentry-cache.html https://www.halolinux.us/kernel-reference/the-dentry-cache.h... (no endorsement of these people, but the dentry cache description is both concise and sufficient.)
wvh 5y ago
Probably having to check if the actual disk entries changed is what slows it down. I wonder if it would be possible with nowadays' memory sizes to keep all metadata in memory as a write-through cache. Not sure if it'd be worth it though, my system has close to half a million files, but I'm only interested in about a hundred or so. I don't think file systems are slow in practice for typical human-scale operations though, with the exception of non-indexed "search all my files" type of operations.

One thing I’ve never understood about Linux filesystems: given how small and bounded the sets of directories and directory entries are, why is filesystem traversal not instantaneous?

spicybright 5y ago

Lack of caches I'd assume. Not because it's not easy, but because no one has taken the time to implement it.

toxik 5y ago
They say there are two hard problems in computer science: cache invalidation, naming, and off-by-one errors.
- spicybright 5y ago
  Hehe. You're right, I forgot one of the golden rules. There's probably a better reason why no one has implemented it.

amelius 5y ago

Also, why can tab-completion in Bash hang my shell?

chrsig 5y ago
This is actually an incredibly frustrating thing -- when doing disk i/o, the process goes into an uninterruptible sleep state[0]. So if your shell is doing some tab completion that goes into an uninterruptible sleep, there's no escape sequence you can send it to cancel that operation. Where I've seen this be the most vexing is in AWS if an EBS volume dies (surprisingly more frequent of an occurrence than you'd think!). It effectively prevents the machine from cleanly shutting down, and you wind up having to wait for the instance to be forcefully terminated. [0] https://eklitzke.org/uninterruptible-sleep https://eklitzke.org/uninterruptible-sleep
- amelius 5y ago
  This is indeed nasty. Imagine you have a server built using asyncio style multitasking, and one of the tasks tries to do disk i/o ... This basically throws the entire asyncio style programming out of the window.
  - chrsig 5y ago
    indeed. this is one of the benefits of a concurrent sequential processing model with a scheduler. e.g., in Go, blocking syscalls get put on their own thread in a thread pool, so that processing can continue while waiting. I'm sure you can do something similar in a raw event loop, but I don't think the machinery is generally baked in to the io interfaces to do so.
kelnos 5y ago
Because tab completion often has to do i/o, which can put the shell into an uninterruptible sleep state. I personally see this most when I've left home but I still have an NFS mount (to my NAS at home) under my home directory.

m000 5y ago

What you describe is an over-specialized optimization that very few users would benefit from, but would still introduce significant complexity. Linux already transparently caches filesystem metadata. You already get a good speedup if you attempt the same directory walk twice, and not much have changed in the filesystem.

gorgoiler 5y ago
My desktop has ~2MB of basenames on it. Memory isn’t free, and there’s more to an inode than a filename, but it seems odd that this data that’s the size of a cat photo doesn’t get special treatment over other vm cache data.
- thanatos519 5y ago
  That's tunable, and apparently the default is reasonable: https://sysctl-explorer.net/vm/vfs_cache_pressure/ https://sysctl-explorer.net/vm/vfs_cache_pressure/ My workstation has 64GB of RAM and only ~7M directory entries so I have 'vm.vfs_cache_pressure = 1' in /etc/sysctl.conf and cache everything with a full directory traversal via find. The first time it takes 52s; subsequent times take 5s. It has never given me memory problems.
  - spicybright 5y ago
    I'm assuming the cache isn't kept on disk tho, right? As in 52s the first time since boot, 5+ for subsequent runs (incorporating time for changed files/directories)

topspin 5y ago

> why is filesystem traversal not instantaneous Because a mounted file system isn't a simple indexed list of paths. File systems are shared, mutable state. The mechanism you're asking about is called the dentry cache[1] and a decent narrative of its operation is found here[2]. It has the fabulously complex job of atomically brokering the state of an arbitrary number of local and remote file systems between an arbitrary number of processes using arbitrary access patterns without consuming all available RAM. Expecting the dentry cache to yield 'instantaneous' results is unreasonable. Comparing its performance to that of an VCS index is naïve. [1] https://www.kernel.org/doc/Documentation/filesystems/vfs.txt https://www.kernel.org/doc/Documentation/filesystems/vfs.txt [2] https://www.halolinux.us/kernel-reference/the-dentry-cache.html https://www.halolinux.us/kernel-reference/the-dentry-cache.h... (no endorsement of these people, but the dentry cache description is both concise and sufficient.)

wvh 5y ago

Probably having to check if the actual disk entries changed is what slows it down. I wonder if it would be possible with nowadays' memory sizes to keep all metadata in memory as a write-through cache. Not sure if it'd be worth it though, my system has close to half a million files, but I'm only interested in about a hundred or so. I don't think file systems are slow in practice for typical human-scale operations though, with the exception of non-indexed "search all my files" type of operations.