Required reading: Chapter 18, 19, and chapter 20 (from "Resource
Allocation", pp. 20-4)
Users desire to store their data persistently so that data survives
when the user turns of his computer. The primary media for doing so
are: magnetic disks, flash memory, and tapes. We focus on magnetic
disks (e.g., the RK in v6).
To help users to remember where they stored their data, most
systems allow users to assign their own names to their data.
Typically the data is organized in files and users assign names to
files. To deal with many files, users can organize their files in
directories, in a hierarchical manner. To avoid that users have to
type long abolute names (e.g., in UNIX absolute names start with "/"),
users can change their working directory and use relative names .
In v6, File namespace operations include create, link, unlink, and
chdir; later UNIXes added rename, mkdir, etc. (How is "mv a b"
implemented in v6? Answer: "link a b"; "unlink "a".) To be able to
name the current directory and the parent directory every directory
includes two entries "." and "..".
A user grafts new file systems on a name space using mount. Umount
removes a file system from the name space. (In DOS, a file system is
named by its device letter.)
The data in a file can be organized in a structured way or not.
The structured variant is often called a database. UNIX uses the
unstructured variant: files are streams of bytes. Any particular
structure is likely to be useful to only a small class of
applications, and other applications will have to work hard to fit
their data into one of the pre-defined structures. Besides, if you
want structure, you can easily write a user-mode library program that
imposes that format on any file. The end-to-end argument in action.
A key issue is the semantics of an update. If a program updates a
file, when are the effects of the update persistent? In particular,
what happens if the logical update requires writing multiple disks
blocks and the power fails during the update. Can it happen that an
update happens only partially? To solve this problem correctly one
needs atomic operations with respect to failures.
Another key issue is what the semantics are of concurrent writes to
the same data item. What is the order of two updates that happen at
the same time? To solve this problem correctly one needs atomic
operations with respect to concurrency.
In v6, a file is a byte stream. The v6 file calls are open, read,
write, seek, close, and stat. Dup duplicates a file descriptor. Data
for a file is reclaimed if it doesn't appear in the name space
anymore. Each file descriptor has a file offset. Read/write
move it implicitly, seek moves it explicitly. Two processes that
share a file because one process is the child (and inherited an open
file descriptor from its parent) will share an offset pointer into the
file: their bytes will be ordered serially in some order; in practice,
one write after the other. Two processes that open the same file will
each have their own offset into the file and may overwrite each
A final key issue is performance, because writing to magnetic disk
is relatively expensive compared to computing. (This is true for the
PDP11/RK6 too.) Two primary ways to improve performance are: careful
file system layout that induces few seeks and overlap I/O with
computation so that file operations don't have to wait until their
completion and so that that the disk driver has more data to write,
which allows disk scheduling etc. An additional method is to cheat on
the semantics of modifications, and give up on atomicity.
V6 follows the last two methods. It doesn't pay attention to file
system layout. It overlaps computation and I/O, but doesn't do any
disk scheduling. It cheats on semantics: when one closes a file, some
of its data may not have been written to disk yet, while other blocks
may have been written---v6 is more careful with i-nodes (probably,
mostly accidently). Later in some of the papers, we will see how one
can do better.
V6 code examples
On disk files are represented by an inode (ino.h), and blocks.
Small files have 8 direct pointers; in large files the eight pointers
are pointers to a block of pointers (see bmap, 6415). Files are
limited to 2^15 blocks. Directories are files with structure: 14-byte
name plus 2-byte inode number. In memory files are represented by a
file structure (struct file) and an in-core inode (inode.h).
- Name space.
- iget. get an inode.
- 7285: check incore inode table.
- 7292--7297: deal with mounted files systems. For example, "mount
/dev/rk0 /mnt/", will create an inode with IMOUNT for /mnt, which will
point to the inode for /dev/rk.
- 7316: does this lock work on multiprocessors? (Answer: no.)
- 7319: read block that contains the inode.
- 7330: copy the inode on disk into the in-core inode structure.
- namei converts pathnames into a pointer to an in-core inode. does
the function win a prize for elegance?
- 7531. Where is the current working directory maintained? (Answer:
struct user.) Why is the current directory maintained in the kernel?
(Answer: no particular reason, because the current directory could
just be another open file descriptor passed to the process on startup
(like the STDIN, STDOUT and STDERR are).
- 7534: lock inode!
- 7535: ////a////b is allowed!
- 7571: which characters are allowed in a directory name?
- Why are names restricted to 14 (DIRSIZE) bytes? (Answer: 16 bytes
is a convenient directory entry size: 14 bytes name, 2 bytes inode
number. With a block size of 512 bytes directory entries don't span
- 7622: directory block is read with bread(). bmap converts the
logical block number into a physical block number. Another process may
get scheduled now, but bread blocks to wait for the disk read to
- 7763: call iput to release lock!
- 7664: read the inode for the matched entry.
- The directory tree is acyclic; links to directories aren't
allowed, except for super users! (see line 5921). This allows
reference counters to be used, which is implemented by nlink. Link
increases it. Unlink decreases it. Iput checks it (and frees blocks,
- Link, unlink, chdir, mount, umount could have taken file
descriptors instead of their path argument. In fact, this would get
rid of some possible race conditions (some of which have security
implications, TOCTTOU). However, this would require that the current
working directory be remembered by the process, and UNIX didn't have
good ways of maintaining static state shared among all processes
belonging to a given user. The easiest way is to create shared state
is to place it in the kernel.
Example of TOCTTOU:
rename ("tmp/etc", "/tmp/x");
symlink ("etc", "/tmp/etc");
Lstat checks whether /tmp/etc is not symbolic link, but by the time it
runs unlink the attacker had time to creat a symbolic link in the
place of /tmp/etc.
- File operations.
- Maintaining the file offset (f_offset in struct file) behind the
read/write interface is a controversial design decision . The
alternative is that the state of a read operation should be maintained
by the process doing the reading (i.e., that the pointer should be
passed as an argument to read). This argument is compelling in view
of the UNIX fork() semantics, which clones a process which shares the
file descriptors of its parent. A read by the parent of a shared file
descriptor (e.g., stdin, changes the read pointer seen by the child).
On the other hand the alternative would make it difficult to get
"(data; ls) > x" right.
- rdwr, 5731. What is the test on line 5746 for? (Answer: check
whether process is reading/writing to pipe; if so, call pipe
- Writei. On a small write, is the block first read? (Answer: yes,
- What is the test on line 6309 for? Answer: if we have written a
complete block, write it out asynchronously and release it; otherwise,
write it out delayed, because with a bit of luck the next write will
be to the same block.
- Readi. What is the test on line 6255? Answer: if we are reading
sequentially, read a block ahead; otherwise, not.
- closef. Only on last close, call closei, which calls iput, which
writes i-node using bwrite(), which waits for completion. We have to
do so, because the incore inode table is not a true cache; as soon as
no process is using the inode, v6 writes it out to the disk (e.g.,
instead of waiting until the replacement policy throws it out).
- Disk layout. See bmap() and ialloc/alloc. No really smart layout
- Overlapping I/O. Reading is done synchronous, except for read
ahead. Writing is always done asynchronously, except for inodes
(iupdate uses bdwrite).
- Reliability. No semantics that the programmer can rely on. V6
calls Update() periodically to write out all dirty blocks. V6 writes
inodes synchronously when no process is using the inode.
- Suppose a program creates a file "foo" on a rk disk, writes 1
byte (containing "a") to it, calls close, and the power fails right
after the call to closef() on line 5854 completes. What are the
possible states that the disk is in? More specifically:
- Is there an inode for "foo" stored on the disk? If so, what is its
content? (Answer: yes, because fclose will call iupdate, which calls
bwrite. the inode will have the content reflecting the one-byte
- Is there a data block for "foo" stored on the disk? If so, what is
its content? (Answer: perhaps. the data block may not have been
written out at the time of the power failure, because partially-filled
blocks are written using bdwrite. thus, the inode will list the data
block number, pointing effectively to a block whose content has
perhaps no relation to "foo".)
- Is there a directory entry for "foo"? Why? Why not? (Answer:
perhaps; the inode of the updated directory is on disk, because iput
will find i_count is 1, and write the inode using iupdate. the data
block, however, might not be, because if the data block is partially
filled it will be written using bdwrite. Note, however, that if the
data block just happens to be full, the iwrite call in wdir will use
bawrite, which will enter the write operation in the disk queue; then,
the iput call in wdir will cause a write of the inode using bdwrite;
bdwrite will first wait until the preceding operations in the queue
have completed; thus, in this special case the data block will be on
- How does UNIX recover from this mess? When the operating starts
again the sys admin runs programs (INUM, etc., which later were
replaced by fsck) that fix up to disk to some consistent state, with
the help of the sys admin. Of course, some recent changes may be lost
(e.g., the byte in "foo").
- File locking. No file locking at the application
level. Protection bits can be used, but only by processes that don't
run as superuser.