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
The server's clients are the holders of its tree: each task whose profile mounts it (sysk 063). In the default system that is the shell. / in the shell's profile is the disk's tree, ("/" fsd), and tools/wire.rkt makes the two streams between them (sysk 062), and /sys the kernel's, as before. The server is an ordinary task: it holds its tree, a pair of streams to each holder, and two stream ends 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 ──fsd-ask-shell (576 bytes)──▶ fsd ──disk-ask (528)──▶ disk ──▶ virtio disk
◀──fsd-reply-shell────────── ◀──disk-answer──────
Both pairs are a client and its server, a request then its reply, which the deadlock check reads in order (pairs).
Every holder, in turn
The server takes the requests of every holder of its tree (sysk 063), up to four, through the kernel's Tree (Several clients, one server). Each holder has 8 fids of its own, and the job of a lease 8 more, so a holder's fid 1 is not another's: fid f of holder w is the server's 8w + f, and the job's come after the holders'. A holder attaches to the root with every right, and may lend nodes to the next job, up to fs-loan-max of them (sysk 089); a job attaches to one of what was lent it, by its number. A session, a file open for writing, is one holder's, and while it lasts another's write is answered busy, as a job's is. A holder's reads are answered at once, as before; only a job's may wait.
peer a ─┐ fids 0..7 holder 0, peer a
peer b ─┼─▶ fsd ─▶ disk 8..15 holder 1, peer b
hog ─┘ (one Tree) 16..23 holder 2, hog
32..39 the job of a lease
tests/clients/fsd.sysk runs two peers and a hog, all three holding one profile, (profile disk-only ("/" fsd)), the one the client of tests/fsd and the lender of Files for jobs hold alone. Each peer makes its file, /a or /b, trying again while the other's is being written (its create is answered busy: one session at a time), and looks for the other's until it is there. The hog sends two requests and reads no reply for a second. Its first reply waits unread, so its second request stays in its stream, and both peers are done before it wakes; then it reads both answers. A holder that stops reading holds up only itself.
A holder's root
A mount may name a directory of the server's tree, ("/" fsd "/pub") (sysk 064): its holder's whole tree is then that directory. The holder never says so. Its attach has no path, as any holder's, and the server attaches it at the root its mount gave it, which it learns from the kernel for the holder it is answering, tree-root, as it learns a lease's stamp. fsd finds it, home, before each of the holder's requests and passes it to the request: the whole tree, or the directory of that name in the root, or none while there is no such directory, when the attach answers no-such-name and a holder of the whole tree has to make it. The protocol has no .., so a walk from there only goes down, and a holder cannot remove its own root.
maker ("/" fsd) / the disk's /
/pub/x /pub/x
/secret /secret
guest ("/" fsd "/pub") / the disk's /pub
/x /pub/x
/secret nothing: no-such-name
tests/clients/sub.sysk runs the two: once the maker has made /pub, the guest attaches there, sees x, can name neither pub nor secret, is refused the removal of its root, and makes y, which the maker finds as /pub/y.
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 still reads the job's requests, for their end: a job stopped by Ctrl-C (sysk 074) ends them with its read unanswered, and the lease closes at once rather than at the deadline. After each of the shell's requests, 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, as a host shows them (syst):
first boot, a fresh disk / % ls dev/ net/ prg/ sys/ / % mkdir /notes / % echo (milk eggs) > /notes/shopping / % ls /sys/task > /notes/tasks / % wc /notes/shopping > /notes/count / % cat /notes/count (wc (bytes 12) (lines 1)) job ended second boot, the same disk / % echo more >> /notes/shopping / % cat /notes/shopping (milk eggs) more / % rm /notes not empty: /notes / % mkdir /notes exists: /notes / % 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.
- Three holders at once, with
tests/clients/fsd.sysk, above (sysk 063). - A holder rooted in a directory, with
tests/clients/sub.sysk, above (sysk 064).
A client more than the holders, 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 a holder (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.