News for hackers. Stuff that matters.
Re:The Linux realtime preemption endgame is near by Animats on Thursday November 16, 2023 @02:26PM (#38294148)
QNX had this right decades ago. The microkernel has upper bounds on everything it does. There are only a few tens of thousands of lines of microkernel code. All the microkernel does is allocate memory, dispatch the CPU, and pass messages between processes. Everything else, including drivers and loggers, is in user space and can be preempted by higher priority threads.

The QNX kernel doesn't do anything with strings. No parsing, no formatting, no messages.

Linux suffers from being too bloated for real time. Millions of lines of kernel, all of which have to be made preemptable. It's the wrong architecture for real time. So it took two decades to try to fix this.

Re:The Linux realtime preemption endgame is near by vacuity on Thursday November 16, 2023 @02:37PM (#38294319)
For a modern example, there's seL4. I believe it does no dynamic memory allocation. It's also formally verified for various properties. (Arguably?) its biggest contribution to kernel design is the pervasive usage of capabilities to securely but flexibly export control to userspace.
Re:The Linux realtime preemption endgame is near by adastra22 on Thursday November 16, 2023 @03:03PM (#38294708)
Capabilities are important, but I don’t think that was introduced by seL4. Mach (which underlies macOS) has the same architecture.
Re:The Linux realtime preemption endgame is near by vacuity on Thursday November 16, 2023 @04:30PM (#38295825)
I didn't say seL4 introduced capabilities. However, to my knowledge, seL4 was the first kernel to show that pervasive usage of capabilities is both feasible and beneficial.
Re:The Linux realtime preemption endgame is near by monocasa on Thursday November 16, 2023 @07:16PM (#38297543)
The other L4s before it showed that caps are useful and can be implemented efficiently.
Re:The Linux realtime preemption endgame is near by vacuity on Thursday November 16, 2023 @08:24PM (#38298069)
https://dl.acm.org/doi/pdf/10.1145/2517349.2522720

" We took a substantially different approach with seL4; its model for managing kernel memory is seL4’s main contribution to OS design. Motivated by the desire to reason about resource usage and isolation, we subject all kernel memory to authority conveyed by capabili- ties (except for the fixed amount used by the kernel to boot up, including its strictly bounded stack). "

I guess I should've said seL4 took capabilities to the extreme.

Re:The Linux realtime preemption endgame is near by naasking on Friday November 17, 2023 @10:48AM (#38305176)
seL4 was heavily inspired by prior capability based operating systems like EROS (now CapROS) and Coyotos. Tying all storage to capabilities was core to those designs.
Re:The Linux realtime preemption endgame is near by adastra22 on Thursday November 16, 2023 @07:54PM (#38297847)
There's quite a history of capabilities-based research OS's that culminated in, but did not start with L4 (of which seL4 is a later variant).
Re:The Linux realtime preemption endgame is near by vacuity on Thursday November 16, 2023 @08:12PM (#38297979)
Yes, but I believe seL4 took it to the max. I may be wrong on that count, but I think seL4 is unique in that it leverages capabilities for pretty much everything except the scheduler. (There was work in that area, but it's incomplete.)
Re:The Linux realtime preemption endgame is near by adastra22 on Thursday November 16, 2023 @08:57PM (#38298322)
L4 was developed in the 90's. Operating Systems like Amoeba, which were fundamentally capability-based to a degree that even exceeds L4, were a hot research topic in the 80's.

L4's contribution was speed. It was assumed that microkernels, and especially capability-based microkernels were fundamentally slower than monolithic kernels. This is why Linux (1991) is monolithic. Yet L4 (1994) was the fastest operating system in existence at the time, despite being a microkernel and capability based. It's too bad those dates aren't reversed, or we might have had a fast, capability-based, microkernel Linux :(

Re:The Linux realtime preemption endgame is near by josephg on Friday November 17, 2023 @07:49AM (#38302784)
How did it achieve its speed? My understanding was that microkernel architectures were fundamentally slower than monolithic kernels because context switching is slower than function calls. How did L4 manage to be the fastest?
Re:The Linux realtime preemption endgame is near by vacuity on Friday November 17, 2023 @10:00AM (#38304451)
Two factors are the small working set (fit the code and data in cache) and heavily optimized IPC. The IPC in L4 kernels is "a context switch with benefits": in the best case, the arguments are placed in registers and the context is switched. Under real workloads, microkernels probably will be slower, but not by much.
Re:The Linux realtime preemption endgame is near by mananaysiempre on Thursday November 16, 2023 @10:08PM (#38298971)
IIRC the KeyKOS/EROS/CapROS tradition used capabilities for everything including the scheduler. Of course, pervasive persistence makes those systems somewhat esoteric (barring fresh builds, they never shut down or boot, only go to sleep and wake up in new bodies; compare Smalltalk, etc.).
Re:The Linux realtime preemption endgame is near by vacuity on Thursday November 16, 2023 @10:15PM (#38299014)
Guess I'm too ignorant. I need to read up on these. I did know about the persistence feature. I think it's not terrible but also not great, and systems should be designed for being shut down and apps being closed.
Re:The Linux realtime preemption endgame is near by naasking on Friday November 17, 2023 @10:53AM (#38305245)
> I think it's not terrible but also not great, and systems should be designed for being shut down and apps being closed.

The problem with shutdowns and restarts is the secure bootstrapping problem. The boot process must be within the trusted computing base, so how do you minimize the chance of introducing vulnerabilities? With checkpointing, if you start in a secure state, you're guaranteed to have a secure state after a reboot. This is not the case with other any other form of reboot, particularly ones that are highly configurable and so easy for the user to introduce an insecure configuration.

In any case, many apps are now designed to restore their state on restart, so they are effectively checkpointing themselves, so there's clearly value to checkpointing. In systems with OS-provided checkpointing it's a central shared service and doesn't have to be replicated in every program. That's a significant reduction in overall system code that can go wrong.

Re:The Linux realtime preemption endgame is near by vacuity on Friday November 17, 2023 @11:33AM (#38305842)
It's fallacious to assume that the persistence model of the system can't enter an invalid state and thus cause issues similar to bootstrapping. The threat model also doesn't make sense to me: if an attacker can manipulate the boot process, I feel like they would be able to attack the overall system just fine. Also, there's the bandwidth usage, latency, and whatnot. I think persistence is a strictly less powerful, although certainly convenient, design for an OS.
Re:The Linux realtime preemption endgame is near by naasking on Friday November 17, 2023 @12:08PM (#38306440)
> The threat model also doesn't make sense to me: if an attacker can manipulate the boot process, I feel like they would be able to attack the overall system just fine.

That's not true actually. These capability systems have the principle of least privilege right down to their core. The checkpointing code is in the kernel which only calls out to the disk driver in user space. The checkpointing code itself is basically just "flush these cached pages to their corresponding locations on disk, then update a boot sector pointer to the new checkpoint", and booting a system is "read these pages pointed to by this disk pointer sequentially into memory and resume".

The attack surface in this system is incomparably small compared to the boot process of a typical OS, which run user-defined scripts and scripts written by completely unknown people from software you downloaded from the internet, often with root or other broad sets of privileges.

I really don't think you can appreciate how this system works without digging into it a little. EROS was built from the design of KeyKOS that ran transactional bank systems back in the 80s. KeyKOS pioneered this kind of checkpointing system, so it saw real industry use in secure systems for years. I recommend at least reading an overview:

https://flint.cs.yale.edu/cs428/doc/eros-ieee.pdf

EROS is kind of like what you'd get it if you took Smalltalk and tried to push it into the hardware as an operating system, while removing all sources of ambient authority. It lives on as CapROS:

https://www.capros.org/

Re:The Linux realtime preemption endgame is near by vacuity on Friday November 17, 2023 @01:02PM (#38307369)
I don't deny that bootstrapping in current systems is ridiculous, but I don't see why it can't be improved. It's not like EROS is a typical OS either. In any case, I'll read up on those OSes.
Re:The Linux realtime preemption endgame is near by adastra22 on Friday November 17, 2023 @01:46AM (#38300342)
Amoeba was my favorite, as it was a homogeneous, decentralized operating system. Different CPU architectures spread across different data centers, and it was all homogenized together into a single system image. You had a shell prompt where you typed commands and the OS could decide to spawn your process on your local device, in the server room rack, or in some connected datacenter in Amsterdam, it didn't make a difference. From the perspective of you, your program, or the shell, it's just a giant many-core machine with weird memory and peripheral access latencies that the OS manages.

Oh, and anytime as needed the OS could serialize out your process, pipe it across the network to another machine, and resume. Useful for load balancing, or relocating a program to be near the data it is accessing. Unless your program pays special attention to the clock, it wouldn't notice.

I still think about Amoeba from time to time, and imagine what could have been if we had gone down that route instead.

Re:The Linux realtime preemption endgame is near by vacuity on Friday November 17, 2023 @02:29AM (#38300586)
Wouldn't there be issues following from distributed systems and CAP? Admittedly, I know nothing about Amoeba.

E.g. You spawn a process on another computer and then the connection drops.

Re:The Linux realtime preemption endgame is near by adastra22 on Friday November 17, 2023 @03:11PM (#38309333)
There's no free lunch of course, so you would have circumstances where a network partition at a bad time would result in a clone instead of a copy. I don't know what, if anything, Amoeba did about this.

In practice it might not be an issue. The reason you'd typically do something like move processes across a WAN is because you want it to operate next to data it is making heavy use of. The copy that booted up local to the data would continue operating, while the copy at the point of origin would suddenly see the data source go offline.

Now of course more complex schemes can be devised, like if the data source is replicated and so both copies continue operating. Maybe a metric could be devised for detecting these instances when the partition is healed, and one or both processes are suspended for manual resolution? Or maybe programs just have to be written with the expectation that their capabilities might suddenly become invalid at any time, because the capability sides with the partition that includes the resource? Or maybe go down the route of making the entire system transactional, so that partition healing can occur, and only throw away transaction deltas once receipts are received for all nodes ratcheting state forward?

It'd be an interesting research area for sure.

Re:The Linux realtime preemption endgame is near by Animats on Friday November 17, 2023 @02:28PM (#38308804)
No, that was KeyKOS, which was way ahead of its time.[1] Norm Hardy was brilliant but had a terrible time getting his ideas across.

[1] https://en.wikipedia.org/wiki/KeyKOS

Re:The Linux realtime preemption endgame is near by _kb on Thursday November 16, 2023 @07:03PM (#38297438)
And unfortunately had its funding dumped because it wasn’t shiny AI.
Re:The Linux realtime preemption endgame is near by snvzz on Friday November 17, 2023 @07:26AM (#38302577)
Its old source of funding. And it was much more complex[0] than that.

seL4 is now a healthy non-profit, seL4 foundation[1].

0. https://microkerneldude.org/2022/02/17/a-story-of-betrayal-c...

1. https://microkerneldude.org/2022/03/22/ts-in-2022-were-back/

Re:The Linux realtime preemption endgame is near by Animats on Friday November 17, 2023 @12:54PM (#38307245)
The trouble with L4 is that it's so low-level you have to put another OS on top of it to do anything Which usually means a bloated Linux. QNX offers a basic POSIX interface, implemented mostly as libraries.
Re:The Linux realtime preemption endgame is near by snvzz on Friday November 17, 2023 @02:06PM (#38308383)
Note that L4 and seL4 are very different kernels. They represent the 2nd generation and 3rd generation of microkernels respectively.

With that out of the way, you're right in that the microkernel doesn't present a posix interface.

But, like QNX, there are libraries for that, seL4 foundation itself maintains some.

They have a major ongoing effort on system servers, driver APIs and ways to deploy system scenarios. Some of them were talked about in a recent seL4 conference.

And then there's third party efforts like the amazing Genode[0], which supports dynamic scenarios with the same drivers and userspace binaries across multiple microkernels.

They even have a modern webbrowser, 3d acceleration as well as providing a virtualbox box that runs inside Genode, so the dogfooding developers are be able to run e.g. Linux inside a virtualbox to bridge the gap.

0. https://www.genode.org/

Re:The Linux realtime preemption endgame is near by bregma on Thursday November 16, 2023 @03:53PM (#38295328)
The current (SDP 8) kernel has 15331 lines of code, including comments and Makefiles.
Re:The Linux realtime preemption endgame is near by gigatexal on Thursday November 16, 2023 @03:59PM (#38295438)
QNX is used in vehicle infotainment systems no? Where else?

I'm not bothered by the kernel bloat. There's a lot of dev time being invested in Linux and while the desktop is not as much of a priority as say the server space a performant kernel on handhelds and other such devices and the dev work to get it there will benefit the desktop users like myself.

Re:The Linux realtime preemption endgame is near by lmm on Thursday November 16, 2023 @04:32PM (#38295862)
> QNX is used in vehicle infotainment systems no? Where else?

A bunch of similar embedded systems. And blackberry, if anyone's still using them.

Re:The Linux realtime preemption endgame is near by bkallus on Thursday November 16, 2023 @04:32PM (#38295860)
I went to a conference at GE Research where I spoke to some QNX reps from Blackberry for a while. Seemed like they were hinting that some embedded computers in some of GE'S aerospace and energy stuff relies on QNX.
Re:The Linux realtime preemption endgame is near by tyfon on Thursday November 16, 2023 @05:00PM (#38296187)
It was used in my old toyota avensis from 2012. The infotainment was so slow you could measure performance in seconds pr frame instead of frames pr second :)

In the end, all I could practically use it for was as a bluetooth audio connector.

Re:The Linux realtime preemption endgame is near by notrom on Thursday November 16, 2023 @06:22PM (#38297093)
I've worked with it in industrial automation systems in large scale manufacturing plants where it was pretty rock solid. And I'm aware of it's use in TV production and transmissions systems.
Re:The Linux realtime preemption endgame is near by Cyph0n on Thursday November 16, 2023 @06:42PM (#38297252)
Cisco routers running IOS-XR, until relatively recently.
Re:The Linux realtime preemption endgame is near by SubjectToChange on Thursday November 16, 2023 @08:34PM (#38298137)
Railroads/Positive Train Control, emergency call centers, etc. QNX is used all over the place. If you want an even more impressive Microkernel RTOS, then Green Hills INTEGRITY is a great example. It's the RTOS behind the B-2, F-{16,22,35}, Boeing 787, Airbus A380, Sikorsky S-92, etc.
Re:The Linux realtime preemption endgame is near by yosefk on Friday November 17, 2023 @07:59AM (#38302878)
"Even more impressive" in what way? I haven't used INTEGRITY but used the Green Hills compiler and debugger extensively for years and they're easily the most buggy development tools I've ever had the misfortune to use. To me the "impressive" thing is their ability to lock safety critical software developers into using this garbage.
Re:The Linux realtime preemption endgame is near by dilyevsky on Thursday November 16, 2023 @09:08PM (#38298418)
Routers, airplanes, satellites, nuclear power stations, lots of good stuff
Re:The Linux realtime preemption endgame is near by gigatexal on Thursday November 16, 2023 @04:01PM (#38295464)
> QNX had this right decades ago. The microkernel has upper bounds on everything it does. There are only a few tens of thousands of lines of microkernel code. All the microkernel does is allocate memory, dispatch the CPU, and pass messages between processes. Everything else, including drivers and loggers, is in user space and can be preempted by higher priority threads.

So much like a well structured main method in a C program or other C like language where main just orchestrates the calling of other functions and such. In this case main might initialize different things where the QNX kernel doesn't but the idea or general concept remains.

I'm no kernel dev but this sounds good to me. Keeps things simple.

Re:The Linux realtime preemption endgame is near by vacuity on Thursday November 16, 2023 @04:38PM (#38295926)
Recently, I've been thinking that we need a microkernel design in applications. You have the core and then services that can integrate amongst each other and the core that provide flexibility. Like the "browser as an OS" kind of things but applied more generally.
Re:The Linux realtime preemption endgame is near by galdosdi on Thursday November 16, 2023 @05:53PM (#38296807)
Yes! This reminds me strongly of the core/modules architecture of the apache httpd, as described by the excellent O'Reilly book on it.

The process of serving an HTTP request is broken into a large number of fine grained stages and plugin modules may hook into any or all of these to modify the input and output to each stage.

The same basic idea makes it easy to turn any application concept into a modules-and-core architecture. From the day I read (skimmed) that book a decade or two ago this pattern has been burned into my brain

Re:The Linux realtime preemption endgame is near by blackth0rn on Thursday November 16, 2023 @06:26PM (#38297117)
ECS systems for the gaming world are somewhat like this. There is the core ECS framework and then the systems and entity's integrate with each other
Re:The Linux realtime preemption endgame is near by spookie on Thursday November 16, 2023 @06:38PM (#38297228)
ECS is incredible. Other areas should take notice
Re:The Linux realtime preemption endgame is near by whstl on Thursday November 16, 2023 @07:07PM (#38297473)
Agreed. I find that we're going in this direction in many areas, games just got there much faster.

Pretty much everywhere there is some undercurrent of "use this ultra-small generic interface for everything and life will be easier". With games and ECS, microkernels and IPC-for-everything, with frontend frameworks and components that only communicate between themselves via props and events, with event sourcing and CQRS backends, Actors in Erlang, with microservices only communicating via the network to enforce encapsulation... Perhaps even Haskell's functional-core-imperative-shell could count as that?

I feel like OOP _tried_ to get to this point, with dependency injection and interface segregation, but didn't quite get there due to bad ergonomics, verbosity and because it was still too easy to break the rules. But it was definitely an attempt at improving things.

Re:The Linux realtime preemption endgame is near by gigatexal on Saturday November 18, 2023 @08:31AM (#38319362)
ECS?
Re:The Linux realtime preemption endgame is near by vacuity on Saturday November 18, 2023 @10:25AM (#38320561)
Entity-component-system paradigm. Compared to OOP, ECS is more "data-first". It's like a database of components (attributes such as Position, Velocity, Player) with entities (simple integer identifiers) as keys. Systems are functions that query for components and perform actions on them. See Shipyard, enTT, Bevy, flecs, etc. The design space is still evolving.
Re:The Linux realtime preemption endgame is near by gigatexal on Sunday November 19, 2023 @01:42AM (#38329822)
As a database guy I really can get around this. OOP hurts my head sometimes when the hierarchies get too deep.
Re:The Linux realtime preemption endgame is near by vbezhenar on Friday November 17, 2023 @12:23AM (#38299913)
COM, OSGI, Service architecture, microservice architecture and countless other approaches. This is correct way to build applications, because it gets reinvented over and over again.
Re:The Linux realtime preemption endgame is near by elcritch on Friday November 17, 2023 @03:50AM (#38301080)
That’s pretty much what Erlang/OTP is, and it’s like a whole OS. Though it lacks capabilities.
Re:The Linux realtime preemption endgame is near by js2 on Thursday November 16, 2023 @06:52PM (#38297351)
VxWorks is what's used on Mars and it's a monolithic kernel, so there's more than one way to do it. :-)
Re:The Linux realtime preemption endgame is near by dilyevsky on Thursday November 16, 2023 @09:11PM (#38298445)
I think RT build also had to disable mmu
Re:The Linux realtime preemption endgame is near by signa11 on Friday November 17, 2023 @05:46AM (#38301805)
this feels like tannenbaum-torvalds debate once again.
Re:The Linux realtime preemption endgame is near by creshal on Friday November 17, 2023 @06:08AM (#38301933)
> Millions of lines of kernel, all of which have to be made preemptable.

~90% of those are device drivers, which you'd still need with a microkernel if you want it to run or arbitrary hardware.

Re:The Linux realtime preemption endgame is near by dontlaugh on Friday November 17, 2023 @07:01AM (#38302358)
But crucially, drivers in a microkernel run in user space and are thus pre-emptible by default. Then the driver itself only has to worry about dealing with hardware timing when pre-empted.
Re:The Linux realtime preemption endgame is near by creshal on Friday November 17, 2023 @07:37AM (#38302671)
Sure, but who's going to write the driver in the first place? Linux's "millions of lines of code" are a really underappreciated asset, there's tons of obscure hardware that is no longer supported by any other actively maintained OS.
Re:The Linux realtime preemption endgame is near by dontlaugh on Friday November 17, 2023 @07:53AM (#38302825)
I also don't see how we could transition to a microkernel, indeed.
Re:The Linux realtime preemption endgame is near by naasking on Friday November 17, 2023 @10:55AM (#38305276)
The very first "hypervisors" were actually microkernels that ran Linux as a guest. This was done with Mach on PowerPC/Mac systems, and also the L4 microkernel. That's one way.

The only downside of course, is that you don't get the isolation benefits of the microkernel for anything depending on the Linux kernel process.

Re:The Linux realtime preemption endgame is near by matheusmoreira on Friday November 17, 2023 @08:35AM (#38303307)
And yet it's getting done! It's very impressive work.
Re:The Linux realtime preemption endgame is near by AndyMcConachie on Friday November 17, 2023 @11:48AM (#38306091)
Linus Torvalds and Andrew Tannenbaum called. They want their argument back!