The UNIX I/O System PS2:5-1
The UNIX I/O System
Dennis M. Ritchie
AT&T Bell Laboratories
Murray Hill, New Jersey 07974
This paper gives an overview of the workings of the UNIX-
I/O system. 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
ordinary files.
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
appears in ``UNIX Implementation;'' the current document restates
parts of that one, but is still more detailed. It is most useful
in conjunction with a copy of the system code, since it is basi-
cally an exegesis of that code.
Device Classes
There are two classes of device: block and character. 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,
since by use of forward and 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
file system. The interface to block devices is very highly struc-
tured; 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 major and a minor dev-
ice number. 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; macros major and minor
are available to access these numbers. The major device number
_________________________
-UNIX is a Trademark of Bell Laboratories.
April 27, 2013
PS2:5-2 The UNIX I/O System
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 simi-
lar 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.
Overview of I/O
The purpose of the open and creat system calls is to set up
entries in three separate system tables. The first of these is
the u_ofile table, which is stored in the system's per-process
data area u. This table is indexed by the file descriptor
returned by the open or creat, and is accessed during a read,
write, or other operation on the open file. An entry contains
only a pointer to the corresponding entry of the file table,
which is a per-system data base. There is one entry in the file
table for each instance of open or creat. This table is per-
system because the same instance of an open file must be shared
among the several processes which can result from forks after the
file is opened. A file table entry contains 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 inode table, 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 channels. In such a case,
instead of an offset, there is a pointer to an associated multi-
plex channel table. Multiplex channels will not be discussed
here.
An entry in the file table corresponds precisely to an
instance of open or creat; if the same file is opened several
times, it will have several entries in this table. However, there
is at most one entry in the inode table for a given file. Also, a
file may enter the inode 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 file
system.
An entry in the inode 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 allowed to disappear, and the device and
i-number whence the entry came. Also, the several block numbers
that give addressing information for the file are expanded from
April 27, 2013
The UNIX I/O System PS2:5-3
the 3-byte, compressed format used on the disk to full long quan-
tities.
During the processing of an open or creat call for a special
file, the system always calls the device's open routine to allow
for any special processing required (rewinding a tape, turning on
the data-terminal-ready lead of a modem, etc.). However, the
close routine is called only when the last process closes a file,
that is, when the i-node table entry is being deallocated. Thus
it is not feasible for a device to maintain, or depend on, a
count of its users, although it is quite possible to implement an
exclusive-use device which cannot be reopened until it has been
closed.
When a read or write takes place, the user's arguments and
the file table entry are used to set up the variables u.u_base,
u.u_count, and u.u_offset 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 rou-
tine is called; it is responsible for transferring data and
updating the count and current location appropriately as dis-
cussed below. Otherwise, the current location is used to calcu-
late a logical block number in the file. If the file is an ordi-
nary 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 bmap
routine. In any event, the resulting physical block number is
used, as discussed below, to read or write the appropriate dev-
ice.
Character Device Drivers
The cdevsw table specifies the interface routines present
for character devices. Each device provides five routines: open,
close, read, write, and special-function (to implement the ioctl
system call). Any of these may be missing. If a call on the rou-
tine should be ignored, (e.g. open on non-exclusive devices that
require no setup) the cdevsw entry can be given as nulldev; if it
should be considered an error, (e.g. write on read-only devices)
nodev is used. For terminals, the cdevsw structure also contains
a pointer to the tty structure associated with the terminal.
The open 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.
The close 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 performs the
final close.
April 27, 2013
PS2:5-4 The UNIX I/O System
When write is called, it is supplied the device as argument.
The per-user variable u.u_count has been set to the number of
characters indicated by the user; for character devices, this
number may be 0 initially. u.u_base is the address supplied by
the user from which to start taking characters. The system may
call the routine internally, so the flag u.u_segflg is supplied
that indicates, if on, that u.u_base refers to the system address
space instead of the user's.
The write routine should copy up to u.u_count characters
from the user's buffer to the device, decrementing u.u_count for
each character passed. For most drivers, which work one character
at a time, the routine cpass( ) is used to pick up characters
from the user's buffer. Successive calls on it return the charac-
ters to be written until u.u_count goes to 0 or an error occurs,
when it returns -1. Cpass takes care of interrogating u.u_segflg
and updating u.u_count.
Write routines which want to transfer a probably large
number of characters into an internal buffer may also use the
routine iomove(buffer, offset, count, flag) which is faster when
many characters must be moved. Iomove transfers up to count char-
acters into the buffer starting offset bytes from the start of
the buffer; flag should be B_WRITE (which is 0) in the write
case. Caution: the caller is responsible for making sure the
count is not too large and is non-zero. As an efficiency note,
iomove is much slower if any of buffer+offset, count or u.u_base
is odd.
The device's read routine is called under conditions similar
to write, except that u.u_count is guaranteed to be non-zero. To
return characters to the user, the routine passc(c) is available;
it takes care of housekeeping like cpass and returns -1 as the
last character specified by u.u_count is returned to the user;
before that time, 0 is returned. Iomove is also usable as with
write; the flag should be B_READ but the same cautions apply.
The ``special-functions'' routine is invoked by the stty and
gtty system calls as follows: (*p) (dev, v) where p is a pointer
to the device's routine, dev is the device number, and v is a
vector. In the gtty case, the device is supposed to place up to 3
words of status information into the vector; this will be
returned to the caller. In the stty case, v is 0; the device
should take up to 3 words of control information from the array
u.u_arg[0...2].
Finally, each device should have appropriate interrupt-time
routines. 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 dev-
ice number. After the interrupt has been processed, a return from
April 27, 2013
The UNIX I/O System PS2:5-5
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 routines
getc and putc. A queue header has the structure
struct {
int c_cc; /* character count */
char *c_cf; /* first character */
char *c_cl; /* last character */
} queue;
A character is placed on the end of a queue by putc(c, &queue)
where c is the character and queue is the queue header. The rou-
tine returns -1 if there is no space to put the character, 0 oth-
erwise. The first character on the queue may be retrieved by
getc(&queue) which returns either the (non-negative) character or
-1 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. Thus device
handlers, especially write routines, must take care to avoid gob-
bling up excessive numbers of characters.
The other major help available to device handlers is the
sleep-wakeup mechanism. The call sleep(event, priority) causes
the process to wait (allowing other processes to run) until the
event occurs; at that time, the process is marked ready-to-run
and the call will return when there is no process with higher
priority.
The call wakeup(event) indicates that the event has hap-
pened, that is, causes processes sleeping on the event to be
awakened. The event 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
are unique.
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 scheduling situation. A distinction is
made between processes sleeping at priority less than the parame-
ter PZERO and those at numerically larger priorities. The former
cannot be interrupted by signals, although it is conceivable that
it may be swapped out. Thus it is a bad idea to sleep with prior-
ity less than PZERO on an event which might never occur. On the
April 27, 2013
PS2:5-6 The UNIX I/O System
other hand, calls to sleep with larger priority may never return
if the process is terminated by some signal in the meantime.
Incidentally, it is a gross error to call sleep in a routine
called at interrupt time, since the process which is running is
almost certainly not the process which should go to sleep. Like-
wise, none of the variables in the user area ``u.'' should be
touched, let alone changed, by an interrupt routine.
If a device driver wishes to wait for some event for which
it is inconvenient or impossible to supply a wakeup, (for exam-
ple, a device going on-line, which does not generally cause an
interrupt), the call sleep(&lbolt, priority) may be given. Lbolt
is an external cell whose address is awakened once every 4
seconds by the clock interrupt routine.
The routines spl4( ), spl5( ), spl6( ), spl7( ) are avail-
able to set the processor priority level as indicated to avoid
inconvenient interrupts from the device.
If a device needs to know about real-time intervals, then
timeout(func, arg, interval) will be useful. This routine
arranges that after interval sixtieths of a second, the func will
be called with arg as argument, in the style (*func)(arg).
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 read the 201 Dataphone dp if there
is no response within a specified number of seconds. 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 can be going on at once. Also, the specified func is
called at clock-interrupt time, so it should conform to the
requirements of interrupt routines in general.
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
accessed frequently. The main data base for this mechanism is the
table of buffers buf. Each buffer header contains a pair of
pointers (b_forw, b_back) which maintain a doubly-linked list of
the buffers associated with a particular block device, and a pair
of pointers (av_forw, av_back) which generally maintain a
doubly-linked list of blocks which are ``free,'' that is, eligi-
ble 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. The buffer header also contains the device and block
number to which the buffer refers, and a pointer to the actual
storage associated with the buffer. There is a word count which
April 27, 2013
The UNIX I/O System PS2:5-7
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 rest of the system. Given a device and block
number, both bread and getblk return a pointer to a buffer header
for the block; the difference is that bread is guaranteed to
return a buffer actually containing the current data for the
block, while getblk 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 B_DONE bit; see below). 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. Getblk is used, for example, when a block is about
to be totally rewritten, so that its previous contents are not
useful; still, no other process can be allowed to refer to the
block until the new data is placed into it.
The breada routine is used to implement read-ahead. it is
logically similar to bread, but takes as an additional argument
the number of a block (on the same device) to be read asynchro-
nously after the specifically requested block is available.
Given a pointer to a buffer, the brelse routine makes the
buffer again available to other processes. It is called, for
example, after data has been extracted following a bread. 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.
Bwrite puts the buffer on the appropriate device queue, waits for
the write to be done, and sets the user's error flag if required.
Bawrite places the buffer on the device's queue, but does not
wait for completion, so that errors cannot be reflected directly
to the user. Bdwrite does not start any I/O operation at all, but
merely marks 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 first be written out.
Bwrite 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. Bawrite 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. Bdwrite is used when there is doubt
that the write is needed at the moment. For example, bdwrite is
called when the last byte of a write system call falls short of
the end of a block, on the assumption that another write will be
given soon which will re-use the same block. On the other hand,
as the end of a block is passed, bawrite is called, since prob-
ably the block will not be accessed again soon and one might as
well start the writing process as soon as possible.
April 27, 2013
PS2:5-8 The UNIX I/O System
In any event, notice that the routines getblk and bread
dedicate the given block exclusively to the use of the caller,
and make others wait, while one of brelse, bwrite, bawrite, or
bdwrite 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. Since they provide one impor-
tant channel for information between the drivers and the block
I/O system, it is important to understand these flags. The fol-
lowing names are manifest constants which select the associated
flag bits.
B_READ This bit is set when the buffer is handed to the device
strategy routine (see below) to indicate a read opera-
tion. The symbol B_WRITE is defined as 0 and does not
define a flag; it is provided as a mnemonic convenience
to callers of routines like swap which have a separate
argument which indicates read or write.
B_DONE This bit is set 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 argu-
ment of getblk to indicate if 1 that the returned
buffer actually contains the data in the requested
block.
B_ERROR This bit may be set to 1 when B_DONE is set to indicate
that an I/O or other error occurred. If it is set the
b_error byte of the buffer header may contain an error
code if it is non-zero. If b_error is 0 the nature of
the error is not specified. Actually no driver at
present sets b_error; the latter is provided for a
future improvement whereby a more detailed error-
reporting scheme may be implemented.
B_BUSY This bit indicates that the buffer header is not on the
free list, i.e. is dedicated to someone's exclusive
use. The buffer still remains attached to the list of
blocks associated with its device, however. When getblk
(or bread, 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 clears.
B_PHYS This bit is set for raw I/O transactions that need to
allocate the Unibus map on an 11/70.
B_MAP This bit is set on buffers that have the Unibus map
allocated, so that the iodone routine knows to deallo-
cate the map.
B_WANTED This flag is used in conjunction with the B_BUSY bit.
Before sleeping as described just above, getblk sets
April 27, 2013
The UNIX I/O System PS2:5-9
this flag. Conversely, when the block is freed and the
busy bit goes down (in brelse) a wakeup is given for
the block header whenever B_WANTED is on. This stra-
tegem avoids the overhead of having to call wakeup
every time a buffer is freed on the chance that someone
might want it.
B_AGE This bit may be set on buffers just before releasing
them; if it is on, the buffer is placed at the head of
the free list, rather than at the tail. It is a perfor-
mance heuristic used when the caller judges that the
same block will not soon be used again.
B_ASYNC This bit is set by bawrite to indicate to the appropri-
ate device driver that the buffer should be released
when the write has been finished, usually at interrupt
time. The difference between bwrite and bawrite is that
the former starts I/O, waits until it is done, and
frees the buffer. The latter merely sets this bit and
starts I/O. The bit indicates that relse should be
called for the buffer on completion.
B_DELWRI This bit is set by bdwrite before releasing the buffer.
When getblk, while searching for a free block, discov-
ers the bit is 1 in a buffer it would otherwise grab,
it causes the block to be written out before reusing
it.
Block Device Drivers
The bdevsw table contains the names of the interface rou-
tines and that of a table for each block device.
Just as for character devices, block device drivers may sup-
ply an open and a close routine called respectively on each open
and on the final close of the device. Instead of separate read
and write routines, each block device driver has a strategy rou-
tine which is called with a pointer to a buffer header as argu-
ment. 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 rou-
tine is to carry out the operation as requested by the informa-
tion in the buffer header. When the transaction is complete the
B_DONE (and possibly the B_ERROR) bits should be set. Then if the
B_ASYNC bit is set, brelse should be called; otherwise, wakeup.
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 the
buffer header; otherwise, the residual count should be set to 0.
This particular mechanism is really for the benefit of the
magtape driver; when reading this device records shorter than
requested are quite normal, and the user should be told the
actual length of the record.
April 27, 2013
PS2:5-10 The UNIX I/O System
Although the most usual argument to the strategy routines 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 appropriate information. For example the swap rou-
tine, which manages movement of core images to and from the swap-
ping device, uses the strategy routine for this device. Care has
to be taken that no extraneous bits get turned on in the flag
word.
The device's table specified by bdevsw has a byte to contain
an active flag and an error count, a pair of links which consti-
tute the head of the chain of buffers for the device (b_forw,
b_back), and a first and last pointer for a device queue. Of
these things, all are used solely by the device driver itself
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 when errors occur. The device queue is used
to remember stacked requests; in the simplest case it may be
maintained as a first-in first-out list. 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 (av_forw, av_back) are also used to contain the
pointers which maintain the device queues.
A couple of routines are provided which are useful to block
device drivers. iodone(bp) arranges that the buffer to which bp
points be released or awakened, as appropriate, when the strategy
module has finished with the buffer, either normally or after an
error. (In the latter case the B_ERROR bit has presumably been
set.)
The routine geterror(bp) can be used to examine the error
bit in a buffer header and arrange that any error indication
found therein is reflected to the user. It may be called only in
the non-interrupt part of a driver when I/O has completed (B_DONE
has been set).
Raw Block-device I/O
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 caller requests. The method involves
setting up a character-type special file corresponding to the raw
device and providing read and write routines which set up what is
usually a private, non-shared buffer header with the appropriate
information and call the device's strategy routine. If desired,
separate open and close routines may be provided but this is usu-
ally unnecessary. A special-function routine might come in handy,
especially for magtape.
A great deal of work has to be done to generate the
April 27, 2013
The UNIX I/O System PS2:5-11
``appropriate information'' to put in the argument buffer for the
strategy module; the worst part is to map relocated user
addresses to physical addresses. Most of this work is done by
physio(strat, bp, dev, rw) whose arguments are the name of the
strategy routine strat, the buffer pointer bp, the device number
dev, and a read-write flag rw whose value is either B_READ or
B_WRITE. Physio 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 in physical space; 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.
April 27, 2013
Generated on 2013-04-27 00:20:00 by $MirOS: src/scripts/roff2htm,v 1.77 2013/01/01 20:49:09 tg Exp $
These manual pages and other documentation are copyrighted by their respective writers;
their source is available at our CVSweb,
AnonCVS, and other mirrors. The rest is Copyright © 2002‒2013 The MirOS Project, Germany.
This product includes material
provided by Thorsten Glaser.
This manual page’s HTML representation is supposed to be valid XHTML/1.1; if not, please send a bug report – diffs preferred.