This paper gives an overview of the workings of the UNIX\(dg
\(dgUNIX is a Trademark of Bell Laboratories.
It was written with an eye toward providing
guidance to writers of device driver routines,
and is oriented more toward describing the environment
and nature of device drivers than the implementation
of that part of the file system which deals with
It is assumed that the reader has a good knowledge
of the overall structure of the file system as discussed
in the paper ``The UNIX Time-sharing System.''
A more detailed discussion
the current document restates parts of that one,
but is still more detailed.
conjunction with a copy of the system code,
since it is basically an exegesis of that code.
There are two classes of device:
The block interface is suitable for devices
like disks, tapes, and DECtape
which work, or can work, with addressible 512-byte blocks.
Ordinary magnetic tape just barely fits in this category,
backward spacing any block can be read, even though
blocks can be written only at the end of the tape.
Block devices can at least potentially contain a mounted
The interface to block devices is very highly structured;
the drivers for these devices share a great many routines
as well as a pool of buffers.
Character-type devices have a much
more straightforward interface, although
more work must be done by the driver itself.
Devices of both types are named by a
These numbers are generally stored as an integer
with the minor device number
in the low-order 8 bits and the major device number
in the next-higher 8 bits;
are available to access these numbers.
The major device number selects which driver will deal with
the device; the minor device number is not used
by the rest of the system but is passed to the
driver at appropriate times.
Typically the minor number
selects a subdevice attached to
a given controller, or one of
several similar hardware interfaces.
The major device numbers for block and character devices
are used as indices in separate tables;
they both start at 0 and therefore overlap.
system calls is to set up entries in three separate
The first of these is the
which is stored in the system's per-process
the file descriptor returned by the
or other operation on the open file.
a pointer to the corresponding
which is a per-system data base.
There is one entry in the
This table is per-system because the same instance
of an open file must be shared among the several processes
after the file is opened.
flags which indicate whether the file
was open for reading or writing or is a pipe, and
a count which is used to decide when all processes
using the entry have terminated or closed the file
(so the entry can be abandoned).
There is also a 32-bit file offset
which is used to indicate where in the file the next read
or write will take place.
Finally, there is a pointer to the
entry for the file in the
which contains a copy of the file's i-node.
Certain open files can be designated ``multiplexed''
files, and several other flags apply to such
In such a case, instead of an offset,
there is a pointer to an associated multiplex channel table.
Multiplex channels will not be discussed here.
table corresponds precisely to an instance of
if the same file is opened several times,
there is at most one entry
Also, a file may enter the
table not only because it is open,
but also because it is the current directory
of some process or because it
is a special file containing a currently-mounted
table differs somewhat from the
corresponding i-node as stored on the disk;
the modified and accessed times are not stored,
and the entry is augmented
by a flag word containing information about the entry,
a count used to determine when it may be
and the device and i-number
Also, the several block numbers that give addressing
information for the file are expanded from
the 3-byte, compressed format used on the disk to full
During the processing of an
the system always calls the device's
routine to allow for any special processing
required (rewinding a tape, turning on
the data-terminal-ready lead of a modem, etc.).
routine is called only when the last
that is, when the i-node table entry
for a device to maintain, or depend on,
a count of its users, although it is quite
implement an exclusive-use device which cannot
be reopened until it has been closed.
table entry are used to set up the
which respectively contain the (user) address
of the I/O target area, the byte-count for the transfer,
and the current location in the file.
If the file referred to is
a character-type special file, the appropriate read
or write routine is called; it is responsible
for transferring data and updating the
count and current location appropriately
Otherwise, the current location is used to calculate
a logical block number in the file.
If the file is an ordinary file the logical block
number must be mapped (possibly using indirect blocks)
to a physical block number; a block-type
special file need not be mapped.
This mapping is performed by the
In any event, the resulting physical block number
is used, as discussed below, to
read or write the appropriate device.
table specifies the interface routines present for
Each device provides five routines:
open, close, read, write, and special-function
Any of these may be missing.
on non-exclusive devices that require no setup)
if it should be considered an error,
structure also contains a pointer to the
structure associated with the terminal.
routine is called each time the file
is opened with the full device number as argument.
The second argument is a flag which is
non-zero only if the device is to be written upon.
routine is called only when the file
is closed for the last time,
that is when the very last process in
which the file is open closes it.
This means it is not possible for the driver to
maintain its own count of its users.
The first argument is the device number;
the second is a flag which is non-zero
if the file was open for writing in the process which
is called, it is supplied the device
the number of characters indicated by the user;
for character devices, this number may be 0
is the address supplied by the user from which to start
routine internally, so the
is supplied that indicates,
refers to the system address space instead of
characters from the user's buffer to the device,
for each character passed.
For most drivers, which work one character at a time,
is used to pick up characters
Successive calls on it return
the characters to be written until
goes to 0 or an error occurs,
takes care of interrogating
Write routines which want to transfer
a probably large number of characters into an internal
buffer may also use the routine
.I "iomove(buffer, offset, count, flag)"
which is faster when many characters must be moved.
bytes from the start of the buffer;
(which is 0) in the write case.
the caller is responsible for making sure
the count is not too large and is non-zero.
.I "buffer+offset, count"
routine is called under conditions similar to
is guaranteed to be non-zero.
To return characters to the user, the routine
is available; it takes care of housekeeping
and returns \(mi1 as the last character
before that time, 0 is returned.
but the same cautions apply.
The ``special-functions'' routine
is a pointer to the device's routine,
the device is supposed to place up to 3 words of status information
into the vector; this will be returned to the caller.
the device should take up to 3 words of
Finally, each device should have appropriate interrupt-time
When an interrupt occurs, it is turned into a C-compatible call
on the devices's interrupt routine.
The interrupt-catching mechanism makes
the low-order four bits of the ``new PS'' word in the
trap vector for the interrupt available
to the interrupt handler.
This is conventionally used by drivers
which deal with multiple similar devices
to encode the minor device number.
After the interrupt has been processed,
a return from the interrupt handler will
return from the interrupt itself.
A number of subroutines are available which are useful
to character device drivers.
Most of these handlers, for example, need a place
to buffer characters in the internal interface
between their ``top half'' (read/write)
and ``bottom half'' (interrupt) routines.
For relatively low data-rate devices, the best mechanism
is the character queue maintained by the
A queue header has the structure
int c_cc; /* character count */
char *c_cf; /* first character */
char *c_cl; /* last character */
A character is placed on the end of a queue by
The routine returns \(mi1 if there is no space
to put the character, 0 otherwise.
The first character on the queue may be retrieved
which returns either the (non-negative) character
or \(mi1 if the queue is empty.
Notice that the space for characters in queues is
shared among all devices in the system
and in the standard system there are only some 600
character slots available.
especially write routines, must take
care to avoid gobbling up excessive numbers of characters.
The other major help available
to device handlers is the sleep-wakeup mechanism.
.I "sleep(event, priority)"
causes the process to wait (allowing other processes to run)
at that time, the process is marked ready-to-run
and the call will return when there is no
has happened, that is, causes processes sleeping
on the event to be awakened.
is an arbitrary quantity agreed upon
by the sleeper and the waker-up.
By convention, it is the address of some data area used
by the driver, which guarantees that events
Processes sleeping on an event should not assume
that the event has really happened;
they should check that the conditions which
caused them to sleep no longer hold.
Priorities can range from 0 to 127;
a higher numerical value indicates a less-favored
A distinction is made between processes sleeping
at priority less than the parameter
and those at numerically larger priorities.
be interrupted by signals, although it
is conceivable that it may be swapped out.
Thus it is a bad idea to sleep with
priority less than PZERO on an event which might never occur.
On the other hand, calls to
may never return if the process is terminated by
some signal in the meantime.
Incidentally, it is a gross error to call
in a routine called at interrupt time, since the process
which is running is almost certainly not the
process which should go to sleep.
Likewise, none of the variables in the user area
should be touched, let alone changed, by an interrupt routine.
wishes to wait for some event for which it is inconvenient
or impossible to supply a
(for example, a device going on-line, which does not
generally cause an interrupt),
.I "sleep(&lbolt, priority)
is an external cell whose address is awakened once every 4 seconds
by the clock interrupt routine.
.I "spl4( ), spl5( ), spl6( ), spl7( )"
set the processor priority level as indicated to avoid
inconvenient interrupts from the device.
If a device needs to know about real-time intervals,
.I "timeout(func, arg, interval)
This routine arranges that after
sixtieths of a second, the
as argument, in the style
Timeouts are used, for example,
to provide real-time delays after function characters
like new-line and tab in typewriter output,
and to terminate an attempt to
if there is no response within a specified number
Notice that the number of sixtieths of a second is limited to 32767,
since it must appear to be positive,
and that only a bounded number of timeouts
is called at clock-interrupt time, so it should
conform to the requirements of interrupt routines
The Block-device Interface
Handling of block devices is mediated by a collection
of routines that manage a set of buffers containing
the images of blocks of data on the various devices.
The most important purpose of these routines is to assure
that several processes that access the same block of the same
device in multiprogrammed fashion maintain a consistent
view of the data in the block.
A secondary but still important purpose is to increase
the efficiency of the system by
keeping in-core copies of blocks that are being
The main data base for this mechanism is the
Each buffer header contains a pair of pointers
which maintain a doubly-linked list
of the buffers associated with a particular
which generally maintain a doubly-linked list of blocks
which are ``free,'' that is,
eligible to be reallocated for another transaction.
Buffers that have I/O in progress
or are busy for other purposes do not appear in this list.
also contains the device and block number to which the
buffer refers, and a pointer to the actual storage associated with
which is the negative of the number of words
to be transferred to or from the buffer;
there is also an error byte and a residual word
count used to communicate information
from an I/O routine to its caller.
Finally, there is a flag word
with bits indicating the status of the buffer.
These flags will be discussed below.
Seven routines constitute
the most important part of the interface with the
Given a device and block number,
return a pointer to a buffer header for the block;
is guaranteed to return a buffer actually containing the
current data for the block,
returns a buffer which contains the data in the
block only if it is already in core (whether it is
or not is indicated by the
In either case the buffer, and the corresponding
device block, is made ``busy,''
so that other processes referring to it
are obliged to wait until it becomes free.
when a block is about to be totally rewritten,
so that its previous contents are
still, no other process can be allowed to refer to the block
until the new data is placed into it.
routine is used to implement read-ahead.
it is logically similar to
but takes as an additional argument the number of
a block (on the same device) to be read asynchronously
after the specifically requested block is available.
Given a pointer to a buffer,
makes the buffer again available to other processes.
It is called, for example, after
data has been extracted following a
There are three subtly-different write routines,
all of which take a buffer pointer as argument,
and all of which logically release the buffer for
use by others and place it on the free list.
buffer on the appropriate device queue,
waits for the write to be done,
and sets the user's error flag if required.
places the buffer on the device's queue, but does not wait
for completion, so that errors cannot be reflected directly to
does not start any I/O operation at all,
the buffer so that if it happens
to be grabbed from the free list to contain
data from some other block, the data in it will
is used when one wants to be sure that
I/O takes place correctly, and that
errors are reflected to the proper user;
it is used, for example, when updating i-nodes.
is useful when more overlap is desired
(because no wait is required for I/O to finish)
but when it is reasonably certain that the
write is really required.
is used when there is doubt that the write is
is called when the last byte of a
system call falls short of the end of a
block, on the assumption that
will be given soon which will re-use the same block.
as the end of a block is passed,
is called, since probably the block will
not be accessed again soon and one might as
well start the writing process as soon as possible.
In any event, notice that the routines
dedicate the given block exclusively to the
use of the caller, and make others wait,
.I "brelse, bwrite, bawrite,"
must eventually be called to free the block for use by others.
As mentioned, each buffer header contains a flag
word which indicates the status of the buffer.
one important channel for information between the drivers and the
block I/O system, it is important to understand these flags.
The following names are manifest constants which
select the associated flag bits.
This bit is set when the buffer is handed to the device strategy routine
(see below) to indicate a read operation.
is defined as 0 and does not define a flag; it is provided
as a mnemonic convenience to callers of routines like
which have a separate argument
which indicates read or write.
to 0 when a block is handed to the the device strategy
routine and is turned on when the operation completes,
whether normally as the result of an error.
It is also used as part of the return argument of
to indicate if 1 that the returned
buffer actually contains the data in the requested block.
This bit may be set to 1 when
is set to indicate that an I/O or other error occurred.
byte of the buffer header may contain an error code
is 0 the nature of the error is not specified.
Actually no driver at present sets
the latter is provided for a future improvement
whereby a more detailed error-reporting
scheme may be implemented.
This bit indicates that the buffer header is not on
dedicated to someone's exclusive use.
The buffer still remains attached to the list of
blocks associated with its device, however.
which calls it) searches the buffer list
for a given device and finds the requested
block with this bit on, it sleeps until the bit
This bit is set for raw I/O transactions that
need to allocate the Unibus map on an 11/70.
This bit is set on buffers that have the Unibus map allocated,
routine knows to deallocate the map.
This flag is used in conjunction with the
Before sleeping as described
Conversely, when the block is freed and the busy bit
is given for the block header whenever
This strategem avoids the overhead
every time a buffer is freed on the chance that someone
This bit may be set on buffers just before releasing them; if it
the buffer is placed at the head of the free list, rather than at the
It is a performance heuristic
used when the caller judges that the same block will not soon be used again.
to indicate to the appropriate device driver
that the buffer should be released when the
write has been finished, usually at interrupt time.
is that the former starts I/O, waits until it is done, and
The latter merely sets this bit and starts I/O.
should be called for the buffer on completion.
before releasing the buffer.
while searching for a free block,
discovers the bit is 1 in a buffer it would otherwise grab,
it causes the block to be written out before reusing it.
table contains the names of the interface routines
and that of a table for each block device.
Just as for character devices, block device drivers may supply
called respectively on each open and on the final close
Instead of separate read and write routines,
each block device driver has a
routine which is called with a pointer to a buffer
As discussed, the buffer header contains
a read/write flag, the core address,
the block number, a (negative) word count,
and the major and minor device number.
The role of the strategy routine
is to carry out the operation as requested by the
information in the buffer header.
When the transaction is complete the
In cases where the device
is capable, under error-free operation,
of transferring fewer words than requested,
the device's word-count register should be placed
in the residual count slot of
otherwise, the residual count should be set to 0.
This particular mechanism is really for the benefit
records shorter than requested are quite normal,
and the user should be told the actual length of the record.
Although the most usual argument
is a genuine buffer header allocated as discussed above,
all that is actually required
is that the argument be a pointer to a place containing the
routine, which manages movement
of core images to and from the swapping device,
uses the strategy routine
Care has to be taken that
no extraneous bits get turned on in the
The device's table specified by
byte to contain an active flag and an error count,
a pair of links which constitute the
head of the chain of buffers for the device
and a first and last pointer for a device queue.
Of these things, all are used solely by the device driver
except for the buffer-chain pointers.
Typically the flag encodes the state of the
device, and is used at a minimum to
indicate that the device is currently engaged in
transferring information and no new command should be issued.
The error count is useful for counting retries
The device queue is used to remember stacked requests;
in the simplest case it may be maintained as a first-in
Since buffers which have been handed over to
the strategy routines are never
on the list of free buffers,
the pointers in the buffer which maintain the free list
are also used to contain the pointers
which maintain the device queues.
are provided which are useful to block device drivers.
arranges that the buffer to which
points be released or awakened,
strategy module has finished with the buffer,
either normally or after an error.
bit has presumably been set.)
can be used to examine the error bit in a buffer header
and arrange that any error indication found therein is
It may be called only in the non-interrupt
part of a driver when I/O has completed
A scheme has been set up whereby block device drivers may
provide the ability to transfer information
directly between the user's core image and the device
without the use of buffers and in blocks as large as
The method involves setting up a character-type special file
corresponding to the raw device
routines which set up what is usually a private,
non-shared buffer header with the appropriate information
and call the device's strategy routine.
routines may be provided but this is usually unnecessary.
A special-function routine might come in handy, especially for
A great deal of work has to be done to generate the
``appropriate information''
to put in the argument buffer for
the worst part is to map relocated user addresses to physical addresses.
Most of this work is done by
.I "physio(strat, bp, dev, rw)
whose arguments are the name of the
makes sure that the user's base address and count are
even (because most devices work in words)
and that the core area affected is contiguous
it delays until the buffer is not busy, and makes it
busy while the operation is in progress;
and it sets up user error return information.