my emacs is completely fucked
Post
Replies:
15
this distinction is actually like the most interesting part of my directory traversal work: using file descriptors and inodes to confidently read and write and have a clear concept of progress and completion, instead of path strings which are fundamentally racy and cannot be deduplicated
@hipsterelectron so wait what is different in practice when you do that
@kirakira great question! there's a short answer and a long answer. the long answer is likely still beyond my ability to do it justice but it's kinda why i've been so focused on filesystems for so long.
so essentially the filesystem is where fucking everything happens all at once. the NASDAQ trading floor. people biking to work. kids walking to school in their outfits. it's new york, baby! it all happens here!
@kirakira it's been really fascinating to learn with build tools how that differs from the challenges of network and web browser engineering like servo. the biggest distinction there is that most async models are wildly inappropriate for local file i/o. there are larger discussions to have about why, but the close technical distinction here is that networking and servers are largely optimizing:
(1) interactions with many other entities they don't control
(2) with incredibly nondeterministic latency for every request
(1) interactions with many other entities they don't control
(2) with incredibly nondeterministic latency for every request
@kirakira so that's the reason why async works really well because it lets you timeshare your cycles when these unpredictable latencies finally occur. but the filesystem is different. you have some degree of control over it (but not much). but importantly, instead of web/http standards for things like caching artifacts (as i'm taking advantage of with pip), you generally have to handle a massive variety of complexity that has grown directly from all the different ideas people had about UNIX from bell labs. it's the C ABI baby!!!
but most importantly, you're often writing code that runs on your users' laptops and touches their files. that's a different degree of closeness and responsibility that you have to bear on top of figuring out all these situations that don't have protocols to provide easy answers.
@kirakira so the reason i started investigating this in the first place was because i thought it would be relatively plug and play. we used the rust
ignore crate in pants for almost two years before we amicably parted ways because pants needed more control over that traversal. this was supposed to be something i could contribute to @ethersync which like pants has to concern itself not just with a single filesystem crawl but also correctly maintaining state over time. this mutable state is where things get really dicey.
@kirakira so then i almost immediately found a deadlock in ripgrep https://github.com/BurntSushi/ripgrep/pull/3010 because it turns out recursive directory traversal is almost uniquely difficult to map to standard parallelism models.
the literally fractal complexity that results from every directory potentially having an entirely new set of entries is genuinely just very difficult to solve.
contrast to a problem space that can be solved: https://github.com/zip-rs/zip2/pull/236. zip files tell you up front what contents they have and you can plan and schedule your work around this. this ability to schedule "offline" is what the filesystem gives you, and it's something i haven't been able to translate to the async executor model vs one with explicit threading.
@kirakira in particular, the reason ripgrep had this occur (andrew gallant is great and i admire him a lot to be clear) is because when you traverse a directory recursively, you legitimately might want to return early, either from a subbranch (e.g. if it doesn't match your regex patterns, like the
ignore crate) or from the entire process. differentiating that from erroneous behavior is extremely difficult and i spent probably several days thinking about that PR before trying to solve it on my own.
@kirakira the reason i focused on (1) file descriptors and (2) inodes is because they (at least fds) represent some of the very few rigid contracts you can actually request from the filesystem (something @zwol has been pondering recently). i believe for example when working on the parallel zip implementation (which required expanding the rust libc wrapper) that POSIX does not guarantee the behavior of parallel write operations on the same file handle, but it does guarantee that parallel reads with
pread() will succeed.so while path strings are a really tempting way to reduce the problem to an abstraction, they can be and often are a complete lie. just yesterday i started getting errors in my shell because i'd unlinked the directory i was in, and even though i added the directory back later (so my shell was still displaying a valid path), the filesystem does not take IOUs like that >=[
@kirakira i think inodes are potentially a little overrated but i'm not sure about that yet and would need to talk to an expert more thoroughly. but one basic thing the
ignore crate (and ripgrep more generally) does that is clearly pessimal is not differentiating symlinks from other types of paths, so they traverse the same output twice. i suspect ripgrep keeps track of more persistent identifiers like inodes when it actually reads the files, but i think it's the wrong abstraction that leads to more than just deadlocking if you're relying on it for correctness like pants
@hipsterelectron @kirakira this is all reminding me of my most controversial stack overflow answer of all time (<https://stackoverflow.com/a/34884735>). The short version of why inodes still, even today, cannot be trusted is that _nothing_ within the computer can prevent the user from yanking one USB stick out of the slot and shoving a different one in, and both of them are formatted with FAT filesystems with nothing at the volume level to distinguish them. (better filesystems have GUIDs nowadays)
@zwol @kirakira yes!! i saw a stackoverflow post where someone was trying to use inodes for uniqueness and the answer was just honey that inode's not for you that belongs to the filesystem. we're just along for the ride. part of the reason why i haven't pushed to finish this work is because i pondered the conjunction of (1) filtered paths by ignore patterns [particularly if you progressively retrieve further patterns from the filesystem] (2) deduplication of paths through symlinks and it just seemed like a provably impossible problem
@hipsterelectron @zwol so just kind of making sure i'm following along properly here, on less sophisticated filesystems is there just no way to know with absolution that an inode hasn't changed under you, or that two inodes don't point to the same file?
@kirakira @zwol the inode is just a number the filesystem uses internally for bookkeeping and it really shouldn't be exposed at all imho. if you're a filesystem implementor it's not actually unreasonable to use small integers generated without randomness since all you need from that identifier is something you can write into your binary bookkeeping format that you store on the user's block device. consider the similar analogy for cryptographic checksums vs faster hashers used in hash tables--that's a contentious discussion of its own but in general it's just a number that should never have been exposed in the first place because the filesystem does not guarantee a single thing about it
and even if inodes were unique within a single filesystem, there is almost always more than one filesystem on each physical device (i can think of at least the EFI boot partition on my laptop), and those filesystems absolutely do not take steps to avoid reusing the same inode numbers, because that's for their internal bookkeeping (and it's what the OS requests of them).
really this is something the OS should be handling and it's extremely surprising that no one has done it. i was going to mention process id (pid) reuse as a similar example but i don't think there's really any good use for pid uniqueness, whereas with files and directories there is imho a very distinct concept of mutable state which is the whole point of the VFS layer!
@hipsterelectron @kirakira pid reuse can cause the wrong process to get killed; this is enough of a live issue that it's why people came up with the pidfd API, and why you can find hardening guidelines telling you to raise pid_max. But it _is_ much less likely to come up.
