Chapter 16Storage and Updates
Background needed. Chapter 1 (block devices, file systems, journals), chapter 10 (domains and how one ends), chapter 11 (facets and file grants), and the outlines of chapters 14 and 15 (file servers and drivers).
A Raspberry Pi in a kiosk loses power whenever someone trips over the cable or the building’s power fails. A cut may land in the middle of an update copying a new system onto the card. The machine must come back every time, with every file it promised to keep and a system that boots, from an SD card that promises little about power cuts and whose every byte may have been changed by someone holding it.
A system can keep its file systems consistent across a crash with journals or copy-on-write, replace system files in place, and keep the old system as a snapshot to boot if the new one fails. If its file systems run in the kernel, a bug in a file system’s parser is a kernel bug, and a crafted disk image is an attack on the kernel.
erXos runs storage as services in Erlang domains of their own. The system itself is a read-only image whose every block is checked against a hash before anything parses it; the files that change live on a separate data partition, behind a file system in its own domain; and an update writes a complete second copy of the system and boots it once on trial, so the copy that runs is never written. A bug in a file system ends a domain, never the machine.
16.1Storage as a service
A bug in the code that reads a disk ends one domain in erXos, which restarts while the rest of the machine runs on. Every part of storage, from the driver to the file system, runs in an Erlang domain, behind facets like any other service (design-storage.md, Overview).
16.1.1The medium and its partitions
The medium has the same layout on every machine, and one file,
abi/medium.txt, says where every partition lies. The packer, the QEMU
harness and the driver all take their numbers from it (chapter 7).
Figure 16.1 shows the layout.
A slot is a pair of partitions: a boot partition, the FAT32 volume
the firmware reads, holding the kernel and the boot image, and a system
partition, holding the system’s read-only files. There are two slots, A
and B. The record partition, first on the medium, is a small FAT16
volume labelled ERXOS that holds the boot-selection record (section
16.6) and the files a user adds before the first boot, such as root’s
authorized_keys. The vault’s partition holds the sealed key files of
the vault (chapter 11, section
11.11.2), and the data partition, the
last, holds /data. Every boundary falls on a 1 MiB line, the erase
unit the layout assumes. The layout is built: the packer writes it to
a card image, and the QEMU disk image has it too.
16.1.2Partition windows
A file system in erXos never holds the disk. It holds a partition
window: an Erlang process of the block driver that serves one
partition’s sectors, numbered from zero, and nothing beyond them.
(Chapter 8’s “window”, the root service’s view of RAM, is a different
thing.) The window checks every request against its range, refuses a
write if it is read-only, and passes what is left to the driver. A file
system that asks for a sector past its partition’s end gets erange.
The system manifest declares which domain may hold each window, and a build check proves the declaration safe: it refuses, for example, a window on a slot held by anyone but the system domain. On QEMU the development manifest declares the data partition’s:
window data
holder @domain.storage
device "/virtio_mmio@a003e00"
role data
partition 0
rights read,write
image none
The block driver does not read these rows. It
is a few processes in the storage domain: a device process that talks
to the controller through the device NIF (chapter 15), a partition
process, and the windows. The partition process reads the partition
table, admits it only if it matches abi/medium.txt, and starts a
window for the record partition, each boot partition, the vault’s
partition and the data partition. From the boot value (section
16.6.2) it adds read-only windows on the booted slot’s system
partition and on the whole record partition, for root’s login keys.
It hands windows only to processes of its own domain. This is built.
16.1.3What a failure ends
The storage domain’s supervisors restart nothing. erx_blk_sup and
erx_storage_sup give every child the permanent restart type and a
restart intensity of zero (chapter 3, section
3.3.4), so the end of any child ends
the supervisor, the application, and with it the whole storage domain.
The domain service then restarts the domain, at most five times in
600 seconds, as the manifest’s row for it says.
Erlang’s habit, the one chapter 3’s supervisors teach, is to restart
only the process that failed. Here that habit would be wrong, because
of the disk’s write cache. A restarted
driver resets the controller, and nothing promises that a reset keeps
what the device’s cache held. A file system that carried on over the
new driver could believe a write was safe that the reset threw away.
So each window binds itself to the first device process it reaches and
answers eio to everything once that process is gone, even if a new
one runs. The file system breaks at its next request, the domain ends,
and the restarted domain mounts the volume afresh from what the medium
holds.
Follow that event when the block driver is killed:
- Files are written to
/data, some of them synced, and a transfer is running. - The block driver in the storage domain is killed while the transfer runs.
- littlefs’s next block request gets
eiofrom the window; the volume is broken, and littlefs, its supervisors and the storage domain end. - Meanwhile
/dataanswerseioin root’s session, and a file opened before the restart must be opened again. - The domain service restarts the domain. The driver resets the device, and the domain reports ready only once littlefs has mounted the volume.
/datareads again: every synced file is present, each kept file cut at a sync.
Root’s session does not fail; it sees a pause in /data.
16.2Read-only system images
The files of the running system are never written by the system that runs them. Each slot’s system partition is a read-only file system image, built once on the developer’s machine, followed by a hash tree that lets any reader prove each block is the one the build wrote.
16.2.1EROFS and its tree
The system partition holds an EROFS image. EROFS, the Enhanced Read-Only File System, is a Linux file system for read-only images: nothing on it changes, so it needs no free-space map and no journal, and a reader has little to get wrong. The tree after it is dm-verity’s format, version 1, with SHA-256 and 4 KiB blocks, so each tree block holds 128 hashes. The image’s manifest, inside the slot’s boot image, records the root hash, the tree’s offset and its salt. The firmware loads the boot image from the boot partition, so the root hash does not pass through the partition it checks.
The packer writes the EROFS image with the fsimg tool, computes the
tree itself, and records the tree in the manifest’s system_image
row.
16.2.2Every block checked before it is parsed
The EROFS reader, erx_erofs, is Erlang, preloaded in every runtime
beside prim_file, so every domain can read an EROFS image without
loading anything first. It never reads the medium itself. Every block
comes through erx_verity, the hash-checking reader, and erx_verity
hands back a block only once it matches the tree (design-storage.md,
Reading EROFS images).
Figure 16.2 traces one read.
The check runs in the calling process, in Erlang, with the runtime’s SHA-256 built-in, and asks for the tree blocks it needs on every read. The parser still checks every bound itself, and a fuzz target feeds it images no tree vouches for.
Flip one byte of a directory block in the system partition. Its hash
no longer matches the tree, so the read answers eio; the reader
fails that one operation and logs the image and block, and the process
that asked carries on. Change files and rebuild the tree to match, and
every read still answers eio, because the root hash comes from the
boot image.
16.2.3The system tree, and every reader checks for itself
The storage domain serves the apps/ directory of the booted slot’s
system partition as the system tree, read-only, through
erx_storage_system (design-storage.md, The system
tree). The build places there
the packages that come with the system, such as the kiosk app on the
Raspberry Pi’s card; packages a user installs lie in /data (section
16.3.3). A package is an app’s
one .app file: a signed header, an EROFS image of the app’s files and
that image’s own hash tree (chapter
23). A domain that runs an app
reads the package through the tree and checks every block against the
package’s own tree, a second time, in its own memory. So a storage
domain can refuse to hand over a file, but it cannot change what a
reader accepts. The system domain and the app template each hold a
read-only file grant of the tree, a process of the storage domain
that serves the tree to that one holder (chapter 11, section
11.7.1); the build
derives both from the manifest. This is built.
Nothing at boot needs the tree: every domain’s code lies in the boot image (chapter 10, section 10.8.2), so a broken system partition costs packages, never the boot.
16.3littlefs in the storage domain
/data is served by littlefs, a small file system from the embedded
world, designed to survive random power failures. It gives
copy-on-write guarantees, keeps its RAM use bounded as the file system
grows, and spreads writes over the blocks it rewrites (dynamic wear
levelling). The storage domain runs it as a NIF (chapter 3), C code
inside the domain’s runtime
(littlefs in the storage
domain).
16.3.1The owner, the worker and one block request
A NIF that waits for the disk cannot run on a normal scheduler, so
littlefs runs on a dirty I/O scheduler, one of ERTS’s threads for long
C calls. But littlefs’s block reads and writes must reach the window,
an Erlang process, and a process stuck in a dirty NIF cannot receive
messages. Two processes share the work, in erx_lfs:
- the owner takes every client request, one at a time, and never blocks;
- the worker alone calls littlefs, one operation at a time.
When littlefs needs a block, its C callback posts {erx_lfs_block, Op, Sector, Count, Req} to the owner and waits. The owner sends the request
to the window and, on the answer, calls erx_littlefs:complete/2, a
short normal NIF that wakes the callback. An operation waits only for
the owner, which waits for nothing, so no cycle of waits can form.
16.3.2What reaches it, and what its failure ends
Two kinds of untrusted input reach littlefs. The partition’s bytes reach it through littlefs’s own bounds checks and checksums, and a fuzz target feeds it crafted images under the NIF’s own configuration. A client’s paths, sizes and offsets reach it through the NIF’s argument decoding, which bounds each before littlefs sees it. A mount that fails never formats the partition.
Any block failure breaks the volume and, as section 16.1.3 traced, ends the storage domain; a littlefs assertion aborts the runtime with the same result. A partition that fails at every mount leaves the domain down once its five restarts are spent. Durability is plain: a file synced before a cut is there after it, and a write not yet synced may be lost.
Running C as a NIF has a cost. A memory error in littlefs that crashes the runtime ends the domain, but one a crafted partition could steer reaches everything the runtime holds: every file of the volume and the block driver itself. This is a limitation of the system. The design places littlefs in a sub-space port of the storage domain (chapter 13, section 13.1), holding only its channel and a data area, so that a fault ends only the port. That placement is designed and not built.
16.3.3Who reaches /data
The volume is the files service data, and its packages/ directory is
a second service, packages, where installed apps lie (chapter
23). For each grantee the
storage domain starts a file grant of the tree, which admits only that
domain’s requests, through the facet the manifest declares (chapter 11,
section 11.6). A
packages file grant reaches nothing outside packages/. The system
domain and root’s session each hold a data file grant over all of
/data, read and write.
Each user’s home is a third service, home, over the volume’s root/
and home/ directories (design-files.md, Building, binding and
mounting). Its file grant is rooted at
the grantee’s own home, /root for root and /home/NAME for anyone
else, and the grant makes the directory when the volume lacks it. The
build gives every user’s session template a home facet, so a user
reaches their own home and nothing else of /data. All three services
are built.
The storage domain also serves login_keys, a read-only tree of one
file, root, holding the keys of the authorized_keys file a user
put on the record partition. It reads the card only when the file is
first asked for, with the FAT reader of section 16.5.1. At boot, while
/root/.ssh/authorized_keys does not exist, root’s session reads
login_keys and writes the keys there; from then on SSH reads only
that copy, which root edits like any file (design-ssh.md, Root’s
login keys on the medium).
This is built.
16.4erXos’s F2FS
The design gives the data and vault partitions F2FS, the Flash-Friendly File System Samsung wrote for Linux (Lee and others, 2015), implemented afresh in Erlang (design-f2fs.md). The vault’s partition is a second volume because the vault’s sealed keys are kept apart from everyone’s files: in the design a storage domain of its own serves it, the vault is its only client, and so no user’s request reaches it (design-storage.md, Data model). It writes the standard on-disk format, so other systems can mount and check what erXos writes, and erXos can mount what they write. erXos’s F2FS as a mounted file system is designed and not built. Two pure parts are built and tested on the host: the codec, which reads a volume’s on-disk structures, and the mount core, which picks the superblock copy and checkpoint and decides the mount mode. The codec has a fuzz target.
16.4.1The durable view is never overwritten
F2FS commits its state in checkpoints: a checkpoint names the
tables that say which blocks are in use. Between two checkpoints, an
fsync of one file appends a roll-forward record to a chain that
the next mount replays. What a mount rebuilds after a cut, the last
checkpoint and its chain, the design calls the durable view, and
its one rule is that no write ever lands on a block the durable view
references
(design-f2fs.md, The construction).
The allocator holds this rule by itself. A block that stops being used stays “touched” until the next checkpoint commits, and the allocator hands out only blocks that are neither in use nor touched. Four rules about the order of writes and flushes complete it. With these, stale chains, torn records and blocks freed too early cannot arise from erXos’s writes, and need no code of their own.
16.4.2One process owns a volume
The volume’s whole state is one Erlang value, held by one process. Every request is one step of a pure function:
step(State, Request) -> {State1, Reply, Plan}
A plan is a list of phases, each a set of block writes followed by a
flush, or a set of reads (design-f2fs.md, One process owns a
volume). The volume
process carries the plan out against the window. A step that needs a
block it does not hold answers {need, Addresses}; the process reads
them and runs the step again from the start. So the core never waits,
and a host test can call any step with exactly the blocks it needs:
chapter 6’s pattern of a pure decision that returns a plan.
16.4.3Crash states as the oracle
The F2FS design lists every state a power cut can leave, row by row, and says what a mount of the image must show for each (design-f2fs.md, The crash states as the oracle). A cut during a checkpoint’s last block, for example, must leave either the old checkpoint with its chain or the new one, whole, and never a mixture. The table says what correct means before any code is written.
The power-cut harness makes those states. It runs the core over a test window that records every write, and after each step of a workload makes every state a cut could leave: each write since the last answered flush kept, lost or torn at a sector boundary, every combination up to ten writes and samples beyond. Each state is mounted and checked: every file holds bytes some write put there, or zeros, and a second mount gives the same tree. Each property has a seeded fault the harness must catch, such as a record’s first flush dropped (design-f2fs.md, The power-cut harness). The harness is designed and not built.
16.5Removable media and the SD controller
16.5.1FAT
FAT is the file system every camera and every other computer can
read, which is why the record partition is FAT16: a user writes
authorized_keys to the ERXOS volume from a laptop before the first
boot. The storage domain reads it with erx_fat_read, a pure core
that finds one file in the root directory by its long name. It admits the boot
sector only if it lays the volume out as abi/medium.txt says, reads
exactly the clusters the file’s size needs, and refuses a chain that
loops or leaves the data area, so whatever the card holds, the read is
bounded. It holds no device: it reads sectors through a function it is
handed. This reader and its fuzz target are built.
The design adds the FAT server, erx_fat, which serves a whole FAT
partition as files, in a storage domain of its own that holds only that
partition’s window (design-storage.md, Removable media:
FAT). It reads FAT12, FAT16
and FAT32 with long names, writes FAT16 and FAT32 and mounts FAT12
read-only, matches names without regard to case as Windows does, and
reports files as mode 0644, since FAT has no owners. A USB stick
reaches it the same way: the USB domain runs a block service for each
medium it finds, and the FAT server holds a drive grant, a right to one partition of
one drive instead of a window. It mounts on access: the first time a
client walks its tree it asks for the window and mounts what it finds;
while the drive is empty its root is an empty read-only directory, and
when the stick is pulled the window ends and the server unmounts
(design-usb.md, Mass storage reaches the file
servers). The
FAT server and USB mass storage are designed and not built.
16.5.2The SD host controller
On the Raspberry Pi 4, the card sits behind an SD host controller with
the standard register set, and erx_blk_sd drives it in Erlang
(design-storage.md, The SD host
controller). It moves data
by programmed I/O through the controller’s data port, at default speed
and 3.3 V. erx_blk_write builds every read, write and status command,
and one table lists the identification commands, so one table and one
module decide what reaches the card. The driver and its fuzz target
are built; on a 4 GB board /data
survives a power cycle. Moving data by DMA through the controller’s
descriptor tables is designed and not built.
16.6Updates through two slots
An update that overwrites the running system can be cut halfway and leave nothing that boots, so erXos never writes the slot it runs from. It writes the other slot, the spare, boots it once as a trial, and makes it the committed slot only if the trial is healthy. The record that chooses the slot is built; the rest of the update path is designed and not built.
16.6.1The boot-selection record
The whole state of an update is one 512-byte sector: the
boot-selection record, the file autoboot.txt of the record
partition. The Raspberry Pi’s firmware reads it to choose a slot, and
every platform uses the same bytes. While slot A is committed it reads:
[all]
tryboot_a_b=1
boot_partition=2
[tryboot]
boot_partition=3
Partition 2 is boot A and partition 3 boot B. When the system asks for a
trial, it sets the firmware’s one-shot tryboot flag and resets; the
firmware boots partition 3 under the [tryboot] section, and clears the
flag, so the boot after that returns to partition 2 unless something
rewrote the record. While B is committed the two numbers swap.
The record has exactly two encodings of the same length, so a commit rewrites one sector and never the file’s directory entry (design-platforms.md, Slots and the boot-selection record). A sector that is neither allows no write; the record sits alone in its erase unit. The packer writes it, committing slot A, and the QEMU harness plays the firmware: it reads the record, parses the slot it names, and boots it; its parser of the record has a fuzz target. These are built.
Write C for the committed slot, the one the record names, and S for
the spare. The boot value, introduced in section 16.6.2, is
normal(X) or trial(X) for the slot X the firmware booted. Figure
16.3 shows the states the record and the boot together allow.
16.6.2The slot writer decides from facts it reads
In the design, one small domain, the slot writer, holds the only writable windows on the slots and the record (design-storage.md, System updates). Before every write it reads two facts for itself: the record, from the medium, and the boot value, which slot the firmware booted and whether as a trial. One pure function over the two decides what it allows:
| Boot value and record | The slot writer allows | The update service |
|---|---|---|
normal(C), record names C | writes to the spare’s two partitions | writes the system image, the boot image, then the spare’s manifest last; checks the spare whole; asks for a trial |
trial(S), record names C | one commit, rewriting the record to name S | once the trial is healthy, asks for the commit, then a reset |
| anything else | nothing | nothing |
No row lets a normal boot rewrite the record or any boot write its own slot. A firmware that falls back to the spare and boots it normally while the record names C matches no row, and nothing is written.
Nothing records an update’s progress. Whether the spare is complete is checked, at each boot and after each write, against the update manifest the update writes last. A spare cut short in either partition has no manifest that matches it, so it is never tried, and the next install writes it again. The facts on the medium are the only state.
An update reaches the update service, in the system domain, from the developer’s host over the host link or from the network, through the service’s install facet; the service reports what it is doing and whether the spare passes its check (design-storage.md, System updates). The design does not say more about where an update is published or what command a user types to start one.
The slot writer, the update service and the commit are designed and not built. The boot value is built: the domain library passes it to the storage domain when it starts the domain, and the block driver uses it to start a window on the booted slot’s system partition alone.
16.6.3A trial writes nothing but the record
A failed trial must leave nothing to undo. So, in the design, on a trial
boot the block driver’s one write path, erx_blk_write, refuses every
write except to the record and the reset count, and every file system
mounts read-only. erx_blk_write is the only module that builds a
write request for the device: a build check refuses any other module
that posts one, and this is built. With one write path, the rule holds whatever the storage
services and the system domain do. The trial rule itself is designed
and not built: erx_blk_write does not apply it.
16.6.4Hangs, faults and the reset count
A trial must end in a boot of the committed slot whatever goes wrong. Every end of the machine nobody ordered, a fault of the system domain, a missed watchdog pet or a failed boot, is a reset (design-fiasco.md, The end path). After a trial the firmware’s flag is spent, so that reset boots the committed slot. The root service’s watchdog thread resets the machine when the system domain’s runtime stops petting it, and on the Raspberry Pi 4 it also arms the hardware watchdog with a 4 s timeout, so a hang of the kernel or of the root service resets the board (design-fiasco.md, The watchdog). Both watchdogs are built. A hang before that thread starts, in the firmware’s own stage or in the kernel’s boot, is not covered and needs a power cycle. The call that asks the firmware for a trial boot is designed and not built: the kernel interface refuses it, so no trial is ever asked for.
The design adds a reset count in a sector of its own beside the record: the number of boots in a row that ended unordered. It rises early in every boot and is cleared at an ordered end or a successful login. A count past three makes the system boot its rescue configuration, the console and a login with no network and no user domain. The reset count is designed and not built.
16.7What fails, and what it reaches
| Failure | What ends | What the user sees |
|---|---|---|
| A bug or assertion in littlefs | the storage domain, then restarted | /data answers eio for a moment; open files must be reopened |
| A block driver crash | the storage domain, then restarted | the same; files synced before it are kept |
| A crafted data partition | the storage domain, at every restart | /data stays unavailable; the partition is never formatted |
| A changed block of a system partition | the one read | eio on that file; the machine boots, since nothing at boot reads the partition |
In the design, a trial that faults or hangs ends only the trial boot, and the committed system boots again.
None of this covers the card itself. Every rule here assumes a medium that writes a sector whole and honours a flush, and an SD card promises neither.
16.8Design choices
Erlang for file systems and the driver. A file system in Erlang cannot write outside its own heap, and its crash is a process exit that a supervisor sees. The per-byte work, SHA-256 and checksums, stays in C built-ins. The cost is speed. littlefs, in C, is the exception, and its memory errors are the limitation section 16.3.2 states.
Restart the domain, not the driver. Restarting the driver alone would let a file system trust writes a device reset discarded. Ending the domain cannot misreport durability, and the domain service already does it.
Checks where the data is used. Trusting the storage domain to check hashes for everyone would save a second hash of each package block; checking in every reader makes a storage domain that can withhold a file but never forge one.
Two slots, not an update in place. An update in place replaces files in a running system; a cut halfway leaves a mixture. Two slots double the space the system takes on the card, in return for a running slot that is never written and a fallback that needs no repair.
No recorded progress. A note saying “spare complete” would have to be right after every cut. Checking the spare against a manifest written last makes the note unnecessary.
Summary
Storage in erXos is Erlang services in their own domains. A file
system reaches the medium only through partition windows, each
serving one partition. When the driver or littlefs fails, the storage domain
ends and restarts, and every file synced before the failure is kept. The
system’s files sit on a read-only EROFS image whose every block is
checked against a hash tree before it is parsed, with the root hash
taken from the boot image. littlefs holds /data as a NIF in the
storage domain, and its memory errors reach that domain’s runtime.
F2FS in Erlang, with a pure core and crash states as its oracle, is
the designed file system for /data; its codec and mount core are
built. Updates write the spare slot, try it once and commit only from
a healthy trial, with the boot-selection record as the only state; the
record’s layout is built, and the trial and commit are designed.
Where to read next
- design-storage.md: the medium, the block
driver, the EROFS reader, the
systemtree, FAT, the SD controller and updates, with every invariant and its test. - littlefs in the storage domain: the owner and worker, the failure path and the tests.
- design-f2fs.md: erXos’s F2FS, its construction, crash states and power-cut harness.
- design-platforms.md, Slots and the boot-selection record: the record on each platform, and trial requests.
- design-fiasco.md, The end path: how every end of the machine becomes a reset.
- Changman Lee, Dongho Sim, Joo-Young Hwang and Sangyeun Cho, “F2FS: A New File System for Flash Storage”, USENIX FAST, 2015: the design of F2FS.
- littlefs project, README, https://github.com/littlefs-project/littlefs: littlefs’s goals.
- Raspberry Pi Ltd, “config.txt” documentation, sections on
autoboot.txtandtryboot, https://www.raspberrypi.com/documentation/computers/config_txt.html: the firmware’s A/B boot. - Ralph Merkle, “A Digital Signature Based on a Conventional Encryption Function”, in Advances in Cryptology - CRYPTO ’87, Lecture Notes in Computer Science 293, Springer, 1988, pp. 369-378: the hash tree.