Better VFS #3715
Comments
matklad
added
the
C-Architecture
|
https://rust-analyzer.github.io/blog/2020/05/18/next-few-years.html
Hello, I'm deeply involved in both watchman and large virtual filesystems at FB. Maybe it's worth us having a realtime chat sometime soonish? I'm interested in hearing more about what's on your mind and can share context on how we think about the problem space in general and perhaps give some advice to inform your design! |
|
Yes, this would be hugely helpful! The best place to coordinate about specific for me would be the rust-lang Zulip instance https://rust-lang.zulipchat.com/#narrow/stream/185405-t-compiler.2Fwg-rls-2.2E0 (@matklad). Email (on GitHub profile) would also work! |
|
Just to shout out: (already did that in Zulip) I'm also interested in improving VFS! However, I know hardly anything about Watchman, but if there is some other grunt work to pave the way to real-time updating Cargo.toml/Cargo.lock, adding files/workspaces dynamically and opening single files without projects, I'm interested! |
|
Responding to the blog post (which was great, thanks!) with some prior art in this area: the Pants build system implements a lazy VFS with symlink aware file watching, spread across three-ish relatively loosely coupled crates. We recently switched from The fs crate implements symlink aware lazy glob expansion atop a VFS trait. Being symlink aware means that the The core The graph crate is similar (in purpose at least?) to salsa: the idea is that you have a Node type (generally implemented using an enum to isolate the implementations), and as Finally, the watch crate is a thin wrapper around the If I understand salsa correctly (and rust-analyzer is still using it?), it's possible that you would be able to do things similar to the |
|
A bit more color on the Pants used The Our hypothesis on this was that having a dependency aware, memoized graph and tracking operations at the syscall level made a few of the things that watchman does redundant. There are other things that we'll likely need to implement on our own though (re-crawl support, for example): so time will tell! |
|
So, trying to facilitate things a bit. Please correct me if I have anything incorrect or missing and I'll add it. Also marked places I'm unclear about, or know there's information missing, with FIXME: What are the requirements for VFS to use with Rust-Analyzer?
What are the shortcomings of current ra_vfs?(@matklad's list is in the starting post, this is my rephrasing)
What are the alternatives / future possibilities?Moving from notify crate to Watchman
Staying with notify?
Developing ra_vfs's other features that don't directly concern file watching
I'd appreciate if @matklad and others who have good understanding of the problem would fill in the FIXMEs and point if there's other stuff missing. Updates: |
|
[Disclosure: I'm heavily invested in both Watchman and EdenFS at FB. I have two different "hats" here in this thread; one is to be a resource to help you understand more about Watchman, the other is as a Rust enthusiast that wants to see more Rust in our monorepo and to facilitate those tools working well in that environment!] Watchman's selling points are mostly to do with scale of the repo, which very few (none that I'm aware of!) other notification libraries consider:
Today it is admittedly difficult to consume the version of watchman from master because it is difficult to build unless you are thoroughly determined, BUT! we've got the GitHub CI producing binaries and in the next few weeks should be able to iron out some kinks and get those showing up in the releases section. My plan for Linux is to ship an AppImage binary, and it should be doable to bundle the linux/windows/macos binaries up with rust-analyzer if that makes sense for your deployment. Not everyone has the same scaling requirements as FB so the above isn't universally relevant. What matters to us is being able to configure the tools to use watchman, even if that isn't the default/only way to make the tool function. So while I'm pro-watchman I'm enough of a pragmatist not to campaign only for watchman vs. some other solution--"why not both?" seems like a valid question to ask. |
This sounds interesting to me. Does Watchman not only provide update notifications but the changed file contents? It sounds to me that no matter how consistent the file metadata model is, if ra_vfs does the file loading by itself, it's bound to have TOCTOU concerns. |
Watchman only needs libc, right? In that case using musl to statically link would be a much more lightweight solution. (Maybe with jemalloc for much better allocator performance?) There is no need to mount a file system that contains the executable and all files it depends on, like AppImage does. https://docs.appimage.org/user-guide/run-appimages.html#mount-an-appimage |
|
Another request to educate me (consider it rubber duck debugging if you will): what does consistency mean in the context of VFS and what level of consistency is required for the use case? The way I imagine things is that the creation, deletion and updated events of files should be known in a consistent order after they have added to watched roots. But when loading the contents after getting a notification of an update, we might get a version that is newer, because we haven't got the update for that change yet? Is that a problem? Is there other, more serious consistency problems I'm missing? I have the impression that 1) consequent filesystem snapshots are still "monotonically increasing" 2) we don't get stuck in a state where we stay at an old version of a file for an indefinitely long time if don't miss any updates after we've first started watching a file and then loaded it. I used to think that the "consistency" required is only that once you got some versions of the files loaded in memory, you can rely on that snapshot not changing, but that is provided just by having the files loaded to memory and being immutable and isn't dependent on the file watcher's functionality. What are the kind of consistency problems around file watching we care about? |
|
Regarding TOCTOU and consistency; here are some more implementation details from watchman. I'm using these to surface some of the concerns we've had to deal with in our role as a general file watching system. These concerns may not apply to every use case! The OS notification stream is buffered by the kernel which means that you need a mechanism to relate an event with "when" it happened, because the time at which you pull the event from the stream is not the time at which it happened, making it potentially racy to understand whether you are up to date. Watchman deals with this by generating a special unique cookie file at the start of a query and waiting to observe the notifications for that file before proceeding; more details here: https://facebook.github.io/watchman/docs/cookies Another aspect of consistency is that because processing of events lags behind the notification stream, the nature of the notification may not reflect the currently observable state on the filesystem! Consider a program that creates a temporary file, writes to it and then Some notification systems are potentially low fidelity; for example, on macOS/fsevents, you can get an event that says "something somewhere under this directory path has changed", but it won't tell you what. It may mean that the whole directory subtree is different, or that some significant amount of it is different. To make it easier to reason about the state of the filesystem, watchman uses the OS notification stream as a source of hints rather than trusted metadata. Watchman builds a model of the observed filesystem and uses those hints to detect when it should update its model. Each time the notification stream provides data, watchman assigns the next monotonic sequence number (called the clock) that will represent that point in time and then uses the hints to The clock allows watchman clients to query about changes since a prior clock. Note that because of TOCTOU and the asynchronous nature of everything, watchman's observation based model only guarantees that changes prior to the creation of the synchronization cookie file have been observed. Effects from events that happened concurrently with or after that may also be included in that view, but are guaranteed to subsequently wake the notification stream and tick the clock, so your application can reason about that subsequent change. A common problem to deal with in this sort of situation is a person who kicks off a build and who edits files while the build is running. In this racy scenario it is ambiguous whether their edits were observed by the compiler, and the compiler generally can't tell that this has happened because it is only concerned with the data it read from the file at the moment it considered it. At best the resultant artifact has ambiguous contents, but if you are caching eg: metadata about symbols/exports from a source file and plan to re-use it on a subsequent run, you may have a poisoned cache entry. One strategy to deal with this is:
Regarding the snapshot concept: I've seen snapshot mentioned a couple of times in this issue; I don't really know anything about the current design or what that means in the context of this project. However, I'd suggest being careful with this term because it implies a level of consistency that is very difficult to obtain without true snapshot support from the underlying filesystem! I'm not sure that you can obtain a stronger ordering/consistency than the happens-before/"eventually consistent" concept above. Regarding file contents: Watchman builds its model from the metadata and avoids looking at file contents. The model reflects the most recently observed state of the filesystem and doesn't include history, so while you can ask watchman to execute a Watchman can be asked to produce a content hash for a file; today it knows about sha1 hashes because those are widely used for change detection (not for crypto!) in tools widely used inside FB. Watchman maintains an LRU cache for content hashes and the size can be specified in a Aside from content hashes, watchman avoids operating on file contents because the IO and memory requirements are hard to predict; eg: someone fat-fingers a command and now you have a 100GB |
The folly and thrift (for talking to EdenFS) dependencies pull in boost, glog and gflags and for difficult to unpick reasons, the cmake flavor of the builds for these things are resistant to compiling their various libraries statically in all combinations of the open sourced FB projects. We've gotten some of them static, but it's hard and thankless work requiring the patience of a saint / the stubbornness of a mule. AppImage is just an expedient way to furnish a binary download; it's not technically required and the cost/benefit of making a musl / all static build vs. the cost of getting there don't look compelling today. We'd like to see it happen, but it's not a small amount of work because it would need to apply across all of the facebook projects that depend on folly. |
|
@wez Thanks for the explanation. For clarification: I use snapshot here to mean an immutable in-memory state of the contents and path-content mappings of the files included in the VFS overlay; so not in a meaning of getting an atomic state of a filesystem but rather, making a best-effort try to load a recent state of the relevant files and then "freeze" that to use as input for the analysis libraries. Thanks for the links, I think I'll take a better look at Watchman docs :) |
|
Let me clarify my vision of "consistent snapshots" as well, as that's a pretty sloppy usage of terminology on my part. The only property we really need from a VFS is repeatable read. If rust-analalyzer queries for a contents of file "foo.rs" and gets We need this property, because rust-analyzer is architectured around ability to forget things. Our concrete syntax trees are a heavy data structure, so we generally parse file, compute some compressed index on the result, and throw away the syntax tree. If later we need syntax tree to get additional info about the file, rust-analyzer just re-parses it from scratch and, at this point, it is important that the re-parsed tree is consistent with the info we persisted in an index. Obviously, file systems do not actually guarantee such repeatable read, so we have to keep the contents of files in memory. This should be OK even for large repos:
So "VFS" for rust-analyzer is (to the first approximation) a Curiously, rust-analyzer doesn't really care what it reads from the files, if that is eventually consistent. Ie, if The only bad thing we need to protect against are lost updates. If, for example, rust-analyzer reads a directory, and then a file changes after we've read its contents but before we've set up a watch, we have a problem. |
|
emacs user: currently goto-definition on external crate (added via cargo add ) doesn't work unless you do restart workspace. (lsp-restart-worspace) would be interested to see that on rust-analyzer! |
|
We had a video discussion with @matklad and @wez around topics related to watching and modeling the file system. I'm summarizing some random thoughts and notes here. Watching changesSome hard things in this space (not necessarily an exhaustive list):
Representing paths
There was talk about the general requirements, about whether a set of APIs @matklad showed seemed to make sense, ideas about eagerness and laziness and stuff like that, but I didn't manage to get any conclusive picture about them. There was also some thing I wanted to talk but it was getting late so I decided not to, but I will expand here: @matklad emphasized that he doesn't want to build and maintain a file watching / notification library himself. He also was interested in Watchman because it's battle-tested and they have been thinking hard about best practices of representing this stuff. However, I am a bit worried about the weight of the dependency in the sense that it's not a library, but another system communicated via IPC, so it feels much more complicated as a component. (Also, thinking about the growing hurdles with distribution/installation.) On the other hand, @wez pointed out earlier that there are some use cases (especially in context of monorepos) where having a single watch daemon makes absolutely more sense. To me, it would make sense to study the API and capabilities of Watchman well, but not commit using it as the one and only "watcher backend", but instead use it as an inspiration for an API so that an alternative, library-based watcher backend would be also possible besides of an Watchman-communicating IPC-based one. It also seems to me that the "watcher notifications" part could be decoupled from the snapshot-managing part relatively well, provided that the interface has been thought well enough. Anyway, some food for thought! Good night. |
Have you seen this happen with Windows paths? I'd have thought that for filesystem paths, legacy programs would be using the relevant Windows code page (and associated Programmer would surely have to go out of their way to both use the Unicode functions and mangle the output. It could happen but I'd naively assume it would be the result of a mistake rather than for legacy reasons. |
|
Wow, thanks @golddranks for staying super late and also writing the notes, that's very helpful! Here are some my take aways from the chat.
My plan is thus:
|
|
@matklad How do you feel about allocating and prioritizing this work over some other work in Rust-Analyzer? I feel like actually writing prototypes of new designs and producing PRs for VFS is something that can be reasonably done by volunteers, while you could provide guidance over the design and the API. I'm interested in participating the development in that way, possibly playing around with Watchman, coding a prototype of a new version of VFS and then discuss it. You could then keep working on non-VFS stuff that seems, at least to me, harder to tackle without deeper understanding of the main codebase. |
|
@golddranks urgh, so it took me a long way to get back here :( Unfortunately, I am pretty bad (yet?) at parallelizing such fundamental changes -- the only algorithm that is known to work here is when someone just dumps 2kloc pull request which implements everything better than I could have done :( I've started new vfs here https://github.com/matklad/rust-analyzer/tree/vfs (though, the code is in an embarrassing state right now :) ) What would definitely be helpful is bringing the notify library up to production quality (publishing version 0.5). I think @stuhood might be intersted in this as well? From my brief look, they are using notify 0.5-pre right now. Another useful thing to do would be bulidin an recursive directory watching implementation. I've outlined the API in notify-rs/notify#175 (though I am not entirely sure if it is the right API). This I think can either be implemented as a separate crate on top of either notify 0.4 or notify 0.5, or as an API inside notify 0.5. |
Polish there would be very much appreciated, yea. Thanks!
We expose this kind of API. If it would help for me to expand the description from #3715 (comment) at all, or to extract a demo, let me know. None of the crates are published, but they've been stable for a while. |
|
We've implemented a new API for VFS, which I feel is good enough. The core insight that helped was separating compler-specific concerns (path interning and binning paths into disjoint file sets) from physical file systems concerns (reading and watching files). Specifically, here's the new interface for file system bits: The handler encapsulate a separate concurrent actor that can walk, read and watch files upon request. The set of files to crawl is specified in term of absolute paths. We went with eager API, as the model seems simpler, and it's nice to account for files which are not linked into the module tree. We provide an implementation of this API based on notify 0.5-pre.3: The impl is known to be buggy around file-watching (file crawling should work OK). As we default to client-side watching, this shouldn't be a problem in practice. Long term, we'd love to pull an off-the-shelf solution for this. When a crate with "watch the set of paths which match the following globs/ignores" appears on crates.io, it should be easy to bridge it to our Thanks everyone for valuable input, it was suuuper helpful ❤️ ! |
|
Since all the "need to restart RA after adding a dependency" bugs were duplicated to this one, is that supported yet (it doesn't seem to work). Do we want to track it in a different issue? |
|
Good call, opened: #5074 |
Now we are in 2023 and crate notify’s version is 5.1.0. Is it mature enough for this task, or any other alternatives? |
|
From the quick look, it seems that notify does not provide this API yet. The specific thing missing is a unified API for walking and watching. This is the API I think is required here: fn is_interesting_path(path: &Path) -> bool {
// Check if this is potentially interesting path (eg, ends with `.rs` and is not in `./target` or `.gitignore`)
}
let watcher = Watcher::new(|p| is_interesting_path(p));
for event in watcher.iter_events() {
match event {
// Creating a new watcher _guarantees_ to yield all events for files already
// on disk if they match the predicate, event if they don't see any changes.
Event::InitialScan(path) => ...,
Event::Change(path) => ...,
}
}I belive that combining "walk&watch" into a single atomic operation is required for correctness. notify 5.1.0 does not seem to provide that. watchman should provide that. I also think that folks from the pants build system build something like that as well. I haven't surveyed other libraries, this might be solved on crates.io. |
Our VFS has a number of implementation and design problem. Being the core of the system, this is not good :-)
The main impl problem is that we hit many bugs in the underlying notify library (so that we try to use client-side watching by default) (and the root cause here is that the OS APIs for file watching are just terrible and nay impossible to use in a non-broken way).
Some of design issues are:
I hope that most of this design issues are actually handled by https://docs.rs/watchman_client/
The text was updated successfully, but these errors were encountered: