9 ms·
The benefits and costs of writing a POSIX kernel in a high-level language
- thrill 8y agoThe paper contributes Biscuit, a kernel written in Go that implements enough of POSIX (virtual memory, mmap, TCP/IP sockets, a logging file system, poll, etc.) to execute significant applications. In experiments comparing nearly identical system call, page fault, and context switch code paths written in Go and C, the Go version was 5% to 15% slower.
- pjmlp 8y agoI would expect that slowdown to be more a consequence of optimizer implementations than anything else, given the quality of C compilers code about 30 years ago.
- Skunkleton 8y agoConsidering all of the stuff that Go does for you this is hugely impressive. It is especially impressive that a research kernel is within 10% of Linux's performance.
- justincormack 8y agoIt is missing a lot of stuff that is potentially time consuming, like access control.
- DblPlusUngood 8y agoWell that was fast! I'm an author of this paper and would be happy to answer questions.
- Immortalin 8y agoIs the code on GitHub?
- Kostic 8y agoAs it can be seen on one of the last slides, it is on GitHub[0]. [0] https://github.com/mit-pdos/biscuit https://github.com/mit-pdos/biscuit
- sitzkrieg 8y agointeresting 'x' commit messages ..
- skissane 8y agoMaybe sometimes the mental effort of writing a commit message just isn't worth it. At work, I try to be a good boy and write proper commit messages, always. On personal projects, I often just use "." or something equally meaningless. Sometimes I can't be bothered explaining myself, and on a personal project nobody is going to be burned by it but me.
- craftyguy 8y agoWell... except in this case they referenced the repo in a paper, so of course folks are going to have a look, fork it, play with it, etc.
- jonathonadler 8y agoA quick scan suggests these commits are comment changes only.
- twic 8y agoThe recent ones are. There are a few further back in history which are substantive changes. Any thoughts on what this change did: https://github.com/mit-pdos/biscuit/commit/b262c40b1baf1fb1ae43f5f25eae37cd8c36b053 https://github.com/mit-pdos/biscuit/commit/b262c40b1baf1fb1a... ?
- Immortalin 8y agoAny plans to borrow code from gVisor to attain full Linux compatibility?
- Someone 8y agoFor the ”C kernel vs go kernel” benchmarks, the paper writes ”The benchmarks allocate no heap memory in steady-state, so Biscuit’s garbage collector is not invoked.”. Is that a fair way to make this comparison? Also, ”This results in heap bounds of less than 500kB for all system calls but rename and fork (1MB and 641kB, respectively).” How does that compare to the C-based kernel? Finally, how does this system hold up after days of uptime?
- DblPlusUngood 8y agoConcerning your first question, that experiment is not intended to measure the cost of GC, which can be made small by trading memory. The point of this experiment is to measure the unavoidable costs of the language.
- Someone 8y agoI would think that measures less costs of the language than costs caused by differences in compiler quality/focus. Or are there go features that make it inherently slower than C for kernel programming, even when ignoring GC?
- frankmcsherry 8y agoI'm not at OSDI or I would have asked there, but: 1. Your skepticism for using Rust cites [26], the PLOS paper from the same people who did [27]. They've essentially recanted, in that their PLOS talk was right after Niko's keynote, and he then talked them through how interior mutability works in Rust. Other than [26], are there other lingering concerns? I could imagine so, but it would be great to take stock. 2. You don't seem to page to disk, and do OOM shootdowns instead. If you did enable disk paging, how comically bad an idea does a tracing GC become? :D Naively, I could imagine RC-GC being less horrible, but perhaps that's my built-in (and absolutely for real) bias.
- DblPlusUngood 8y ago1. I wouldn't say we are skeptical of Rust, I'm sure it could be made to work well and we would love to see such a Rust kernel! I do wonder whether it would be harder to implement highly-concurrent data structures in Rust though, such as the directory cache. 2. GC performance would be basically unaffected by paging, since kernels don't page their own heaps out to disk and thus a kernel heap access would never have to wait for a disk IO. Or maybe you had something else in mind?
- frankmcsherry 8y ago1. Jon sits two desks away, right? ;) Re 2., I assumed (incorrectly, it seems) that virtual memory mappings can eventually spill to disk. If you grab 1/32 of RAM For the kernel, then you could only virtually map 16x RAM if the page tables have 512 entries. Admittedly, I took my OS class in the previous millennium, so I might be out of date here...
- blt 8y agoNon sequitur, but is Cody Cutler (you?) related to Dave Cutler, the designer of VMS and Windows NT? Maybe OS programming runs in the family :)
- DblPlusUngood 8y agoHah, I am Cody and I'm not related to Dave Cutler (as far as I know!).
- throwaway5250 8y agoIntriguing. Interesting that it implements fork(2), even though Go itself cannot really deal with that call.
- anyfoo 8y agoThough implementing fork() in a kernel is entirely distinct from using fork() in user space. Implementing fork() is mostly "just" manipulating a bunch of data structures the right way. Copy the right bytes and set the right values. It's like how you can implement Java, C++, python, Haskell and any other (practical) language in C, despite C having no support for e.g. classes or lambdas. Or how humans can design and build combustion engines, despite us not having the capability to ingest gasoline in order to rotate an axle at 6000rpm ourselves.
- throwaway5250 8y agoYeah, I get the difference in levels of abstraction. Still interesting, at least to me. Among other things, it limits how "thin" the POSIX emulation can be. So, for example, if I had a POSIXy super-CPU, an implementation of fork() in C, running on that CPU, could be rather thin. An implementation of fork() in Go seems like it'd necessarily have to be considerably thicker, as fork() is more foreign to Go. But yes, I understand that this noodling has little to do with what the authors were going for, nor really with current reality. Definitely a cool--amazing even--project.
- aidenn0 8y agoI fail to see how the implementation of fork in C would be any thinner than an implementation of fork in Go. I expect the implementations would look very similar.
- anyfoo 8y agoThat sounds more like some kind of unusual “emulation layer” in user space than any “kernel”, and given your decision to use the host environment’s fork(), apparently one that just uses the host operating system’s (that’s what that “Super CPU” is, not a CPU at all but a full operating system) process model and everything associated with it, so you wouldn’t be able to emulate much.
- ilovecaching 8y agoI would love to see a production ready kernel written in Rust adopted by the industry. I am exclusively using Go and Rust at home and at work, and I find myself equally productive in both. Go lacks a lot of 'high level' features for a GC language, so I don't find the GC to be that advantageous. Rust is safe, fast, and a joy to write. I'm not surprised by these numbers, I would be interested to see a breakdown of compile times for similarly sized kernels in Rust, Go, and C.
- dorfsmay 8y agoProduction ready means different things to diff people, and I don't know how many people use it in Prod, but have you looked at redox: https://github.com/redox-os/redox https://github.com/redox-os/redox
- kbenson 8y agoIt would be really interesting to see a Linux ABI layer implemented on top of redox, a la IllumOS, to allow software designed to run on linux to run. Given that Bryan Cantrill is gung-ho about rust, and he's got quite a lot of knowledge in this area, maybe someone can woo him to help (even if in an advisory role).
- mlinksva 8y agoThe Redox leader did ask https://twitter.com/jeremy_soller/status/1042261893367250944 https://twitter.com/jeremy_soller/status/1042261893367250944
- lima 8y agoWhile not a full kernel, Google's gVisor is a userland Linux kernel emulator written in Go: https://github.com/google/gvisor https://github.com/google/gvisor They use it in production for App Engine sandboxing.
- XorNot 8y ago"Production" - they won't commit to actually supporting it for production for the rest of us (currently got app engine flex burning a hole in our pocket at work because the old runtime was too problematic and sans it being out of beta we can't move to the new one).
- xenadu02 8y agoAn unoptimized research kernel using GC (instead of ref-counting or Rust-style lifetimes) manages to get within 5-15% of a traditional kernel for the things they measured. That is impressive. Lots of asterisks and caveats apply I'm sure, but it bolsters the argument that writing kernels and device drivers in a high-level safe language wouldn't impose the 2x or worse perf penalty detractors like to claim. I know I'd trade 10% perf for the elimination of whole classes of security vulnerabilities. (For the same reason, I want the standards committee to produce a bounds-checked dialect of C where I can choose to pay some perf cost to get real dynamic and bounds-checked arrays)
- dymk 8y agoCompanies managing large houses with many thousands of computers care about efficiency gains in the sub-percent range - so even a 5% performance penalty is entirely a no-go. I doubt the kernel is nearly as featureful as Linux, either. Now, could one of these academic kernels have sheer engineering effort put into optimizing that 5-15% regression away? Probably.
- wmf 8y agoOr just don't use GC.
- btilly 8y agoWhether reference counting or GC is more efficient depends on your workload. There are common workloads where reference counting is better. And others where GC is better. In general neither can win. So saying "just don't use GC" as a answer to improving throughput shows ignorance. So what are the real tradeoffs? GC is less work. Is easier to get right. And lets you handle complex self-referential data structures more easily. Reference counting lets you handle real-time constraints more easily. Is simpler to understand. And results in faster freeing of potentially scarce external resources.
- dymk 8y ago
- deleted 8y ago[deleted]
- duckqlz 8y agoSince when did C stop being a high level language O_o?
- Const-me 8y agoI think it's a moving target. 70 years ago, assembly was high-level.
- aaronmdjones 8y agoSome would argue that it still is. https://blog.erratasec.com/2015/03/x86-is-high-level-language.html https://blog.erratasec.com/2015/03/x86-is-high-level-languag...
- Animats 8y agoInteresting. It's not that Go is a "high level" language, it's that it is garbage collected. What happens if it runs out of memory?
- pjmlp 8y agoThe same that happens to the Linux kernel I guess.
- cdoxsey 8y agoThis is covered in the paper. They use static analysis to know the memory costbof a kernel function and rather than optimistically run the kernel function and then unwind it if they run out of memory, they delay it until memory is available.
- jaunkst 8y agoGC can make high demand applications stutter. From a performance and security prespective I think rust makes a great candidate for a HLL kernal.
- pjmlp 8y agoGC enabled system programming languages like D, Active Oberon or Modula-3, among others, allow for many ways to allocate memory, it is not GC all the way down.
- jstewartmobile 8y ago5-15% seems like a bargain compared to the massive slowdown everyone noticed after the first meltdown patches (not that this would have fixed that problem, of course). If this approach took off, maybe it would light a fire under the chip industry to put a little more thought into hardware-assisted garbage collection.
- bitwize 8y agoBut what did the memory footprint look like compared to C?
- nineteen999 8y agoLast time I looked (which was a while back) both Go and Rust binaries for "Hello world" were over a megabyte with out-of-the-box settings, compared to just a few kilobytes for C and slightly more for C++. I should qualify that they were the simplest of Hello world programs, I didn't add any fancy options to try and reduce the size at all. I'd be keen to see what the smallest binaries the reference implementations of these languages can produce are.
- steveklabnik 8y agoRust's standard library is statically linked, C's is not. You have to compare the total size. Additionally, Rust includes jemalloc by default on many platforms. If you really want to get extreme with this, http://mainisusuallyafunction.blogspot.com/2015/01/151-byte-static-linux-binary-in-rust.html http://mainisusuallyafunction.blogspot.com/2015/01/151-byte-..., while a bit old, talks about various things that are still true, though some stuff has changed a bit. There's also https://www.rust-lang.org/en-US/faq.html#why-do-rust-programs-have-larger-binary-sizes-than-C-programs https://www.rust-lang.org/en-US/faq.html#why-do-rust-program... Additionally, some people have done more work since then; the smallest binary rustc has ever produced is now 145 bytes: https://github.com/tormol/tiny-rust-executable https://github.com/tormol/tiny-rust-executable
- nineteen999 8y agoThanks - yes I meant to mention, that statically linked (and stripped of symbols) I get 745k for the C hello world with gcc 7.2, so the gap isn't as big as all that. I understand that shared libraries/dynamic linking is still a WIP for rust so it's not exactly a fair comparison yet. With a shared standard library you also get the benefit of having the RAM shared across multiple processes. The 145 byte example also not being a fair comparison, since you've left out the standard library! Obviously C can do that too, but it's pretty neat to see the progress rust is making. (anyway, I'm going off topic since we're discussing kernel programming here).
- Senderman 8y agoThe misplaced hyphenations mid-paragraph in that abstract made me vocalise the text in my head as a reader with hiccups.
- lapinot 8y agoThats the sad state of (i guess) automatic pdf text extraction, consequence of research papers being exclusively in pdf, consequence of (la)tex coming from another age. I love and praise tex for what it allows to do, but my opinion is that now is the time to get past it, learn everything it has done right and apply the new knowledge we have in language design to get a better surface language (lower friction syntax, higher-level semantics allowing to separate structured content from typography and extract other stuff than a visual document from a source file). Tex being so good means it has such a monopoly that this kind of project have to be tremendously good to have a chance (which is probably a good thing).
- xvilka 8y agoPOSIX itself an outdated standard. Some things we're designed without understanding of modern security and portability problems. Either new iteration of the standard required, or a new standard from scratch.