Communication with block drivers is asynchronous, but at this time, access to
these drivers is serialized on a per-driver basis. File Servers are treated
differently. VFS was designed to be able to send requests concurrently to File
Servers, although at the time of writing there are no File Servers that can
actually make use of that functionality. To identify which reply from an FS
belongs to which worker thread, all requests have an embedded transaction
identification number (a magic number + thread id encoded in the mtype field of
a message) which the FS has to echo upon reply. Because the range of valid
transaction IDs is isolated from valid system call numbers, VFS can use that ID
to differentiate between replies from File Servers and actual new system calls
from FSes. Using this mechanism VFS is able to support FUSE and ProcFS.
== Locking ==
## 4 Locking
To ensure correct execution of system calls, worker threads sometimes need
certain objects within VFS to remain unchanged during thread suspension
and resumption (i.e., when they need to communicate with a driver or File
Server). Threads keep most state on the stack, but there are a few global
variables that require protection: the fproc table, vmnt table, vnode table,
and filp table. Other tables such as lock table, select table, and dmap table
don't require protection by means of exclusive access. There it's required
and enough to simply mark an entry in use.
=== Locking requirements ===
## 4.1 Locking requirements
VFS implements the locking model described in [2]. For completeness of this
document we'll describe it here, too. The requirements are based on a threading
package that is non-preemptive. VFS must guarantee correct functioning with
several, semi-concurrently executing threads in any arbitrary order. The
latter requirement follows from the fact that threads need service from
other components like File Servers and drivers, and they may take any time
to complete requests.
1. Consistency of replicated values. Several system calls rely on VFS keeping a replicated representation of data in File Servers (e.g., file sizes, file modes, etc.).
1. Isolation of system calls. Many system calls involve multiple requests to FSes. Concurrent requests from other processes must not lead to otherwise impossible results (e.g., a chmod operation on a file cannot fail halfway through because it's suddenly unlinked or moved).
1. Integrity of objects. From the point of view of threads, obtaining mutual exclusion is a potentially blocking operation. The integrity of any objects used across blocking calls must be guaranteed (e.g., the file mode in a vnode must remain intact not only when talking to other components, but also when obtaining a lock on a filp).
1. No deadlock. Not one call may cause another call to never complete. Deadlock situations are typically the result of two or more threads that each hold exclusive access to one resource and want exclusive access to the resource held by the other thread. These resources are a) data (global variables) and b) worker threads.
a. Conflicts between locking of different types of objects can be avoided by keeping a locking order: objects of different type must always be locked in the same order. If multiple objects of the same type are to be locked, then first a "common denominator" higher up in the locking order must be locked.
a. Some threads can only run to completion when another thread does work on their behalf. Examples of this are drivers and file servers that do system calls on their own (e.g., ProcFS, PFS/UNIX Domain Sockets, FUSE) or crashing components (e.g., a driver for a character special file that crashes during a request; a second thread is required to handle resource clean up or driver restart before the first thread can abort or retry the request).
1. No starvation. VFS must guarantee that every system call completes in finite time (e.g., an infinite stream of reads must never completely block writes). Furthermore, we want to maximize parallelism to improve performance. This leads to:
1. A request to one File Server must not block access to other FS processes. This means that most forms of locking cannot take place at a global level, and must at most take place on the file system level.
1. No read-only operation on a regular file must block an independent read call to that file. In particular, (read-only) open and close operations may not block such reads, and multiple independent reads on the same file must be able to take place concurrently (i.e., reads that do not share a file position between their file descriptors).
=== Three-level Lock ===
## 4.2 Three-level Lock
From the requirements it follows that we need at least two locking types: read
and write locks. Concurrent reads are allowed, but writes are exclusive both
from reads and from each other. However, in a lot of cases it possible to use
a third locking type that is in between read and write lock: the serialize
lock. This is implemented in the three-level lock [2]. The three-level
lock provides:
TLL_READ: allows an unlimited number of threads to hold the lock with the
same type (both the thread itself and other threads); N * concurrent.
TLL_READSER: also allows an unlimited number of threads with type TLL_READ,
but only one thread can obtain serial access to the lock; N * concurrent +