Rust, a modern system programming language focused on performance, safety and concurrency, seems an ideal choice for creating a new operating system, and several such projects already exist. Now there is a new one, Theseus, described by creator Kevin Boos as "an Experiment in Operating System Structure and State Management."
The key thinking behind Theseus is to avoid what Boos and three other contributors from Rice and Yale universities call "state spill".
In a paper presented at the USENIX symposium on operating systems design and implementation last November, the researchers defined this as when "one software component harboring changed states as a result of handling an interaction from another component, such that their future correctness depends on said states."
This is the norm in modern systems, they said, and gave as an example that if an Android system service fails, the "entire userspace framework" crashes, affecting all applications even those not using the failed service.
State spill is a barrier to reliability, they argued, which impacts everything from firmware in tiny pacemakers to networks in data centres. In order to discover "to what extent state spill can be avoided in OS code", the researchers decided to write a new OS from scratch, choosing Rust because it has an ownership model.
Ownership, described by the Rust docs as "Rust's central feature", key to how the language achieves memory safety, enforces three rules:
- Each value in Rust has a variable that's called its owner
- There can only be one owner at a time
- When the owner goes out of scope, the value will be dropped
Avoiding state spill required rethinking OS structure, the researchers said, in particular how the OS is modularised. Theseus OS has many tiny components, called cells, each with clear bounds. Cells are based on Rust crates (project containers).
The bigger innovation, though, is what they call "intralingual OS design" by which they mean using programming language mechanisms to implement the OS. The idea is to "shift semantic errors from runtime failures into compile-time errors."
This means that Theseus is more deeply tied to Rust than other Rust-based operating systems.
State management is handled using principles based on client-server models. Clients own their state and servers use stateless communication "which dictates that everything necessary for a given request to be handled should be included in that request."
This is familiar from REST web models. Theseus therefore avoids things like handles, pointers to resources owned by the operating system, in favour of owning their resources directly.
Resilience in Theseus uses a technique called cell swapping, where new cells replace existing ones and take on their dependencies. An old cell is not actually dropped until it is no longer referred to by any other cell.
Fault recovery involves replacing corrupt cells with new ones. This, the researchers claimed, "allows [Theseus] to tolerate faults in the lowest system layers in the face of multiple failed subsystems."
Similar mechanisms enable live updates. In a test of fault recovery, the researchers injected 800,000 faults and achieved a 69 per cent successful recovery rate.
How is performance?
"We do not claim that Theseus generally outperforms existing OSes like Linux... but our results do not indicate significant performance drawbacks," the researchers said, based on tests like LMBench.
Despite its experimental architecture, there are limitations. Unsafe code is "an unfortunate necessity in a low-level kernel environment," the researchers said, because of the need to interact with hardware. Another limitation is that components must be implemented in safe Rust.
Other "safe or managed" languages could be supported, but unsafe languages would need hardware or software based isolation. The designers are also compromising principles in some areas, such as the file system.
"A fully spill-free FS would break existing POSIX interfaces by granting sole ownership of a file to the client currently accessing it, meaning that the file would appear to be absent until the client releases it."
That sounds inconvenient. The "current tradeoff" is to support legacy file system standards and accept state spill for this case.
Currently Theseus is on GitHub and comprises 38,000 lines of Rust code and 900 lines of assembly. The operating system can be built on Linux, Windows using WSL (Windows Subsystem for Linux), macOS, or in a Docker container. It can be run in the QEMU emulator.
The team loves Visual Studio Code for development, and said it has "excellent cross-platform support for Rust. Other options are available, but we don't recommend them."
Another prominent Rust-based OS is Redox OS, currently at version 0.6. The last major update was in December, and included a complete rewrite of the kernel memory manager, many updated and new components including a greatly improved relibc library (used by most user applications), and a new package format called pkgar.
Why bother with Theseus when we have Redox?
The answer is that the two projects have little in common, other than the use of Rust and that they are new operating systems. Redox supports Unix-like syscalls, and has an architecture "largely inspired by MINIX," according to its docs.
Redox will be more familiar to developers. Note, though, that Redox does aim to be resilient with isolated components, resistance against one failed component crashing other components, and restricted communication between components. Redox, its designers claimed, is "for users that want minimal issues with their computer systems." That sounds like most of us.
Another Rust-based operating systems is Tock, designed for embedded systems. There are others, but most are not very active.
The question raised by Theseus is whether a radically different new operating system can have sufficient advantages to overcome the huge difficulties of establishing it in a world so heavily invested in existing ones like Linux (and Linux-based Android), macOS, and Windows.
Google has a good chance with Fuchsia, perhaps. A Rust-based option is attractive, though, and projects like this one and Redox OS are worth watching. ®