17 Buffer Manipulation

In this chapter we look at the file “bio.c” in detail. It contains most of the basic routines used to manipulate buffer headers and buffers (4535, 4720).

Individual buffer headers are tagged by a device number “b_dev”, (4527) and a block number “b_blkno”, (4531). (Note the way in which the latter is declared as an unsigned integer.)

Buffer headers may be linked simultaneously into two lists:

the “b”-lists: are lists, one per device controller, which link together buffers associated with that device type;
the “av”-list: is a list of buffers which may be detached from their current use and converted to an alternate use.

Both the “av”-list and the various “b”-lists are doubly linked to facilitate insertion and deletion at any point.

17.1 Flags

If a buffer is withdrawn temporarily from the “av”-list, then its “B_BUSY” flag is raised.

If the contents of a buffer correctly reflect the information that is or should be stored on disk, then the “B_DONE” flag is raised.

If the “B_DELWRI” flag is raised, the contents of the buffer are more up to date than the contents of the corresponding disk block, and hence the buffer must be written out before it can be reassigned.

17.2 A Cache-like Memory

It will be seen that the large buffers in UNIX are manipulated in a way which is analogous to the operation of hardware cache attached to the main memory of a computer e.g. the PDP11/70.

Buffers are not assigned to any particular program or file, except for very short intervals at a time. In this way a relatively small number of buffers can be shared effectively amongst a large number of programs and files.

Information is left in the buffers until the buffer is needed i.e. immediate “write through” is avoided if only part of the buffer has recently been changed. Programs which read or write records which are small compared with the buffer size are then not penalised unduly.

Finally when programs are terminated and files are closed, the problems of ensuring that the program’s buffers are flushed properly (problems which have plagued other operating systems) have largely disappeared.

There is one area of practical concern: if the decision “when to write” is left to the operating system alone, then some buffers may not be written out for a very long time. Accordingly there is a utility program which runs twice per minute and forces all such buffers to be written out unconditionally. This limits the likely amount of damage that a sudden system crash may cause.

17.3 clrbuf (5038)

This routine zeros out the first 256 words (512 bytes) of the buffer. Note that the parameter passed to “clrbuf” is the address of the buffer header. “clrbuf” is called by “alloc” (6982).

17.4 incore (4899)

This routine searches for a buffer that is already assigned to a particular (device, block number) pair. It searches the circular “b”-list whose head is the “devtab” structure for the device type. If a buffer is found, the address of the buffer header is returned. “incore” is called by “breada” (4780, 4788).

17.5 getblk (4921)

This routine performs the same search as “incore” but goes further in that if the initial search is unsuccessful, a buffer is allocated from the “av”-list (available list).

By a call on “notavail” (4999), the buffer is removed from the “av”-list and flagged as “B_BUSY”.

“getblk” is more suspicious of its parameters than “incore”. It is called by

  exec   (3040)        writei (6304)
  exit   (3237)        iinit  (6928)
  bread  (4758)        alloc  (6981)
  breada (4781,4789)   free   (7016)
  smount (6123)        update (7216)

4940:

At this point the required buffer has been located by searching the “b”-list. Either it is “B_BUSY” in which case a “sleep” must be taken (4943), or else it is appropriated (4948);

4953:

If the required buffer has not been located, and if the “av”-list is empty, set the “B_WANTED” flag for the “av”-list and go to “sleep” (4955);

4960:

If the “av”-list is not empty, select the first member, and if it represents a “delayed write” arrange to have it written out asynchronously (4962);

4966:

“B_RELOC” is a relic! (See 4583);

4967:

The code from here until 4973 unconditionally removes the buffer from the “b”-list for its current device type and reinserts it into the bn-list for the new device type. Since this will frequently be a “no-op” i.e. the new and old device type will be the same, it would seem desirable to insert a test

 if (bp->b_dev == dev)

before executing lines 4967 to 4974.

Note the special handling for calls where
“dev == NODEV” (–1). (Such calls incidentally are made without a second parameter - tut! tut! See e.g. 3040.)

“bfreelist” serves as the “devtab” structure for the “b”-list for “NODEV”.

17.6 brelse (4869)

This procedure takes the buffer passed as a parameter and links it back into the “av”-list.

Any process which is either waiting for the particular buffer or any available buffer is woken up.

Note however that since both “sleeps” (4943, 4955) are at the same priority, if two processes are waiting – one for the particular buffer and one for any buffer – it will be a toss-up which will get it.

By giving the first priority over the second (e.g. by biasing by one) the race should be resolved more satisfactorily. The disadvantage of such a change might be that it could lead to a deadlock situation in certain rather peculiar circumstances.

If an error has occurred e.g. upon reading information into the buffer the information in the buffer may be incorrect. The assignment on line 4883 ensures that the information in the buffer will not be mistakenly retrieved subsequently. The “B_ERROR” flag is set e.g. by “rkstrategy” (5403) and “rkintr” (5467).

To see how this could occur, consider what happens to a buffer when a disk i/o operation is completed:

5471

“rkintr” calls “iodone”;

5026

“iodone” sets the “B_DONE” flag;

5028

“iodone” calls “brelse”;

4387

“brelse” resets the “B_WANTED”, “B_BUSY” and “B_ASYNC” flags but not the “B_DONE” flag;

. . . . . . . . . . . .

4948

“getblk” finds the buffer and calls “notavail”;

5010

“notavail” sets the “B_BUSY” flag;

4759

“bread” (which called “getblk”) finds the “B_DONE” flag set and exits.

Note that buffer headers are removed from the “av”-list by “notavail” and are returned by “brelse”. Buffer headers are moved from one “b”-list to another by “getblk”.

17.7 binit (5055)

This procedure is called by “main” (1614) to initialise the buffer pool. Empty, doubly linked circular lists are set up:

for the “av”-list (“bfreelist” is head);
the “b”-list for null devices (“dev == NODEV”) (“bfreelist” is again head);
a “b”-list for each major device type.

For each buffer:

the buffer header is linked into the “b”-list for the device “NODEV” (–1);
the address of the buffer is set in the header (5067);
the buffer flags are set as “B_BUSY” (this doesn’t seem to be really necessary) (5072);
the buffer header is linked into the “av”-list by a call on “brelse” (5073);

The number of block devices is recorded as “nblkdev”. This is used for checking values for “dev” in “getblk” (4927), “getmdev” (6192) and “openi” (6720). Inspection of “bdevsw” (4656) shows that “nblkdev” will be set to eight whereas the value one is what is really required.

This result could be obtained by “editing” as follows:

    /5084/m/5081/ "nblkdev=i;
    /5083/m/5077/ "i++

17.8 bread (4754)

This is the standard procedure for reading from block devices. It is called by:

  wait   (3282)      iinit  (6927)
  breada (4799)      alloc  (6973)
  statl  (6051)      ialloc (7097)
  smount (6116)      iget   (7319)
  readi  (6258)      iupdat (7386)
  writei (6305)      itrunc (7426, 7431)
  bmap   (6472,6488) namei  (7625)

“getblk” finds a buffer. If the “B_DONE” flag is set no i/o is needed.

17.9 breada (4773)

This procedure has an additional parameter, as compared with “bread”. It is called only by “readi” (6256).

4780:

Check if the desired block has already been assigned to a buffer. (It may not yet be available, but at least is it there?);

4781:

If not initiate the necessary read operation but don’t wait for it to finish;

4788:

Look around for the “read ahead” block. If it is not there, allocate a buffer (4789) but release it (4791) if the buffer is already ready;

4793:

The “read ahead” block is not ready, so initiate an asynchronous read operation;

4798:

If a buffer was assigned to the current block call “bread” to wrap it up, else...

4800:

Wait for the completion of the operation which was started at line 4785.

17.10 bwrite (4809)

This is the standard procedure for writing to block devices. It is called by “exit” (3239), “bawrite” (4863), “getblk” (4963), “bflush” (5241), “free” (7021), “update” (7221) and “iupdat” (7400). N.B. “writei” calls “bawrite” (6310)!

4820:

If the “B_ASYNC” flag is not set, the procedure does not return until the i/o operation is completed;

4823:

If the “B_ASYNC” is set, but “B DELWRI” was not set (note “flag” is set at line 4816) call “geterror” (5336) to check on the error flag. (If “B_DELWRI” was set, and there is an error, sending the error indication to the right process is “too hard.”). The call (4824) on “geterror” will only report errors related to the initiation of the write operation.

17.11 bawrite (4856)

This procedure is called by “writei” (6310) and “bdwrite” (4845). “writei” calls either “bawrite” or “bdwrite” depending on whether the block to be written has been wholly or partially filled.

17.12 bdwrite (4836)

This procedure is called by “writei” (6311) and “bmap” (6443, 6449, 6485, 6500 and 6501 !).

4844:

Don’t delay the write if the device is a magnetic tape drive ... keep everything in order;

4847:

Set the “B_DONE”, “B_DELWRI” flags and call “brelse” to link the buffer into the “av”-list.

17.13 bflush (5229)

This procedure is called by “update” (7201), which is called by “panic” (2420), “sync” (3489) and “sumount” (6150).

“bflush” searches the “av”-list for “delayed write” blocks and forces them to be written out asynchronously.

Note that as “notavail” adjusts the links of the “av”-list, the search (which runs at processor priority six) is reinitiated after each “delayed write” block is encountered.

Note also that since it happens that “bflush” is only called by “update” with “dev” equal to “NODEV”, line 5238, in particular, could be simplified.

17.14 physio (5259)

This routine is called to handle “raw” input/output i.e. operations which ignore the normal 512 character block size.

“physio” is called by “rkread” (5476) and “rkwrite” (5483) which appear as entries in the array “cdevsw” (4684)

“Raw i/o” is not an essential feature of UNIX. For disk devices it is used mainly for copying whole disks and checking the integrity of the file system as a whole (see e.g. ICHECK (VIII) in the UPM), where it is convenient to read whole tracks, rather than single blocks, at a time.

Note the declaration of “strat” (5261). Since the actual parameter used e.g. “rkstrategy” (5389) does not return any value, is this form of declaration really necessary? Section Four

Section Four is concerned with files and file systems.

A file system is a set of files and associated tables and directories organised onto a single storage device such as a disk pack.

This section covers the means of creating and accessing files, locating files via directories, and organising and maintaining file systems.

It also includes the code for an exotic breed of file called a “pipe”.