15 Introduction to Basic I/O

There are three files whose contents need to be thoroughly absorbed before the subject of UNIX input/output is broached in detail.

15.1 The File ‘buf.h’

This file declares two structures called “buf” (4520) and “devtab” (4551). Instances of the structure “buf” are declared as ’bfreelist (4567) and as the array “buf” (!) (4535) with “NBUF” elements.

The structure “buf” is possibly misnamed because it is in fact a buffer header (or buffer control block). The buffer areas proper are allocated separately and declared (4720) as 

   ``char buffers [NBUF] [514];''

Pointers from the “buf” array to the “buffers” array are set up by the procedure “binit”.

Other instances of the structure “buf” are declared as “swbuf” (4721) and “rrkbuf” (5387). No 514 character buffer areas are associated with “bfreelist” or “swbuf” or “rrkbuf”.

The “buf” structure may be divided into three parts:

(a) flags

These convey status information and are contained within a single word. Masks for setting these flags are defined as “B_WRITE”, “B_READ” etc. in lines 4572 to 4586.

(b) list pointer

Forward and backward pointers for two doubly linked lists, which we shall refer to as the “b”-list and the “av”-list.

(c) i/o parameters

A set of values associated with the actual data transfer.

15.2 devtab (4551)

The “devtab” structure has five words, the last four of which are forward and backward pointers.

One instance of “devtab” is declared within the device handler for each block type of peripheral device. For our model system the only block device is the RK05 disk, and “rktab” is declared as a “devtab” structure at line 5386.

The “devtab” structure contains some status information for the the device and serves as a list head for:

(a)

the list of buffers associated with the device, and simultaneously on the “av”-list;

(b)

the list of outstanding i/o requests for the device.

15.3 The File ‘conf.h’

The file “conf.h” declares:

  • yet another way to dissect an integer into two parts (“d_minor” and “d_major”). Note that “d_major” corresponds to “hibyte” (0180);

  • two arrays of structures;

  • two integer variables, “nlkdev” and “nchrdev”.

The two arrays of structures, “bdevsw” and “cdevsw”, are declared but not dimensioned or initialised in “conf.h”. The initialisation of these arrays is performed in the file “conf.c”.

15.4 The File ‘conf.c’

This file, along with “low.s”, is generated individually at each installation (to reflect the set of peripherals actually installed) by the program “mkconf”. (In our case, “conf.c” reflects the representative devices for our model system.)

This file initialises the following: 

  bdevsw  (4656)   swapdev (4696)
  cdevsw  (4663)   swplo   (4637)
  rootdev (4635)   nswap   (4698)

15.5 System Generation

System generation at a UNIX installation consists mainly of:

  • running “mkconf” with appropriate input;

  • recompiling the output files (created as “c.c” and “l.s”);

  • reloading the system with the revised object files.

This process only takes a few minutes (not the several hours of some other operating systems). Note that “bdevsw” and “cdevsw” are defined differently in “conf.c” from elsewhere, namely as a one dimensional array of pointers to functions which return integer values. This quietly ignores the fact that, for example, “rktab” is not a function, and relies on the linking program not to enquire too closely into the nature of the work which it is performing.

15.6 swap (5196)

Before plunging into all the detail of the file “bio.c”, it will be instructive as well as convenient to examine one routine which was introduced earlier, namely “swap”.

The buffer head “swbuf” was declared to control swapping input/output, which must share access to the disk with other activity. No element of “buffers” is associated with “swbuf”. Instead the core area occupied (or to be occupied) by the program serves as the data buffer.

5200:

The address of the flags in “swbuf” is transferred to the register variable “fp” for convenience and economy;

5202:

The “B_BUSY” flag is tested, and if it is on, a swap operation is already under way, so that the “B_WANTED” flag is set and the process must wait via a call on “sleep”.

Note that the code loop on lines 5202 to 5205 runs at priority level six, i.e. one higher than the disk interrupt priority.

Can you see why this is necessary? Under what conditions will the “B_BUSY” flag be set?

5206:

The flags are set to reflect:

  • “swbuf” is in use (“B_BUSY”);

  • physical i/o implying a large transfer direct to/from the user data segment
    (“B_PHYS”);

  • whether the operation is read or write. (“rdflg” is a parameter to “swap”);

5207:

The “b_dev” field is initialised. (Presumably this could have been performed once during initialisation rather than every time “swbuf” is used, i.e. in “binit”.);

5208:

“b_wcount” is initialised. Note the negative value and the effective multiplication by 32;

5210:

The hardware device controller requires a full physical address (18 bits on the PDP 11/40). The block number of a 32 word block must be converted into two parts: the low order ten bits are shifted left six places and stored as “b_addr”, and the remaining six high order bits as “b_xmem”. (On the PDP 11/40 and 11/45 only two of these bits are significant.);

5212:

A mouthful at first glance! Shift “swapdev” eight places to the right to obtain the major device number. Use the result to index “bdevsw”. From the structure thus selected, extract the strategy routine and execute it with the address of “swbuf” passed as a parameter;

5213:

Explain why this call on “spl6” is necessary;

5214:

Wait until the i/o operation is complete. Note that the first parameter to “sleep” is in effect the address of “swbuf”;

5216:

Wakeup those processes (if any) which are waiting for “swbuf”;

5218:

Reset the process or priority to zero, thus allowing any pending interrupts to “happen”;

5219:

Reset both the “B_BUSY” and “B_WANTED” flags.

15.7 Race Conditions

The code for “swap” has a number of interesting features. In particular it displays in microcosm the problems of race conditions when several processes are running together.

Consider the following scenario:

No swapping is taking place when process A initiates a swapping operation. Denoting “swbuf.b_flags” by simply “flags”, we have initially 

  flags == null

Process A is not delayed at line 5204, initiates its i/o operation and goes to sleep at line 5215. We now have 

  flags == B_BUSY | B_PHYS | rdflg

which was set at line 5206.

Suppose now while the i/o operation is proceeding, process B also initiates a swapping operation. It too begins to execute “swap”, but finds the “B_BUSY” flag set, so it sets the “B_WANTED” flag (5203) and goes to sleep also (5204). We now have 

  flags == B_BUSY | B_PHYS | rdflg | B_WANTED

At last the i/o operation completes. Process C takes the interrupt and executes “rkintr”, which calls (5471) “iodone” which calls (5301) “wakeup” to awaken process A and process B. “iodone” also sets the “B_DONE” flag and resets the “B_WANTED” flag so that 

  flags == B_BUSY | B_PHYS | rdflg | B_DONE

What happens next depends on the order in which process A and process B are reactivated. (Since they both have the same priority, “PSWP”, it is a toss-up which goes first.)

Case (a):

Process A goes first. “B_DONE” is set so no more sleeping is needed. “B_WANTED” is reset so there is no one to “wakeup”. Process A tidies up (5219), and leaves “swap” with 

  flags == B_PHYS | rdflg | B_DONE

Process B now runs and is able to initiate its i/o operation without further delay.

Case (b):

Process B goes first. It finds “B_BUSY” on, so it turns the “B_WANTED” flag back on, and goes to sleep again, leaving 

  flags == B_BUSY | B_PHYS | rdflg |
           B_DONE | B_WANTED

Process A starts again as in Case (a), but this time finds “B_WANTED” on so it must call “wakeup” (5217) in addition to its other chores. Process B finally wakes again and the whole chain completes.

Case (b) is obviously much less efficient than case (a). It would seem that a simple change to line 5215 to read 

  sleep (fp, PSWP-1);

would cost virtually nothing and ensure that Case (b) never occurred!

The necessity for the raising of processor priority at various points should be studied: for example if line 5201 was omitted and if process B had just completed line 5203 when the “i/o complete” interrupt occurred for Process A’s operation, then “iodone” would turn off “B_WANTED” and perform “wakeup” before process B went to sleep ... forever! A bad scene.

15.8 Reentrancy

Note also the assumption made above, that both process A and process B could execute “swap” simultaneously. All UNIX procedures are in general “re-entrant” (which means multiple simultaneous executions are possible). How would UNIX have to change if re-entrancy were not allowed?

15.9 For the Uninitiated

We can now return to complete an investigation started in Chapter Eight concerning “aretu” and “u.u_ssav”:

After setting “u.u_ssav” (2284), “expand” calls (2285) “xswap”, which calls (4380) “swap”, which calls (5215) “sleep”, which calls (2084) “swtch”, which resets “u.u_rsav” (2189).

Thus in fact “u.u_rsav” finally gets reset to a value appropriate to four procedure calls deeper than that for “u.u_ssav”.

15.10 Additional Reading

The article “The UNIX I/O System” by Dennis Ritchie is highly pertinent.