erXos: An Operating System in ErlangAppendix ELineage
Contents
  1. 1Operating Systems from the Ground Up
  2. 2Microkernels and Capabilities
  3. 3Erlang and OTP
  4. 4History and Goals
  5. 5Design Overview of erXos
  6. 6Correct by Construction
  7. 7One Source for Every Fact
  8. 8The Kernel Interface and Fiasco
  9. 9Processes, Runtimes and Two-Level Scheduling
  10. 10Domains: A Wall Around Some Processes
  11. 11Authority and Security
  12. 12Memory and Budgets
  13. 13Native Programs, Pipes and POSIX-lite
  14. 14Files, Namespaces and Service Trees
  15. 15Devices and Drivers
  16. 16Storage and Updates
  17. 17The Network Stack
  18. 18WiFi
  19. 19Bluetooth
  20. 20The Command Shell and the UNIX Surface
  21. 21The Live Machine
  22. 22Displays, Windows and the Web
  23. 23Apps and Packages
  24. 24Startup, Configuration and Shutdown
  25. 25Checking the System
  26. AGlossary
  27. BReading the Design Documents
  28. CBuilding and Booting erXos
  29. DDependencies and Licenses
  30. ELineage
    1. E.1Erlang and its runtimes
    2. E.2UNIX and FreeBSD
    3. E.3Microkernels and capabilities
    4. E.4Plan 9 and Inferno
    5. E.5Live and language-based systems
    6. E.6Devices, storage, networks and radios
    7. E.7Lessons taken as warnings
    8. E.8Citations

Appendix ELineage

Almost every mechanism in erXos was first built somewhere else. What erXos adds is the way the mechanisms meet: an Erlang process as the operating system’s process, across address spaces, with Erlang’s semantics kept. Chapter 4, section 4.3 tells that story for the four sources that shaped erXos most. This appendix is the reference list behind it. It gives each system or paper erXos draws on, the idea taken and the chapter where it appears, then the systems whose failures erXos was designed to avoid.

The evidence is the project’s survey of earlier systems, research-prior-art.md, the other records in design.md, References, and each chapter’s “Where to read next”. Section E.8 gives the citations.

E.1Erlang and its runtimes

SourceWhat erXos took, or the contrast it drawsWhere
Erlang/OTP and Armstrong’s thesis (2003)Isolated processes that share nothing, “let it crash” and supervisors as the whole system’s failure model, and restarting, after Gray’s study of transient faults (1985)Chapter 3, chapter 4
ERTS, read as described in The BEAM Book (Stenman and others)Preemption only at function calls and receives, per-process heaps; the runtime as a parts bin taken apart and recombinedChapter 3, chapter 9
Safe Erlang (Brown and Sahlin 1999)The diagnosis that a pid is “both forgeable and too powerful”; in erXos’s design a pid is a name, and a domain reaches another’s process only through an exportChapter 4, chapter 10, chapter 11
Nerves and GRiSPErlang over a conventional kernel, Linux or RTEMS; erXos moves the walls inside the Erlang system insteadChapter 4
LING and HydrOSErlang with no operating system beneath it, walled by virtual machine or by CPU core; HydrOS’s drivers in ErlangChapter 4

Table E.1. Sources in Erlang (research-prior-art.md, Safe Erlang, Other systems, The Erlang runtime).

E.2UNIX and FreeBSD

Where UNIX systems differ, erXos follows FreeBSD. It keeps FreeBSD’s behavior and redesigns the structure, so most entries here are a behavior kept and an inside replaced.

SourceWhat erXos took, or the contrast it drawsWhere
UNIXFiles, processes, text pipes, a shell and small tools as the surfaceChapter 4, chapter 20
McKusick, Neville-Neil and Watson, The Design and Implementation of the FreeBSD Operating System (2014)The arc and manner of this book; the tty layer that erx_tty followsREADME.md, chapter 20
FreeBSD’s netinetThe TCP/IP stack’s behavior, redesigned as Erlang processes and pure functionsChapter 17
FreeBSD’s signal and error numbersThe numbers musl and liberx give native programsChapter 13
FreeBSD’s syscalls.masterThe precedent for generating system-call tables from one fileChapter 7
FreeBSD’s rc.conf, rc.subr and service(8)How services are configured and started, kept where it fitsChapter 20, chapter 23
FreeBSD’s pkgPackages as archives with a manifest, recorded in a database and installed by scripts that run as root; erXos keeps each app one file, runs nothing at install and has no pkg commandsChapter 23
macOS’s /ApplicationsInstalling by copying a file into a directory, which cp NAME.app /apps/ followsChapter 23
FreeBSD’s loader, init and rcorder(8)The contrast for the boot: erXos boots one archive under one hash instead of a loader reading a file system, and derives the boot order once at build time instead of from REQUIRE lines at every bootChapter 24
FreeBSD’s reboot(8)The name, -p and halt as the same program; the flags for things erXos lacks are usage errorsChapter 24
Capsicum, FreeBSD’s capability modeThe contrast: FreeBSD narrows a process’s authority after the fact, and erXos starts a program with noneChapter 2, chapter 11
FreeBSD’s namei and tmpfsThe path lookup and RAM file system that erXos’s resolver and /tmp followChapter 14
Baumann and others, “A fork() in the road” (2019)The case for starting programs with a spawn call, not forkChapter 13

Table E.2. Sources in UNIX and FreeBSD.

E.3Microkernels and capabilities

SourceWhat erXos took, or the contrast it drawsWhere
L4 (Liedtke 1993, 1995)A kernel of address spaces, threads and fast IPC, with everything else in user modeChapter 2
Fiasco (TU Dresden, from 1998)The kernel itself, behind erXos’s kernel interface, with a few small patchesChapter 4, chapter 8
L4ReA root task that creates every program and hands it its capabilities; its loader ned’s CPU sets, the model for each domain’s designed CPU setChapter 2, chapter 8, chapter 9
Dennis and Van Horn (1966)The capability: a reference that carries rightsChapter 2
Saltzer and Schroeder (1975)Least privilege, economy of mechanism and complete mediationChapter 6, chapter 11
Hardy, “The Confused Deputy” (1988)The problem that facets and minted handles answerChapter 2, chapter 11
KeyKOS and EROS (Shapiro, Smith and Farber 1999)The space bank, which ends everything it paid for when it ends: erXos’s budgetsChapter 2, chapter 12
Zircon, Fuchsia’s kernelHandles with rights that only shrink; no ambient authorityChapter 2, chapter 10
GenodeEach session paid from a quota its client donates; erXos’s memory shares for usersChapter 4
MINIX 3A reincarnation server that restarts a failed driver, the microkernel form of a supervisorChapter 2
QNXA UNIX look over a microkernelChapter 2, chapter 4
seL4The alternative not taken: a kernel proved correct (Klein and others 2009); its device driver framework, sDDF, for splitting a driver from its policyChapter 6, chapter 15

Table E.3. Sources in microkernels and capability systems (research-kernel-bases.md, research-architecture.md for Genode).

E.4Plan 9 and Inferno

Plan 9 shaped how erXos’s names, files and windows work; how they look is erXos’s own.

SourceWhat erXos took, or the contrast it drawsWhere
Plan 9’s namespaces and 9P (Pike and others 1993, 1995)A private table from paths to file servers per domain, and one file protocol, 9P2000.LChapter 14
Plan 9’s file conventionsState is a file to read, control a file to writeChapter 14
rc, Plan 9’s shell (Duff)The command shell’s languageChapter 20
8½ and rio (Pike 1991), and the draw protocolEach window a directory of files; the draw protocol, executed in the client; the overlapping window policyChapter 22
The plumberRoutes from a value on the screen to an action, in find and actChapter 22
factotum (Cox and others 2002)A key holder that signs or answers but never gives up the key: the vault, and the WiFi key holderChapter 11, chapter 18
Inferno (Dorward and others 1997)A virtual machine at the center; erXos adds hardware wallsChapter 4

Table E.4. Sources in Plan 9 and Inferno.

E.5Live and language-based systems

SourceWhat erXos took, or the contrast it drawsWhere
Genera, the Symbolics Lisp machine environment (Walker and others 1987)A live machine, every object examinable and code patched as it runs; output bound to its valueChapter 21, chapter 22
Singularity (Hunt and Larus 2007; Aiken and others 2006)Evidence that protection crossings, not safety checks, dominate the cost of isolation; hence many processes per address spaceChapter 4, chapter 8
Midori (Duffy, blog)Erlang’s supervisors as a whole system’s failure model, found outside ErlangChapter 4
Barrelfish (Baumann and others 2009)Hardware facts as data, and a plan kept apart from the register writes: the checked system manifest and the one ABI fileChapter 6, chapter 7
BOOM (Berkeley)Systems as rules over state and events; why a logic language is allowed where it simplifies, though erXos uses no DatalogChapter 7
Minsky; Bernhardt“Make illegal states unrepresentable”; “functional core, imperative shell”Chapter 6

Table E.5. Sources in live and language-based systems (research-prior-art.md, Genera, Singularity, research-os-ideas.md).

E.6Devices, storage, networks and radios

SourceWhat erXos took, or the contrast it drawsWhere
OASIS, VIRTIO 1.2 (2022)The device rings of QEMU’s devicesChapter 15
F2FS (Lee and others 2015)The read-write file system’s design, implemented in ErlangChapter 16
littlefsThe small file system that the storage domain runs as a NIFChapter 16
Merkle’s hash tree (1987)Each block of a read-only system image checked against one root hashChapter 16
The Raspberry Pi firmware’s trybootUpdates through two slots and a trial bootChapter 16
OpenBSD’s bwfm(4)The WiFi driver’s model, the chip’s supplicant offChapter 18
Fuchsia’s WLAN stackPolicy apart from the state machine, its transitions written onceChapter 18
wpa_supplicantThe states of SAE’s public halfChapter 18
Cheshire and Baker, COBS (1999)The framing of the host link over a serial lineChapter 21

Table E.6. Sources for devices and I/O (design-wifi.md, Lineage holds the full WiFi table).

E.7Lessons taken as warnings

Each failure or refused mechanism below shaped a rule of erXos.

  • Scheduler activations and M:N threading (Anderson and others 1991). Upcalls arrived at any point, and a lock holder preempted by an upcall had to be resumed specially before anything else could run; NetBSD 5.0 and FreeBSD 7.0 moved to one kernel thread per user thread. erXos keeps two levels of scheduling but sends no upcall to a thread that runs Erlang processes (chapter 4, section 4.2, chapter 9).
  • Akaros took a core away at any line, even under a lock. The same rule answers it (chapter 4).
  • Time donation, as in seL4’s passive servers. A client lends its CPU time to the server working for it. erXos’s services run on their own threads, so no domain’s scheduling depends on another’s (chapter 9).
  • SPIN (Bershad and others 1995). A crashed kernel extension could leave the system inconsistent; erXos runs everything but the kernel in user mode (chapter 4).
  • The eBPF verifier. Proving loaded code safe puts a verifier in the trusted base, and its bugs become kernel exploits. erXos runs untrusted code behind hardware walls instead (chapter 11).
  • Speculative execution. One address space keeps no secrets, as the V8 team concluded (McIlroy and others 2019). Domains that do not trust each other are separate address spaces (chapter 4).
  • Genera’s open core. With no protected kernel, users reached for primitives not theirs to touch. erXos adds walls to the live machine (chapter 21).

E.8Citations

The works named above, as the tree records them; research-prior-art.md and the chapters’ “Where to read next” give addresses. A detail no document in the tree confirms carries a note for the book’s checker.

  • M. Aiken, M. Fähndrich, C. Hawblitzel, G. Hunt and J. Larus, “Deconstructing Process Isolation”, MSPC 2006.
  • Thomas Anderson, Brian Bershad, Edward Lazowska and Henry Levy, “Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism”, SOSP 1991; ACM TOCS 10(1), 1992.
  • Joe Armstrong, Making Reliable Distributed Systems in the Presence of Software Errors, PhD thesis, Royal Institute of Technology, Stockholm, 2003.
  • Andrew Baumann and others, “The Multikernel: A New OS Architecture for Scalable Multicore Systems”, SOSP 2009.
  • Andrew Baumann, Jonathan Appavoo, Orran Krieger and Timothy Roscoe, “A fork() in the road”, HotOS 2019.
  • Brian Bershad and others, “Extensibility, Safety and Performance in the SPIN Operating System”, SOSP 1995.
  • Lawrie Brown and Dan Sahlin, “Extending Erlang for Safe Mobile Code Execution”, ICICS 1999, LNCS 1726.
  • Stuart Cheshire and Mary Baker, “Consistent Overhead Byte Stuffing”, IEEE/ACM Transactions on Networking 7(2):159-172, 1999.
  • Russ Cox, Eric Grosse, Rob Pike, Dave Presotto and Sean Quinlan, “Security in Plan 9”, USENIX Security 2002.
  • Jack Dennis and Earl Van Horn, “Programming Semantics for Multiprogrammed Computations”, Communications of the ACM 9(3), 1966.
  • Sean Dorward and others, “The Inferno Operating System”, Bell Labs Technical Journal 2(1), 1997.
  • Tom Duff, “Rc - The Plan 9 Shell”.
  • J. Duffy, the Midori blog series, 2015 to 2016 (a secondary source).
  • Kevin Elphinstone and Gernot Heiser, “From L3 to seL4: What Have We Learnt in 20 Years of L4 Microkernels?”, SOSP 2013.
  • Jim Gray, “Why Do Computers Stop and What Can Be Done About It?”, Tandem Computers Technical Report 85.7, 1985.
  • Norm Hardy, “The Confused Deputy (or why capabilities might have been invented)”, ACM SIGOPS Operating Systems Review 22(4), 1988.
  • Galen Hunt and James Larus, “Singularity: Rethinking the Software Stack”, ACM SIGOPS Operating Systems Review 41(2), 2007.
  • Gerwin Klein and others, “seL4: Formal Verification of an OS Kernel”, SOSP 2009.
  • Changman Lee, Dongho Sim, Joo-Young Hwang and Sangyeun Cho, “F2FS: A New File System for Flash Storage”, USENIX FAST 2015.
  • Jochen Liedtke, “On µ-Kernel Construction”, SOSP 1995, which cites his 1993 paper on L3.
  • R. McIlroy, J. Sevcik, T. Tebbi, B. L. Titzer and T. Verwaest, “Spectre is here to stay”, arXiv:1902.05178, 2019.
  • Marshall Kirk McKusick, George Neville-Neil and Robert Watson, The Design and Implementation of the FreeBSD Operating System, 2nd edition, Addison-Wesley, 2014.
  • Ralph Merkle, “A Digital Signature Based on a Conventional Encryption Function”, CRYPTO ’87, pp. 369-378.
  • OASIS, Virtual I/O Device (VIRTIO) Version 1.2, 2022.
  • Rob Pike, “8½, the Plan 9 Window System”, Proceedings of the Summer 1991 USENIX Conference.
  • Rob Pike, Dave Presotto, Sean Dorward, Bob Flandrena, Ken Thompson, Howard Trickey and Phil Winterbottom, “Plan 9 from Bell Labs”, Computing Systems, 1995.
  • Rob Pike, Dave Presotto, Ken Thompson, Howard Trickey and Phil Winterbottom, “The Use of Name Spaces in Plan 9”, Operating Systems Review 27(2), 1993.
  • Jerome Saltzer and Michael Schroeder, “The Protection of Information in Computer Systems”, Proceedings of the IEEE, 1975.
  • Jonathan Shapiro, Jonathan Smith and David Farber, “EROS: a fast capability system”, SOSP 1999.
  • E. Stenman and others, The BEAM Book.
  • J. H. Walker, D. A. Moon, D. L. Weinreb and M. McMahon, “The Symbolics Genera Programming Environment”, IEEE Software 4(6), 1987.