MirOS Manual: 03.iosys(PSD)


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.

                          July 4, 2014

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

                          July 4, 2014

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.

                          July 4, 2014

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

                          July 4, 2014

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

                          July 4, 2014

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

                          July 4, 2014

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.

                          July 4, 2014

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

                          July 4, 2014

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.

                          July 4, 2014

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

                          July 4, 2014

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.

                          July 4, 2014

Generated on 2014-07-04 21:17:45 by $MirOS: src/scripts/roff2htm,v 1.79 2014/02/10 00:36:11 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‒2014 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.