Tale of OpenBSD secure memory allocator internals – malloc(3)
bsdb0y.github.io
bsdb0y.github.io
OpenBSD does interesting stuff like this or pledge(2) and unveil(2).
Dragonfly does interesting stuff like their concurrent lockfree/lockless servers approach instead of using kernel locks, and HAMMER2[0].
Genode[1][2] implements multiserver systems supporting many kernels including seL4, making good use of capabilities.
[0]: https://gitweb.dragonflybsd.org/dragonfly.git/blob/HEAD:/sys...
Linux has a VFS with lockless path lookups. The push to get Linux running on machines like the SGI Altix, with at least 10240 cores running one shared instance of the kernel, has really helped with locking issues. Another factor has been the push for real-time performance, with and without choosing the option to make the kernel preemptable.
When the kernel isn't monolithic, kernel preemption isn't necessary, or worth it[0]. Imagine if instead of the, I argue insane, complexity added by the fine-grained SMP locks and the unholy mess that is kernel preemption, the kernel had been split into separate processes, which maps to SMP cleanly.
Actually, I don't have to imagine it, because that's what Dragonfly has been progressively doing since they forked FreeBSD, and what microkernel multiserver systems like Genode/seL4 or HelenOS are from the get-go.
It turns out, despite having very little manpower (which is why they chose to focus on x86-64), Dragonfly has performance and scalability competitive to Linux today. Imagine if they had more people. I will not be too surprised when Dragonfly finally leaves Linux in the dust and people wonder how the hell, which is something I predict will happen. Linux hit a ceiling despite all the money thrown into it. Dragonfly hasn't yet.
[0]: http://ts.csiro.au/publications/nicta_full_text/5859.pdf
But most BSD ( including OpenBSD which you just praised ) is monolith as well.
> I will not be too surprised when Dragonfly finally leaves Linux in the dust and people wonder how the hell, which is something I predict will happen.
Dragonfly would have to first leave FreeBSD in the dust before taking on all the linux distros.
Microkernels are great for learning about kernels. Monoliths have been great for general and corporate use. Perhaps the future is hybrid, only time will tell.
You're late to the party, as Dragonfly is already outdoing Linux in some areas, such as the network stack[0].
>But most BSD ( including OpenBSD which you just praised ) is monolith as well.
I praised them for the engineering they've been doing. They still retain flexibility, despite the monolithic design. Linux went all-in with their smp locking and kernel preemption, and the costs of getting any work done on the source code have skyrocketed since.
>Perhaps the future is hybrid, only time will tell.
Hybrid is a marketing term. It's a blurry line between a monolith and a so-called hybrid. What they're marketing is structure. Structure is good. Netbsd is an example of a well structured system. Linux is the counterpart: A poorly structured one.
>Monoliths have been great for general and corporate use.
UNIX is an old design. Corporate hates taking risks. However, there's massive scale deployments of microkernel systems, they're just not on your face; the visibility is actually quite low for these. But they do tasks that greatly benefit from or outright require such a design.
Monolithic design limits are more evident than ever, as we're hitting them left and right. So this is changing. For instance, besides systems such as Genode and HelenOS, Google is working on Fuchsia and Huawei on HarmonyOS. Brace for impact, as waves will be made when this all finally hits.
https://research.csiro.au/tsblog/using-rump-kernels-to-run-u...
Lock free path lookups are not a hack. It is a pretty amazing feat IMO. And the fact that it is done for all filesystems transparently in the VFS layer ... You couldn't do that on the Windows NT kernel for example (a microkernel design), because every filesystem driver has to figure out its own path logic there. Linux isn't known for good design all the time but it is a good design.
Windows NT isn't a microkernel design. It does however have some structure to it. Some call it Hybrid kernel, I call it crude layering. It's still better than the spaghetti Linux is.
>you couldn't do it
Each approach has different tradeoffs. With the microkernel multiserver approach, you get a lot of advantages, such as having a tiny amount of code running in supervisor mode, having strong separation enforced by it, particularly if using the capability model (not to be confused with POSIX capabilities). Possibly formally proven like seL4. It is possible to build a secure system on such a design. It is also possible to build a hard realtime (with proven WCET). It is not possible to do either with a monolith, because of the impossibility of proving the correctness of the monolith inherent to its sheer size and the exponential nature of verification work.
In detriment, there's more context switches, which have a cost. But this cost is an order of magnitude smaller on seL4 than Linux, for a solid example. You'd need a severe amount of extra context switches for an actual performance penalty. And seL4 would still have a massive advantage in latency.
>but you are just trolling here.
No, I am not, and I do not appreciate the accusation. Try and be kind.
It is not possible to implement a general purpose OS on a monolithic architecture. Try as you might you'll always fall short, because it's not possible to do hard realtime on a monolith no matter how much some pretend otherwise (no WCET means no hard realtime. Must have proof of not missing those deadline), nor is it possible to have security (huge TCB, no security. No amount of mitigation can do away with this fundamental problem). And thus, you'll always fall short of general purpose.
That's the point I'm making. Linux and all these other systems we use aren't general purpose operating systems. They're just stopgaps. They're due to be replaced. The question isn't if but when and by what exactly.
Due to the above, security is also in question. Spectre and related troubles take care of that.
Most people have a very different idea of "general purpose operating systems". It includes Linux.
Microkernels have huge problems. Reality disagrees with Andrew S. Tanenbaum. Simplification of components does not come free. Those simple components can have fiendishly complex interactions with each other. Some proven-secure microkernel systems are really insecure because all the buggy code has been shoved into parts that don't count for the security audit. Practical data structure choices become very limited, killing performance. Context switches have always been costly, and the situation has suddenly gotten far worse because we now require Spectre mitigation.
Remember also that performance problems are energy use problems. You might be willing to tolerate slowness, but consider battery life and the power fed into huge server farms.
A popular misconception is still a misconception.
>all the buggy code has been shoved into parts that don't count for the security audit.
I hate to repeat myself, but as explained above, at least the microkernel multiserver design has a chance of being secure, because it doesn't run more code than needed in supervisor mode, and isolates components individually.
A monolith cannot, because it has an excessively large trusted computer base, which makes cost of proof impractical.
>Microkernels have huge problems. Reality disagrees with Andrew S. Tanenbaum.
I refer you to the last installment of the Linus-AST debate[0].
>killing performance.
I recommend this article[1].
>Well, I guess nothing qualifies then, because you can't have a WCET on commodity hardware. You'd have to have a CPU without any kind of cache (branch history, TLB, etc.) and without any kind of instruction scheduling. You couldn't even have two cores sharing a bus, either on chip or on the motherboard.
seL4 has WCET for x86. It simply assumes the worst case for all of this. And it's still a good WCET. I recommend you read the paper[2].
[0]: http://www.cosy.sbg.ac.at/~clausen/PVSE2006/linus-rebuttal.h...
[1]: https://web.archive.org/web/20200216184858/https://blog.dark...
[2]: https://www.cse.unsw.edu.au/~cs9242/15/papers/Blackham_SCRH_...
The OS vendor produces a boot loader and a simple task switcher that can pass messages. This is somewhat badly proven to be free of bugs. It's unimpressive because there is almost no code or functionality.
Things like filesystems and TCP/IP stacks are full of security holes. None of that counts. All that buggy code gets linked into the user's app. Practically speaking, the app serves as a kernel without memory protection and the super-secure (Verified! Proven!) task switcher serves as a hypervisor.
OK, so maybe nobody can hack into the simple task switcher that is supposedly an OS but actually a hypervisor. The big fat juicy app, containing most of a kernel, is as secure as VxWorks 5 or MacOS 9. It's not a good sign if you need to copy-and-paste the code for an old BSD network stack into your app.
Maybe the theory is different, but in actual practice the above is really how the world of secure microkernels gets stuff done.
This[0] is the kind of work done around seL4.
As others mentioned on the thread, you praised OpenBSD, which is just as monolithic.
It's a pretty common opinion that the *BSDs are better architected as a whole unit and maybe a bit more care is taken with evolving kernel interfaces and so forth. I share that opinion.
But what I don't understand is that you are unwilling to see where Linux has done something well, and cite the monolithic design as the critical flaw. We have your counter example of OpenBSD (monoliths done well) and we even have some examples of good design in Linux (lock-free path caching in VFS). Linux, despite criticisms that you or I may have, is thriving pretty well in many domains as well, so I might be tempted to say the proof is in the pudding.
I still cite Windows NT as a microkernel design gone wrong, though I wouldn't confuse that as an inevitable property of microkernels. I am ex-MSFT by the way and have seen NT kernel source, and used to work on a filesystem driver there in 2008-2011. The NT I/O manager is this "message-based" thing, but the design that emerges from it is much worse than what Linux has, and the relatively bad I/O performance is a result. [In WSLv2, they opted to run a Linux kernel in a VM, rather than fix the inevitable performance consequences of the NT I/O design choices. The bad I/O performance of NT was specifically cited as a rationale for forking and embedding Linux.] It is actually a good example of how "microkernel" type thinking gives a poorer result if you are not careful about the big picture.
I am beginner into this.
And, yes, it is deep because OpenBSD malloc(3) has lots of features and I have tried to cover each and every line of code. So, I have shared all my learning and the process of how I learned.
In future, if people want to learn anything that requires malloc(3) understanding they can refer to this.
And, yes I have to paste the code otherwise it would be difficult to track the explanation and respective code.
I have explained the following things: - What is the code doing - Reason on why is it doing that - tried to explain the developers' idea behind that code algorithm - tried to explain the mathematical calculations on the basis of sample code through the debugger
And, the blog is for everyone, irrespective of ability to read C, or understanding of malloc(3) internals.
If you got lost then please keep patience because for me it took exactly 30 days to understand, still, I am learning it. At least read the whole blog again and then if you want, you can make the remark as per your understanding.
If you go through the whole blog, you will find out mailing lists and twitter links where the author discussed his queries and the reasons/ideas with the developer.
Hope I cleared your queries, if you still have some doubts then please read the whole blog again, or you can also directly jump into the source code and learn it from there.
As for OpenBSD, I wouldn't hold my breath: remember that Rust isn't the first 'safe' low level language but the others (Ada for example) didn't find success inside OpenBSD.
That said development follow fashions, so who knows?