11 ms·
Fil's Unbelievable Garbage Collector
- aidenn0 1y agoHow can the GC be precise when C and C++ allow casting between pointers and integers?
- 1vuio0pswjnm7 1y agoYet another useful project using musl not glibc https://wiki.musl-libc.org/projects-using-musl https://wiki.musl-libc.org/projects-using-musl
- loa_in_ 1y agoI'm amazed by how readable the source is, the names meaningful and not filled with jargon.
- jcul 1y agoThis looks pretty amazing, I'm surprised I haven't heard of it before. Looking forward to trying it out. Seems like a good way to verify the safety of some programs, even if not feasible for production due to performance constraints. Though we have sanitizers for tests, this seems more complete.
- program_whiz 1y agoCan anyone explain how the roots are known to the GC, I can't spot it. Does it have some kind of precompile step to mark roots for GC scan? @pizlonator ?
- celeritascelery 1y agoIt is having LLVM insert instructions to fill out the stack map
- achierius 1y agoWhy did you choose to use an advancing wavefront rather than retreating wavefront strategy?
- reactordev 1y agoOh this is so cool
- kerkeslager 1y agoI'm not sure I understand all of what they're doing there, but I did read the referenced Doligez-Leroy-Gonthier paper a while back and I am glad someone is doing something with that in a non-academic (maybe?) context. That paper looked promising to me when I read it, but I basically had no faith that it would ever make it out of academia because the algorithm is so complex. It took me a really long time to think I understood it, and it's one of those things I actually am not confident I could implement even when I understood it (I certainly don't understand it now).
- pizlonator 1y agoI don’t think I’m the only one doing something in the vicinity of that paper. I think close relatives of DLG shipped in some prod JVMs.
- kerkeslager 1y agoInteresting. I've read a lot about some complex JVMs, but I guess maybe they didn't cite their sources and I didn't make the connection on my own.
- jomarry 1y ago[dead]
- pcfwik 1y agoGiven the goal is to work with existing C programs (which already have free(...) calls "carefully" placed), and you're already keeping separate bounds info for every pointer, I wonder why you chose to go with a full GC rather than lock-and-key style temporal checking[1]? The latter would make memory usage more predictable and avoid the performance overhead and scheduling headaches of a GC. Perhaps storing the key would take too much space, or checking it would take too much time, or storing it would cause race condition issues in a multithreaded setting? [1] https://acg.cis.upenn.edu/papers/ismm10_cets.pdf https://acg.cis.upenn.edu/papers/ismm10_cets.pdf
- pizlonator 1y agoI think the lock and key approaches don’t have Fil-C’s niftiest property: the capability model is totally thread safe and doesn’t require fancy atomics or locking in common cases
- pcfwik 1y agomakes sense, thanks --- cool project!
- pcfwik 1y agoAlso find it interesting that you're allowing out-of-bounds pointer arithmetic as long as no dereference happens, which is a class of UB compilers have been known to exploit ( https://stackoverflow.com/questions/23683029/is-gccs-option-o2-breaking-this-small-program-or-do-i-have-undefined-behavior https://stackoverflow.com/questions/23683029/is-gccs-option-... ). Do you disable such optimizations inside LLVM, or does Fil-C avoid this entirely by breaking pointers into pointer base + integer offset (in which case I wonder if you're missing out on any optimizations that work specifically on pointers)?
- pizlonator 1y agoFor starters, llvm is a lot less willing to exploit that UB It’s also weird that GCC gets away with this at all as many C programs in Linux that compile with GCC make deliberate use of out of bounds pointers. But yeah, if you look at my patch to llvm, you’ll find that: - I run a highly curated opt pipeline before instrumentation happens. - FilPizlonator drops flags in LLVM IR that would have permitted downstream passes to perform UB driven optimizations. - I made some surgical changes to clang CodeGen and some llvm passes to fix some obvious issues from UB But also let’s consider what would happen if I hadn’t done any of that except for dropping UB flags in FilPizlonator. In that case, a pass before pizlonation would have done some optimization. At worst, that optimization would be a logic error or it would induce a Fil-C panic. FilPizlonator strongly limits UB to its “memory safe subset” by construction. I call this the GIMSO property (garbage in, memory safety out).
- jandrewrogers 1y agoI think it is really cool that someone is going hard at this part of the design space from an engineering geek standpoint even though I can’t use it myself.
- crawshaw 1y agoIt is great that Fil-C exists. This is the sort of technique that is very effective for real programs, but that developers are convinced does not work. Existence proofs cut through long circular arguments.
- johncolanduoni 1y agoWhat do the benchmarks look like? My main concern with this approach would be that the performance envelope would eliminate it for the use-cases where C/C++ are still popular. If throughput/latency/footprint are too similar to using Go or what have you, there end up being far fewer situations in which you would reach for it.
- pizlonator 1y agoSome programs run as fast as normally. That's admittedly not super common, but it happens. Some programs have a ~4x slowdown. That's also not super common, but it happens. Most programs are somewhere in the middle. > for the use-cases where C/C++ are still popular This is a myth. 99% of the C/C++ code you are using right now is not perf sensitive. It's written in C or C++ because: - That's what it was originally written in and nobody bothered to write a better version in any other language. - The code depends on a C/C++ library and there doesn't exist a high quality binding for that library in any other language, which forces the dev to write code in C/C++. - C/C++ provides the best level of abstraction (memory and syscalls) for the use case. Great examples are things like shells and text editors, where the syscalls you want to use are exposed at the highest level of fidelity in libc and if you wrote your code in any other language you'd be constrained by that language's library's limited (and perpetually outdated) view of those syscalls.
- baranul 1y agoVery good answer and agree. There seems to be a psychological component wrapped up in the mythology versus the reality of what's necessary.
- monkeyelite 1y ago
- charleslmunger 1y agoThis is really cool! I noticed >The fast path of a pollcheck is just a load-and-branch. A neat technique I've seen used to avoid these branches is documented at https://android-developers.googleblog.com/2023/11/the-secret-to-androids-improved-memory-latest-android-runtime-update.html https://android-developers.googleblog.com/2023/11/the-secret... under "Implicit suspend checks".
- pizlonator 1y agoYeah that’s a common optimization for poll checks. I think most production JVMs do that. I’m very far from doing those kinds of low level optimizations because I have a large pile of very high level and very basic optimizations still left to do!
- titzer 1y agoWe did it for MaxineVM back in the day, having the thread-local-storage point to itself and the safepoint as a load back into the same register. The problem is that that introduces a chain of dependent loads for all safepoints and for all operations that use thread-local storage. That seems like it would hurt OOE and IPC as a result. I am working on adding threads to Virgil (slowly, in the background, heh). I'll use the simple load+branch from the TLS for the simple reason that the GC code is also written in Virgil and it must be possible to turn off safepoints that have been inserted into the GC code itself, which is easy and robust to do if they are thread-local.
- o11c 1y agoNote that the "safepointing" logic is exactly the same thing that's needed in refcounting to atomic replace a field. This article glosses over what I consider the hardest part - the enter/exit functionality around native functions may that block (but which must touch the allocator).
- pizlonator 1y ago> Note that the "safepointing" logic is exactly the same thing that's needed in refcounting to atomic replace a field. No it's not, not even close. > This article glosses over what I consider the hardest part - the enter/exit functionality around native functions may that block (but which must touch the allocator). Yeah, that part is hard, and maybe I'll describe it in another post. Look for `filc_enter` and `filc_exit` in https://github.com/pizlonator/fil-c/blob/deluge/libpas/src/libpas/filc_runtime.c https://github.com/pizlonator/fil-c/blob/deluge/libpas/src/l...
- Quitschquat 1y agoI love garbage collector design and impl. It’s one of those “go to” thing to do when learning a new language. Never heard of this one, looking forward to diving in this weekend.
- system2 1y ago> Fil-C uses a parallel concurrent on-the-fly grey-stack Dijkstra accurate non-moving garbage collector called FUGC Half of my hair turned white while trying to understand this.
- gleenn 1y ago> The only "pause" threads experience is the callback executed in response to the soft handshake, which does work bounded by that thread's stack height. So this is probably not great for functional/deeply-recursive code I guess?
- pizlonator 1y agoMeh. The stack scan is really fast. There's not a lot of logic in there. If you max out the stack height limit (megabytes of stack?) then maybe that means milliseconds of work to scan that stack. That's still not bad.
- adastra22 1y agoThat's a very long time. Milliseconds of work is an entire frame update-render cycle in a modern game.
- pizlonator 1y agoWould your modern game have a stack that is so deep that it brushes up against the stack height limit? Probably not. Your game would be inches of stack away from crashing
- debugnik 1y agoYou're missing the point, they're giving an example of an entire workload that fits into your technique's worst-case overhead. It's could be the right trade-off and rarely be hit, but that worst-case does sound bad.
- pizlonator 1y agoStacks tend to be small enough that the cost of scanning them is minuscule. (I’m not trying to BS my way here - I’m explaining the reason why on the fly GC optimization almost never involves doing stuff about the time it takes to scan stack. It’s just not worth it. If it was, we’d be seeing a lot of stacklet type optimizations.)
- AndyKelley 1y agoSuper cool project. Sorry if you explained this already, I don't know what "Dijkstra accurate" means. How does it know if an object is truly available to be reclaimed, given that pointers can be converted to integers?
- pizlonator 1y ago> given that pointers can be converted to integers? Because if they get converted to integers and then stored to the heap then they lose their capability. So accesses to them will trap and the GC doesn’t need to care about them. Also it’s not “Dijkstra accurate”. It’s a Dijkstra collector in the sense that it uses a Dijkstra barrier. And it’s an accurate collector. But these are orthogonal things
- charleslmunger 1y agoOut of curiosity, does this idiom work in fil-c? https://github.com/protocolbuffers/protobuf/blob/cb873c8987dd33282125ecbbae378b74be5f4707/upb/wire/eps_copy_input_stream.h#L286 https://github.com/protocolbuffers/protobuf/blob/cb873c8987d... // This somewhat silly looking add-and-subtract behavior provides provenance // from the original input buffer's pointer. After optimization it produces // the same assembly as just casting `(uintptr_t)ptr+input_delta` // https://godbolt.org/z/zosG88oPn size_t position = (uintptr_t)ptr + e->input_delta - (uintptr_t)e->buffer_start; return e->buffer_start + position; It does use the implementation defined behavior that a char pointer + 1 casted to uintptr is the same as casting to uintptr then adding 1.
- pizlonator 1y agoYeah that should just work Code that strives to preserve provenance works in Fil-C
- charleslmunger 1y agoVery cool. Hardware asan did not catch the pointer provenance bug in the previous implementation of that code because it relies on tag bits, and the produced pointer was bit-identical to the intended one. It sounds like fil-c would have caught it because the pointer capabilities are stored elsewhere.
- kragen 1y agoHmm, Fil-C seems potentially really important; there's a lot of software that only exists in the form of C code which it's important to preserve access to, even if the tradeoffs made by conventional C compilers (accepting large risks of security problems in exchange for a small improvement in single-core performance) have largely become obsolete. The list of supported software is astounding: CPython, SQLite, OpenSSH, ICU, CMake, Perl5, and Bash, for example. There are a lot of things in that list that nobody is likely to ever rewrite in Rust. I wonder if it's feasible to use Fil-C to do multitasking between mutually untrusted processes on a computer without an MMU? They're making all the right noises about capability security and nonblocking synchronization and whatnot. Does anyone have experience using it in practice? I see that https://news.ycombinator.com/item?id=45134852 https://news.ycombinator.com/item?id=45134852 reports a 4× slowdown or better. The name is hilarious. Feelthay! Feelthay!
- yndoendo 1y agoNote the power of SQLite being written in C is the portability to non standard OSes. [0] I've used on an embedded real-time μC/OS-II variant. [1] Architecture of embedded solutions is different than desktop and server. Example, to prevent memory from fragmenting and high performance, do not free it. Mark that memory (object / struct) as reusable. It is similar to customized heap allocation or pooling. [0] https://sqlite.org/vfs.html https://sqlite.org/vfs.html [1] https://en.wikipedia.org/wiki/Micro-Controller_Operating_Systems https://en.wikipedia.org/wiki/Micro-Controller_Operating_Sys...
- kragen 1y agoProbably worth pointing out that Fil-C doesn't yet support 32-bit systems (or presumably 16-bit or 8-bit systems): https://fil-c.org/invisicaps https://fil-c.org/invisicaps
- justin66 1y ago> There are a lot of things in that list that nobody is likely to ever rewrite in Rust. How many years away are we from having AI-enhanced static analysis tools that can accurately look at our C code (after the fact or while we're writing it) and say "this will cause problems, here's a fix" with a level of accuracy sufficient that we can just continue using C?
- tangled 1y agoThis feels like one of those rather rare projects that is both sailing pretty close to research, and also yielding industrially useful results -- I love it! Normally I'd expect to see something like this coming out of one of the big tech companies, where there are enough advertising megabucks to pay a small team to work on a project like this (providing someone can make the business case...). So I'm curious: what was the initial motivation for this work? Assuming this is not a passion project, who is funding it? How many person years of work has this involved? What is the end game?
- latchkey 1y ago> What is the end game? * Copyright (c) 2024-2025 Epic Games, Inc. All Rights Reserved.
- Culonavirus 1y ago"Filip Pizlo, senior director of language engineering at Epic Games, has created his own memory-safe flavor of C and – because why not?" https://www.theregister.com/2024/11/16/rusthaters_unite_filc/ https://www.theregister.com/2024/11/16/rusthaters_unite_filc... Good stuff!
- saagarjha 1y agoI think this is a passion project.
- pizlonator 1y agoYes
- RobertEva 1y agoPretty wild to see a concurrent, non-moving GC strapped onto plain C. If I can take a mid-size C codebase and trade ~2–3× runtime for fewer memory footguns, I’d take it. How rough is incremental adoption—per target, or all-in toolchain?
- discord9 1y agoThis is very cool, also I wonder does fugc works without InvisiCap, what would it be like without the capability pointer, does it just became not accurate but still usable?
- CMay 1y agoI love C, performance and security. Between this garbage collector and the capability enforcement, this is appealing. I've thought a few times about what a more secure C would look like, brushing over capability concepts here and there, but I don't belong near compiler code. How hard would it be to support Windows?
- lucideer 1y ago<off-topic> Took me far too long to understand your opening sentence; eventually realised the Oxford comma would've helped me out. Rare to see a clear example in the wild.
- falcor84 1y agoI would have also accepted a colon.
- kccqzy 1y agoThat would change the meaning.
- falcor84 1y agoWhy, what do you mean? My understanding was that it's a list of subjects of affection, so for clarity, I would rewrite > I love C, performance and security. as > I love: C, performance and security. How would it change the meaning? What am I missing?
- CMay 1y agoYour colon does not really solve ambiguity. They likely thought you meant "I love C: performance and security." which would make it more explicit, but it would also change the meaning and thus be incorrect. If I thought it was ambiguous enough to really try to fix, what I would probably default to is an elaboration. For example: "I love the intersection of C, performance and security." The meaning is not exactly the same, but it is more the same than your colon.
- gaanbal 1y agowow, this is really fugcing cool
- synergy20 1y agowill fil-c support ARM soon,for that matter, risc-v? safety is super important for embedded devices running c or c++
- classified 1y agoThe description left me confused. Is this something that has to be integrated into the compiler?
- jitl 1y agoIt’s an implementation of a very C compatible language called FilC. A fork of LLVM to add the Pizlonator compiler pass combined with runtime support stuff.
- VagabundoP 1y agoRelated, this is the Python garbage collector episode: https://www.podscan.fm/podcasts/corepy/episodes/episode-21-a-garbage-episode https://www.podscan.fm/podcasts/corepy/episodes/episode-21-a... I found it very interesting.
- illuminator83 1y agoIMHO Garbage collection is and always was an evolutionary dead end. No matter how nice you make it, it feels wrong to make a mess and have some else clean it up inefficiently at some point later. And because of that it always involves some sort of hidden runtime cost which might bite you eventually and makes it unusable for many tasks. I'd rather have my resource management verified at compile time and with no runtime overhead. That this is possible is proven by multiple languages now. That being said, I can imagine some C programs for which using Fil-C is an acceptable trade-off because they just won't be rewritten in language that is safer anytime soon.
- brazzy 1y ago> IMHO Garbage collection is and always was an evolutionary dead end. An evolutionary dead end that is used by probably upwards of 90% of all productively running code, and is the subject of lots of active research, as evidenced by TFA? > No matter how nice you make it, it feels wrong to make a mess and have some else clean it up inefficiently at some point later. > And because of that it always involves some sort of hidden runtime cost Because of what? Your feelings?
- zozbot234 1y ago> IMHO Garbage collection is and always was an evolutionary dead end. No matter how nice you make it, it feels wrong to make a mess and have some else clean it up inefficiently at some point later. There are problem domains where tracing garbage collection simply cannot be avoided. This is essentially always the case when working with problems that involve constructing arbitrary spaghetti-like reference graphs, possibly with cycles. There's no alternative in that case to "making a mess" and dealing with it as you go, because that requirement is inherent in the problem itself. It would be interesting to have a version of Fil-C that could work with a memory-safe language like Rust to allow both "safe" leaf references (potentially using ownership and reference counting to represent more complex allocated objects, but would not themselves "own" pointers to Fil-C-managed data, thus avoiding the need to trace inside these objects and auto-free them) and general Fil-C managed pointers with possible cycles (perhaps restricted to some arena/custom address space, to make tracing and collecting more efficient). Due to memory safety, the use of "leaf" references could be ensured not to alter the invariants that Fil-C relies on; but managed pointers would nonetheless be available whenever GC could not be avoided.
- Nick0981 1y agoJust skimmed through the docs - this is super interesting. Love the idea of a minimal GC with no runtime dependencies. Anyone here tested it with something more intense than toy benchmarks? Curious how it handles edge cases under memory pressure or concurrency. Also, would be great to hear how it compares to Boehm or Rust’s drop model in real-world workloads.
- maxuser 1y ago+1 to seeing a comparison to Boehm. I remember that being all the rage at the time, but then stopped hearing about it. I recall Boehm being a conservative collector, whereas Fil-C appears to be precise.
- brucehoult 1y agoI already tried to compare to Boehm on a toy program, but Fil-C didn't seem to GC at all! https://lobste.rs/s/q7b1gm/fil_s_unbelievable_garbage_collector#c_bwcbvi https://lobste.rs/s/q7b1gm/fil_s_unbelievable_garbage_collec...
- dan-robertson 1y agoI’m curious how expensive the write barrier is in practice? IIRC, it is often write barriers that most affect performance sensitive programs running on non-concurrent garbage collectors (and perhaps safepoints that can cause problems for performance sensitive threads when running with a concurrent gc).
- gok 1y agoHow hard would it be to add generational collection?
- xd1936 1y agoGreat name. Big RUNK energy[1]. 1. https://twitter.com/6thgrade4ever/status/1433519577892327424 https://twitter.com/6thgrade4ever/status/1433519577892327424
- gwbas1c 1y agoI skimmed the article. I'm curious about CPU / RAM overhead tradeoffs. IE, in may cases GC is more CPU efficient than reference counting, but the tradeoff is higher RAM consumption.