Files on the disk
The disk holds a tree of files (sysk 029). One task, fsd, keeps it, and serves it in the same protocol as the kernel's tree (Files), over a pair of streams. A change is never made in place: it goes to free sectors, and one write of a root record makes it the disk's. Cut the power at any write, and the disk holds the tree as it was before the change, or after it.
Where it sits
In the default system the shell is the server's one client. / in the shell's namespace is the disk's tree, and /sys the kernel's, as before. The server is an ordinary task: it holds four stream ends, two to the shell and two to the disk driver (Storage), and nothing else. It cannot touch the device, and it knows the disk only as numbered 512-byte sectors.
shell ──fs-ask (576 bytes)──▶ fsd ──disk-ask (528)──▶ disk-driver ──▶ virtio disk
◀──fs-reply────────── ◀──disk-answer──────
Both pairs are a client and its server, a request then its reply, which the deadlock check reads in order (pairs).
The disk after five changes
This is a real disk: tests/fsd on a fresh image, read back sector by sector. The client made /a, then the directory /d, then /d/b, rewrote half of /d/b, and removed /a. Two roots are on it. Pick one to see what it reaches, and pick a sector to see what it holds.
The two trees share every sector neither change touched: the table's last seven sectors, and all of /d/b. Root A still reaches /a, whose sectors are free as far as root B is concerned; they stay as they are until something takes them. Nothing on the disk says which sectors are free: mounting works it out (below).
Two records
A root is one sector. It names the eight sectors of the node table and holds a CRC-32C of each, and its own at the end. The table holds 64 nodes of 64 bytes; a node's kind is its qid type, so a directory is 1 and a file 2, and 0 is a free node. A node names its parent, so a directory's children are the nodes that name it: a directory has no blocks of its own.
A name is 1 to 32 bytes, with no / and no zero byte, and never . or ... Every byte the format does not use must be zero, so that a later version can use it.
A file's map
A file's bytes are 512-byte blocks, wherever there was room. Its node names its map: at depth 1, one index sector of 128 sector numbers, enough for 64 KiB; at depth 2, an index of index sectors, enough for 8 MiB. A 0 in an index is a hole, which reads as zeros, so a file written only at its end takes no room before it. A file grows deeper when it must, and never shallower.
A change, made whole
The fourth change writes 488 bytes over /d/b from offset 512: its second block. Three bitmaps keep the transaction straight. Durable is every sector the root in use reaches; pending, every sector this change has taken; release, every durable sector it replaces. A durable sector is never written, so until the root is, the disk still holds the tree as it was. Step through it, with the real sectors:
A file open for writing is a session: its node's next version, the top of its map and one index sector live in the server's memory until clunk commits them. There is one session at a time, and while it lasts the tree changes no other way. Every commit is the same four steps: the table sectors that changed, to fresh sectors; FLUSH; the root, with seq + 1, into the older slot; FLUSH. Only then does the client hear ok. If any of it fails, the server mounts the disk again, as the durable root left it.
Copy-on-write is a contract. disk-write requires (writable fs s): the sector is the root slot not in use, or one the durable bitmap does not hold. sysp proves every write in svc/fsd.sysp keeps it, formatting included. take, the one place sectors come from, ensures what it hands out is in neither bitmap, whatever its search does: allocation checked by its result, not by its method. That mounting marks every sector the durable root reaches is checked when the server runs, and tested below; it is not proven.
Twenty-six writes, and a power cut at each
Formatting and the five changes are 26 writes. tests/fsd/crash.sysk puts a recorder between the server and the driver: from write n on, it drops every write and flush and answers them done, as a disk does whose power has gone. Booted again on the same disk, the client says what the tree holds. The test does this at every write, and again with write n torn: its first 256 bytes new, its last 256 old. Every run finds one of the six states the changes went through, and a later cut never finds an earlier state. Pick a write.
Torn or cut, every run gives the same answer: a torn root fails its CRC, so the other root stands, and a torn table sector or block belongs to a change no root names yet. Past the last write, nothing is lost: the tree is d b1.
Mounting: free space is never stored
The server mounts the disk when it starts, and again after any failure. It reads both roots and takes the newest that is sound: right magic, version, size and CRC, every unused byte zero. It reads the table, checks each sector against its CRC in the root, and checks every node: a free node all zeros, the root a nameless directory, any other a named child of a directory, its map within the disk and its length within its map; names unique in each directory; every parent chain reaching the root. Then it walks every map and marks each sector it reaches, refusing any sector reached twice or past the disk's end. What it marked is the durable bitmap; everything else is free.
A disk whose two root slots are all zeros is formatted. Anything else unsound is refused, never repaired: every request then answers io (6), and the disk is left as it is. The tests damage a good disk five ways:
| Damage | What the server does |
|---|---|
| one byte in each root | refuses: neither root is sound, and they are not zeros, so it does not format |
| one byte in the root in use | mounts the other: the tree one change before (a d b1) |
| one byte in a table sector | refuses: its CRC in the root does not match |
| an index sector naming a sector past the disk's end | refuses: the map walk finds it |
| a root with a right CRC naming a table sector past the end, the other slot zeroed | refuses: the root is not sound, and one slot is not zeros |
What the server answers
The same ten operations as the kernel's tree, and the same header check (fs-begin, shared with kernel/files.sysp), but here write, create and remove do something. Whatever a request's 576 bytes say, fsd-serve ends with the server's state sound and a reply; sysp proves it. What sound means is said once, as Fs's invariant: every buffer its size, every number in its range (sysk 037, sysp 030). sysp asks it of the state wherever a function is handed it and gives it back, so no contract of the 39 functions that take it repeats it, where tree-ok once appeared 84 times. The checksums and copies take whole buffers, and their callers lend the part with a view: (crc32c (view (. fs table) (* t block) block)). The client has 8 fids.
| Op | On the disk's tree |
|---|---|
| open | to read, a file or a directory; to write, a file: a session. mode-truncate starts it empty |
| read | a file's bytes, holes as zeros; a directory's entries, 64 bytes each, with each file's length. A job's read that waits is held until the file's version moves or its deadline passes (sysk 033) |
| write | at any offset of the session's file, block by block; the reply's count says how many bytes |
| create | in a directory, a file (open for writing: a session, stored at clunk) or a directory (stored now); exists (15) if the name is taken |
| remove | a file, or an empty directory, at once; not-empty (16), and never the root |
| clunk | for the session's fid, the commit: its status says whether the file is stored (no-space 5, io 6) |
A job's waiting read (Reads that wait) is held in the lease's own variables, the deadline worked out once from the server's clock; while it is held the server reads none of the job's requests, and after each of the shell's, and at the alarm, it serves the read again: held still, or answered. A second session while one is open is busy (7). A session the client never clunks is not stored: its sectors are only pending, and the next mount forgets them.
In the shell
With a disk attached, the shell makes directories and files, and a command's lines can go into a file with >, or onto its end with >>. The file is stored when the command is done, whole. From the boot tests, two boots on one disk:
first boot, a fresh disk sysk> ls sys/ sysk> mkdir /notes sysk> echo (milk eggs) > /notes/shopping sysk> ls /sys/task > /notes/tasks sysk> greeter > /notes/greeting sysk> cat /notes/greeting greeter: hello from a job job ended second boot, the same disk sysk> echo more >> /notes/shopping sysk> cat /notes/shopping (milk eggs) more sysk> rm /notes not empty: /notes sysk> mkdir /notes exists: /notes sysk> rm /sys/time not permitted: /sys/time
Without a disk, the server answers every request io, and the shell says device failed: /; /sys is still there. make run attaches a 16 MiB disk, all the format uses.
Tested
- Five changes, each whole, kept.
tests/fsd/system.syskruns the client on a fresh disk: every change ok, and after themd b1. Booted again, it finds the same tree: making/dand/d/bagain is refused asexists(15), while/a, removed, is made again.big.syskdoes it with a 102,400-byte file, so the map goes to depth 2. - A power cut at every write, cut and torn, with
crash.syskandtests/fsd/recorder.sysp, above. - Damaged disks refused, above; and the shell's files across reboots.
A second client, while a job that binds the files service runs: the server keeps a table of 8 fids for it, each with its rights, lent it by the shell (Files for jobs, sysk 031). Not yet: more than one session at a time; disks past 16 MiB; trees past 64 nodes; caching sectors in memory; proving that mounting marks every sector the root reaches.