This paper presents an evaluation of the use of a high-level language (HLL) with garbage collection to implement a monolithic POSIX-style kernel. The goal is to explore if it is reasonable to use an HLL instead of C for such kernels, by examining performance costs, implementation challenges, and programmability and safety benefits.
The 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. Biscuit makes liberal use of Go’s HLL features (closures, channels, maps, interfaces, garbage collected heap allocation), which sub- jectively made programming easier. The most challenging puzzle was handling the possibility of running out of kernel heap memory; Biscuit benefited from the analyzability of Go source to address this challenge.
On a set of kernel-intensive benchmarks (including NGINX and Redis) the fraction of kernel CPU time Biscuit spends on HLL features (primarily garbage collection and thread stack expansion checks) ranges up to 13%. The longest single GC-related pause suffered by NGINX was 115 microseconds; the longest observed sum of GC delays to a complete NGINX client request was 600 microsec- onds. 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.
Scientific papers about operating system experiments – who doesn’t love them?
We often debate this very topic without having good data to talk about. This should make for good points of discussion.
Personally I’ve been leaning towards achieving memory safety through static language analysis rather than garbage collection, but this is very interesting none-the-less. These performance tradeoffs may be worthwhile in some security contexts.
With garbage collection, additional memory usage is to be expected, but I do wonder if the performance could be improved upon with further optimization.
The one I wonder about it: I always get the impression Rust would be a better choice than Go. Because Rust doesn’t use GC, uses less memory and less CPU and is faster in a lot of cases.
Lennie,
I think so too, but right I’d welcome development in any of them because I feel change is long overdue.
High level developers have been more adventurous with new languages like python, coffeescript, ruby, etc, but most low level systems programming hasn’t embraced change. I’m just as guilty as anyone. The barrier for me is that the current tools are so well established that retooling/rewriting everything to basically get what we already have is a really hard sell. Of course security is a pro for switching, but investing in platforms with an uncertain future with rather limited support and requiring niche developer skills can be difficult to justify. For better or worse, there are efficiencies to be had by following the big crowds, regardless of if it’s the best choice or not.
Well you can combine Rust and C(++) and I assume assembly language in the same project.
Because Mozilla is doing it for their C++ code base:
https://research.mozilla.org/servo-engines/
“Hopefully, Rust is a pretty intuitive language for C++ programmers. Most of the syntax is pretty similar. The big difference (in my experience) is that the sometimes vague concepts of good systems programming are strictly enforced by the compiler. This can be infuriating at first – there are things you want to do, but the compiler won’t let you (at least in safe code), and sometimes these things are safe, but you can’t convince the compiler of that. However, you’ll quickly develop a good intuition for what is allowed. Communicating your own notions of memory safety to the compiler requires some new and sometimes complicated type annotations. But if you have a strong idea of lifetimes for your objects and experience with generic programming, they shouldn’t be too tough to learn.”
https://github.com/nrc/r4cppp
To be honest, given that the best case performance advantage of Linux over biscuit was about 10%, and that was using RAM disk based I/O, and given that once an SSD based test was included that performance got to within 2%, that says to me performance is perfectly adequate for most use cases.
We’ve paid a bigger performance hit than that with Spectre and Meltdown mitigation.
christian,
This is a hand-wavy answer, but that fact that you can manually prove using logic that two threads can not deadlock nor mishandle pointers means that a software algorithm could implement the same logical rules to prove the same conclusions about correctness. Most languages can’t do this because the code is assumed to be correct and the programmer’s intent of pointer ownership is not conveyed. But if you have this information, then in principal, static analysis can prove code correctness even across threads.
Rust has taken this concept and run with it, all with static compile time analysis and no runtime overhead. It’s one of the reasons I wish it would be used more.
https://blog.rust-lang.org/2015/04/10/Fearless-Concurrency.html
C is not a low level language: https://queue.acm.org/detail.cfm?id=3212479
I would suggest not to start this again.
Why? Is your computer a PDP11?
Mine is. It, however, isn’t exactly fast…
What is Fuschia written in, C++?
A mix of C++, Rust, Go and Dart.
The kernel process, most drivers and UI composition engine are in C++.
The TCP/IP stack, disk management utilities are in Go.
Rust is minimally used still.
The UI framework is Dart, as it makes use of Flutter.
Coroutines will be coming to C++, and so will heap elision. They both have working implementations, leading to what some call “negative overhead abstractions”.
The one thing that smells slightly to me is that they changed the code paths in an existing C kernel to be more like what they had written in Go.
Different languages encourage and allow different operations and methodologies, and make different guarantees. I think a better comparison would be a “natural” C kernel and a “natural” Go kernel, both with similar effort put into optimization.
Linux and BSDs have had decades, and man-millennia of effort put into optimization. It’s not reasonable to expect a new Go kernel to even approach that sort of effort.
What I mean is that what is idiomatic in Go is not idiomatic in C, and that will change the results.
In C, you very often tightly pack structures, where in a GC’ed language this is not nearly as natural (and in some cases not possible). You often rely on non-exhaustive logic in the small scale and partial structure initialization, both of which are usually frowned upon in other languages.
I don’t know a lot of Go, but many languages provide very easy to use systems that are extremely verbose in C (interfaces, exhaustive disjunctions, compiler-verified memory region re-use), as well.
Making the C similar to Go will cause the benchmark to be “If I make C look like Go, which is faster?”, which I very much suspect will not favor C as much as what idiomatic C would compared with idiomatic Go.
Idiomatic C often results in things like leaked buffers, buffer overruns and buffers used after they’ve been free’d.
I personally like C the language, but would happily dump many of it’s idioms which are based around it’s limited runtime environment.
What I most miss from other languages, for example, are things like nice exception handling and nice standard library constructs for strings and data collections.
GC got me in hot water the other week, so I won’t mention that
I never said it was better to use C. But I think you’re close to the point I’m trying to make: C encourages different things than Go. Comparing C made to look like Go doesn’t make as much sense to me as comparing “normal” C and “normal” Go. The results will be different. Go will probably have fewer bugs, but C will probably be faster and use less memory. I strongly suspect making C look like Go will reduce the gap in both case.
Yes, when you do slow things in C, of course you’ll reduce the gap. But a 15% improvment in important parts of an OS kernel is nothing to sneeze at. If a Go kernel requires a significant slow down to be safe, then the kernel won’t be used, meaning it has added nothing to safety landscape.
Very much depends on your use case. Desktop and HPC will be largely CPU bound, but CPU bound at user level, so not involving the kernel much.
Anything that is storage I/O bound will find the storage system is the bottleneck, and the kernel simply becomes an occasional arbiter of disk I/O.
The main use case I can think of where this Go kernel might be a problem is anything requiring very low latency. So, for example, high throughput network routing. A 15% dip in performance here might add 15% to the bottom line latencies, and a corresponding loss of throughput.
Anywhere else, that performance lost will be eaten by Moore’s Law in a couple of months. Otherwise, it’s just 15% on top of typically less than 15% kernel time for the other use cases.
I, personally, would happily pay that price on any of my (non low-latency critical) computers.
christian,
Moores law died for single threaded performance several years back. We keep adding more transistors, but in practice this translates into more cores, which might not do as much to counteract increased kernel overhead occurring on every core.
I’ve stated my opinion on Garbage Collectors before, I prefer the deterministic behavior of explicit frees, which often go hand in hand with destructors, but it’s still an interesting problem to me and it’s fun to have these kinds of discussions!
Those additional cores are what allows concurrent marking. My GC probably (I’ve not measured it yet, mind) spends most of its time marking live data, chasing pointers from the various roots. Being a slab based allocator, marking a block of memory is simply a matter of bit twiddling to the mark bitmap as to mark the block as in use. Once everything is marked, the mark bitmap simply becomes the in-use bitmap used when allocating new memory from the heap. The sweep stage of my GC is simply replacing the in-use bitmap with the mark bitmap. If there are no finalizers declared for a slab type, that’s it, no more to do. If a finalizer is defined, it has to be called with each block that is now determined to be dead, but I’ve only actually used the finalizer for testing.
This is work that can easily be done in parallel with other useful work, and adding more cores just makes it truly parallel. It can even operate concurrently with memory allocations in other threads/cores, as an allocation can simply spot the case of an in progress GC, and redo any marking of the newly allocated block in the mark bitmap.
For low latency work, there is nothing stopping you pre-allocating all the memory buffers you’ll need, so there’ll be no requirement to call the allocator and potentially hit any pauses. Your low latency, high priority task can simply preempt any in flight GC as required.
Perhaps this discussion would be best moved to forum.osdev.org?
christian,
Perhaps, I’m not sure I have enough motivation to though, haha.
Edited 2018-10-10 14:55 UTC
This is all very much theoretical at the moment, as I’m uni-processor only at this point, and GC when idle, so there can be no race conditions.
What I envisage, though, is that the GC can mark all threads that are not running. The running threads can continue on their merry way, and if they call into the allocator at all, they can take that opportunity to briefly stop and mark their own thread roots, mark whatever it is they’ve just allocated, then continue on. Else, they can spot the outstanding GC in progress at their next schedule point. Or, if GC is invoked because memory is really low, they can be interrupted with an IPI to finish their portion of the marking as soon as possible. This last case would be the main potential problem, as IPIs are relatively slow and the remaining marking of unknown bounds, though most of the live data should have already been marked (we don’t mark memory twice, we ignore already marked data.)
christian,
Ok. The thing I’d be concerned about is one thread modifying a reference at the same moment the GC is trying to scan/mark it. You could obviously use locks, but performance would suffer. Anyways it’ll be interesting to hear from you when you get to implementing SMP.
How about your battery-powered handheld computers? 15% of its charge being used to clean up garbage?
kwan_e,
It’s not 15% overall because the phone won’t be running inside the kernel 100% of the time. It’d be more in the ballpark of 2% overhead overall depending on how much time is actually spent in the kernel. I personally wouldn’t push for GC in the kernel, but at the same time I don’t necessarily think it’s an unreasonable idea. To the extent that someone wants to try, I say go for it, we could all learn from their experiences, both positive and negative
In these cases, I’d fully expect them to be written in easier, higher level languages, with security policies designed around human flaws. But that takes us out of kernel space and malevolent parties would get better results with phishing and social engineering rather than hoping to trigger a kernel bug.
For sure, memory access bugs dominate CVEs, but I feel like there have been more security breaches traced to the end-user side (and middleware bugs, such as SQL injection attacks) than have been traced to memory access bugs.
kwan_e,
Arguably many kinds of bugs can be effectively neutralized at the library/language level when we approach the problem with an eye for safety. SQL injection used to be a huge recurring problem when the standard practice for building SQL commands was to concatenate strings. Now we have better ways to do it: SQL parameters. SQL injection can be virtually eradicated (except for those who insist on not using parameters). As an added benefit, SQL parameters can eliminate data conversion overhead and help the SQL parser lookup cached queries.
It’s kernels all the way down.
According to the Linux Security Summit 2018 talks, 68% of the kernel exploits were caused by out-of-bounds memory corruption.
Yes, but how many of them lead to actual security breaches. An exploit does not necessary lead to an actual incident. You can have exploits for every part of the kernel, but have they actually resulted in sensitive data being accessed?
Compared to when government employees just leave hard drives around, or banks who lose a truck full of backup tapes, or a shopping website leaving customer details in plain text accessible from the internet.
kwan_e,
The corollary to this argument is how many breaches are unreported or even undetected? Many companies would rather hide their vulnerabilities…
http://www.osnews.com/story/30776/Google_exposed_user_data_chose_to…
What language is G+ written in?
And what language would most programmers use to exploit that hole? Facebook’s written in PHP.
Kernel bugs would require significant resources to actually be exploitable. On the level of state actors, like what happened (allegedly) with Stuxnet. So obviously, if these kind of breaches are common, then of course we won’t hear about them much because they are state secrets on both sides.
On the other hand, if kernel bugs would lead to “consumer level” breaches like the above, and the others I mentioned, surely we would have heard a lot more by now, just by the sheer numbers of attack vectors and attackers. Otherwise you’d have to imagine some kind of conspiracy where companies only leak/report breaches based on the language used to write the system that was breached…
—————–
So this is not to downplay the severity or commonality of memory access CVEs. For sure, we must treat potential security exploits almost as seriously as actual ones. But Linus Torvalds also does have a point about the security industry being attention whores. Every bug that leads to a security exploit is advertized as if they were the end of the computing world if they were not fixed yesterday. The reality, though, is that the proof-of-concepts to show the exploit in action requires significant hoops to jump through to work, compared to the ease of phishing and social engineering, or incompetence.
Edited 2018-10-11 22:26 UTC
kwan_e,
I just don’t see the point in calling the security industry attention whores for recognizing the widespread security problems with C. I suspect that everyone in this thread would all agree that phishing and social engineering are also problems, however in the context of an article about “the benefits and costs of writing a posix kernel in go”, it makes a ton of sense to take a critical look at the computer languages themselves.
But Linus’ point was that’s not what they’re doing. They over-dramatize a lot of kernel exploits that would have required a sufficiently compromised machine to begin with, blowing everything out of proportion. That’s what makes them, in his view, attention whores. The “widespread security problems with C” is not as widespread as is claimed, given my argument above about how exploits have rarely been converted into actual incidents.
Actually they were, many of those exploits were used while attacking Android devices, as those statistics were shown by Google at their Summit talks.
Which is why Google is driving the Kernel Self Preservation Project.
Using C is like using butcher knifes with chain gloves, driving without car belts or motorbike helmets.
Some people have luck all their lives, others unfortunately not.
Edited 2018-10-12 06:59 UTC
kwan_e,
Well he’s often been overly defensive and dramatic himself. However I’d need to see exactly what Linus said, otherwise I risk taking “his” point out of context. If he did say kernel exploits don’t matter because they require a sufficiently compromised machine to begin with, it’s still just an excuse in my book since privilege escalation attacks can escalate a modest attack into a highly damaging one.
If a different programming paradigm can exterminate one class of bugs entirely, that’s an objective ‘pro’. Of course there are usually pros and cons to consider, performance often being cited as the con for managed languages. Honestly I really do enjoy low level coding, I always have, but after having witnessed the same critical flaws for decades I know that if we keep doing things the same way, we’ll be destined to repeat these flaws over and over again. This is why I welcome research that attempts to make code safer while finding ways to minimize the cons.
He didn’t say that, and neither am I saying that, or saying he said that. It’s about proportion. In one of his mailing list rants, he was talking about how security people like the solution for everything to be “if this process violates some security, we must kill it.” The fact is the kernel sees a lot of violations that are the result of harmless bugs in userspace programs. It does no one any favours when any buggy program is killed outright, giving users the impression that the system is unstable.
It’s this kind of response that is out of proportion, in his view.
kwan_e,
He’s entitled to his opinions too, but if you’d like to discuss something specific that linus has said, it’d be better to have a link.
First page on Google:
https://www.theregister.co.uk/2017/11/20/security_people_are_morons_…
kwan_e,
It’s just his usual expletive self, cool. I don’t see what it adds here exactly.
Edited 2018-10-12 22:33 UTC
Self,
Oops, I’ve got to laugh at my own typos sometimes!
Did you not read the linked-to LKML rants? He does make a good point about how to actually go about fixing security issues. Screwing over users is not the way to go about it. It’s ironic that for all of Torvalds’ abuse, he cares about users more than the polite security people. Not that it excuses his abuse.
And I’m saying there is something to be said about using certain language features degrading performance by 15% that has the “security over users” attitude. Certainly, it’s not as bad as “let’s kill the process/system” kind of disregard for users.
kwan_e,
Well, I’ve acknowledged that performance is a potential negative. Yet it’s a cost that some would still find beneficial anyways. I think it would be fair to say that we’ve been releasing software that is both slow AND non-robust for quite some time now. In other words, we’ve collectively neglected both software security and efficiency.
In theory, it could be good news because it means we should find enough speedups in X to offset the overhead of Y. Compile time safety enforcement could be even better. The bad news is that we find ourselves in a race-to-the-bottom that dis-incentivizes long term solutions.
I’m really irked by the code quality of many projects that get thrown my way on a regular basis. My urge is to fix them, but few clients want to pay for that time. In many ways the relationship between clients and myself is similar to that of clients at an automobile mechanic: they question the need for me to do the work in much the same way I question the need for a mechanic to do the work.
Tell me about it. I inherited a codebase from someone who did all he could to tick the management boxes to get promoted, but couldn’t design or code anything. I’m the one who had to deal with customer issues, like not even getting it installed and working, taking up all my time and the customer’s patience. But he gets the promotions and pay raises for doing a shit job. And at the same time, me reducing the number of customer complaints and time-wasted by the maintainers who came after by simply designing things properly doesn’t get any recognition.
I just wish there were retroactive demotions, but instead we get people promoted to spread their brand of incompetence on a wider scale.
Such as?
(maybe post-fact we can have a laugh out of this 
)
Edited 2018-10-13 13:44 UTC
You mean the codebase, or the box ticking?
The code base was an Eclipse client and a custom server written in Java, proof that no safe languages can prevent people making stupid design choices. The only thing it had going for it was that it was safe* because no one wanted to fucking use it, or they couldn’t install it.
As for the box ticking, the company culture was that you have to have high visibility, and talk yourself up all the time, to get promoted. Nothing about the quality of the work they’re doing at the moment, or the costs to other people when their shoddy work blows up soon after they get promoted to a better position.
* Actually, no it wasn’t safe because one of the issues was that it used Java’s serialization that was later shown to have security flaws.
I meant box ticking.
…but this leads to question, why do you put up with this?
And an even better one: why won’t you make yourself promoted? 
zima,
This is a discussion I’d really like to have, but I think it’s too late to have in this article with comments about to close. I don’t know if you can bring it up organically elsewhere? We could just hijack another discussion, haha.
BTW, in ending: today I had a dream with Alf …and a cat.
It was a large corporation, shall we say, so there’s a lot of processes that are basically meaningless at assessing an employee’s performance or worth. So that system doesn’t work for a lot of people who aren’t natural self-promoters. I, like many others here, prefer if our work speaks for itself. But the company had been taken over by salesmen and MBAs, and they have no clue about how to manage and assess employees of a technical industry. They’re people guided by meaningless short term targets and oneupmanship so of course that’s going to reflected in employee assessment.*
To be fair, I only put up with it for 9 years in total. I would have left sooner, but I felt I had responsibility to not leave behind a pile of shit like the people before me did. Also, in Australia, you can only get your 10th year long service leave as a pro-rata payment after 7 years of employment
* The ironic thing is, the highest employee rating I got was from the same fellow who got promoted to be a manager and became my manager for a while. Given the work I was doing at the time, I figured out that the only reason he gave me a higher rating was because it would look good on his promotional box ticking for advancing beyond manager. Most managers can’t give more than the average rating because that would mean the company had to pay out more in bonuses. And guess what? He did get promoted not long after.
Edited 2018-10-13 18:24 UTC
kwan_e,
Sorry for my ignorance, but can you explain what this means? Is this like some form of “social security” to use US-centric terminology?
In Australia, you get extra leave for the 10th year that you’ve been with your employer. That applies even if your employer is US-based, as mine was. However, you can opt to get paid out instead (or if you’ve been made redundant or resign), but only after 7 years, at which point you’ll be paid proportionally.
Apparently it hearkens back to colonial times when long service leave was used to sail back to England to visit home for a while.
kwan_e,
I bet female workers get paid maternity leave too. What a bunch of socialist crap.
/sarcasm
My wife had no pay or benefits during maternity leave. So I was on the hook for $1400/mo for family heath insurance during her leave since my job doesn’t cover it. We’re actually lucky her gov job pays family health insurance, many in the private sector have it worse.
The “primary carer” gets paid parental leave from the government, and either parent can receive any parental leave payments an employer may provide too.