TL;DR
This paper presents "Aquarium," a novel system that uses program synthesis to automatically generate machine-dependent operating system (OS) code. By leveraging domain-specific languages for OS functionality and machine architectures, Aquarium significantly reduces the effort required to port OSes to new hardware, a growing challenge in the post-Moore's Law era.
What Problem Does This Paper Address?
The rapid diversification of hardware architectures, coupled with the slowing of Moore's Law, has made porting operating systems (OS) to new machines an increasingly critical and expensive task. Traditionally, this involves significant manual effort by experienced kernel developers to reimplement machine-dependent code, which is time-consuming and prone to errors. The authors aim to automate this process by using program synthesis to generate this low-level assembly code from high-level specifications.
Methods
The core of the Aquarium system lies in its two domain-specific languages:
- Alewife: A language for writing machine-independent specifications of machine-dependent OS functionality. It abstracts away hardware details, allowing OS developers to focus on the intended behavior.
- Cassiopea: A language for describing instruction set architecture (ISA) semantics. This allows computer architects to formally define how a machine operates at the assembly level.
The workflow involves:
- An OS developer writes an Alewife specification for a piece of OS functionality.
- A computer architect provides a Cassiopea description of the target architecture.
- An "Alewife compiler" uses these inputs, along with "lowering files" (which map Alewife abstractions to machine-specific details), to generate a machine-dependent specification.
- The Cassiopea synthesis engine then uses this machine-dependent specification and the Cassiopea machine description to synthesize assembly code. This process includes verification to ensure correctness.
The system also incorporates several optimizations to improve the scalability of assembly synthesis, including read/write constraints, state gating, dependency constraints, and rule-based decomposition.
Datasets
The authors evaluated their system using:
- Two pre-existing operating systems: Barrelfish and OS/161.
- Four real hardware architectures: 32-bit MIPS, 32-bit ARM, 32-bit RISC-V, and x86_64.
They synthesized 140 OS components in total from these sources.
Key Insights and Ideas
- Decoupling Expertise: The system effectively separates the concerns of OS developers (specifying functionality) and computer architects (describing hardware), enabling them to work with specialized languages.
- Abstraction is Key: Alewife's ability to abstract machine-dependent details is crucial for writing reusable specifications, making the porting effort proportional to the number of OSes and architectures (N+M) rather than their product (N*M).
- Synthesis for Assembly is Hard, But Feasible: The paper demonstrates that program synthesis, while challenging for low-level assembly code due to large search spaces, is indeed feasible for generating correct OS components.
- Optimizations are Critical: The significant speedups achieved by optimizations highlight their necessity for making synthesis practical for complex code.
- Formal Specifications as a Bridge: The use of formal languages like Alewife and Cassiopea provides a precise and verifiable bridge between high-level OS logic and low-level hardware implementation.
Key Results
- Successful Synthesis: The system successfully synthesized 140 OS components from two OSes across four architectures.
- Efficiency Gains: The optimizations improved synthesis performance by an average of 21x, with one case showing a 1380x speedup.
- Reduced Porting Effort: The authors estimate that the incremental cost of a new port is significantly reduced, with a ratio of manual lowering files to synthesized code lines of 0.175.
- Verification: The synthesis engine also verifies hand-written assembly code, demonstrating its utility for validation.
- Scalability: While not fully solved, the optimizations significantly improve scalability, with no timeouts observed within a half-hour limit.
Limitations and Future Work
- Scalability: While improved, synthesis still faces scalability challenges for very long assembly code sequences.
- Machine-Specific Code: Alewife struggles with highly machine-specific code that doesn't map well to machine-independent abstractions.
- Concurrency and Time: The current system does not model concurrency or real-time aspects, limiting its applicability to hard real-time OSes.
- Security: The system does not address security vulnerabilities arising from microarchitectural details (e.g., Spectre, Meltdown).
- Future Work: The authors suggest exploring ways to reuse existing implementations, improve the automation of lowering files, develop better declarative description languages, and extend the system to handle concurrency and time-sensitive code. They also propose integrating security-related constraints into the synthesis process.
Summary updated