Disks: The Alto File System
This document describes the disk formats used in the Alto File System.
It also describes a "disk object," a Bcpl software construct that is
used to interface low-level disk drivers with packages that implement
higher-level objects, such as streams.
The primary focus of the description will be for the "standard" Alto
disks: either (1) up to 2 Diablo Model 31 disk drives or (2) one Diablo
Model 44 disk drive. The low-level drivers for these disks are called
"Bfs" (Basic File System). With minor modifications, the description
below applies to the Trident Model T80 and T300 disk drives, when
formatted for Alto file system conventions. The differences are
flagged with the string [Trident]. Low-level drivers for the Trident
disks are called "Tfs."
1. Distribution
Relocatable binary files for the BFS are kept in <Alto>BFSBrs.dm. The
sources, command files, and test program (described later in this
document) are kept in <AltoSource>BFSSources.dm Relocatable binary
files for the TFS are kept in <Alto>TFS.dm; sources are kept on
<AltoSource>TFSSources.dm.
2. File and Disk Structure
This section describes the conventions of the Alto file system. The
files AltoFileSys.D and Bfs.D contain Bcpl structure declarations that
correspond to this description ([Trident]: See also "Tfs.D").
The unit of transfer between disk and memory, and hence that of the
file system, is the disk sector. Each sector has three fields: a 2-
word header, an 8-word label, and a 256-word data page. ([Trident]:
The fields are a 2-word header, a 10-word label, and a 1024-word data
page.)
A sector is identified by a disk address; there are two kinds of disk
addresses, real and virtual. The hardware deals in real addresses,
which have a somewhat arbitrary format. An unfortunate consequence is
that the real addresses for all the pages on a disk unit are sparse in
the set of 16 bit integers. To correct this defect, virtual addresses
have been introduced. They have the property that the pages of a disk
unit which holds n pages have virtual addresses 0 ... (n-1).
Furthermore, the ordering of pages by virtual address is such that
successive pages in the virtual space are usually sequential on the
disk. As a result, assigning a sequence of pages to consecutive
virtual addresses will ensure that they can be read in as fast as
possible.
------------
Copyright Xerox Corporation 1982
Disks & Bfs April 10, 1982 2
2.1. Legal Alto Files
An Alto file is a data structure that contains two sorts of
information: some is mandatory, and is required for all legal files;
the remainder is "hints". Programs that operate on files should
endeavor to keep the hints accurate, but should never depend on the
accuracy of a hint.
A legal Alto file consists of a sequence of pages held together by a
doubly-linked list recorded in the label fields. Each label contains
the mandatory information:
The forward and backward links, recorded as real disk addresses.
A page number which gives the position of the page in the file;
pages are numbered from 0.
A count of the number of characters of data in the page (numchars).
This may range from 0 (for a completely empty page) to 512 (for a
completely full page). ([Trident]: A full page contains 2048
characters.)
A real file id, which is a three-word unique identifier for the
file. The user normally deals with virtual file ids (see the
discussion of file pointers, below), which are automatically
converted into real file ids when a label is needed.
Three bits in the file id deserve special mention:
Directory: This bit is on if the file is itself a directory file.
This information is used by the disk Scavenger when trying to re-
build a damaged disk data structure.
Random: This bit is currently unused.
NoLog: This bit is no longer used, but many existing files are
likely to have it set.
Leader Page: Page 0 of a file is called the leader page; it contains no
file data, but only a collection of file properties, all of which are
hints. The structure LD in AltoFileSys.D declares the format of a
leader page, which contains the following standard items:
The file name, a hint so that the Scavenger can enter this file in
a directory if it is not already in one.
The times for creation, last read and last write, interpreted as
follows:
A file's creation date is a stamp generated when the
information in the file is created. When a file is copied
(without modification), the creation date should be copied
with it. When a file is modified in any way (either in-place
or as a result of being overwritten by newly-created
information), a new creation date should be generated.
A file's write date is updated whenever that file is
physically written on a given file system.
Disks & Bfs April 10, 1982 3
A file's read date is updated whenever that file is
physically read from within a given file system.
A pointer to the directory in which the file is thought to be
entered (zeroes imply the system directory SysDir).
A "hint" describing the last page of the file.
A "consecutive" bit which is a hint that the pages of the file lie
at consecutive virtual disk addresses.
The changeSerial field related to version numbering: whenever a
new version of a file "foo" is made, the changeSerial field of all
other files "foo" (i.e., older versions) is incremented. Thus, a
program that wishes to be sure that it is using the most recent
version of a file can verify that changeSerial=0. If a program
keeps an FP as a hint for a file, and is concerned about the
relative position of that file in the list of version numbers, it
can also keep and verify the changeSerial entry of the file.
Version numbers have been deimplemented.
These standard items use up about 40 words of the leader page. The
remaining space is available for storing other information in blocks
which start with a one word header containing type and length fields.
A zero terminates the list. The structure FPROP in AltoFileSys.d
defines the header format. The only standard use of this facility is
to record the logical shape of the disk in the leader page of SysDir.
Data: The first data byte of a file is the first byte of page 1.
In a legal file with n pages, the label field of page i must contain:
A next link with the real disk address of page (i+1), or 0 if i=n-1.
A previous link with the real disk address of page (i-1), or 0 if
i=0.
A page number between 0 and (n-1), inclusive.
A numchars word = 512 if i<n-1, and <512 if i=n-1. The last page
must not be completely full. ([Trident]: = 2048 if i<n-1, and <2048
if i = n-1.)
A real file id which is the same for every page in the file, and
different from the real file id of any other file on the disk.
A file is addressed by an object called a file pointer (FP), which is
declared in AltoFileSys.D. A file pointer contains a virtual file id,
and also the virtual address of the leader page of the file. The low-
level disk routines construct a real file id from the virtual one when
they must deal with a disk label. Since it is possible for the user to
read a label from the disk and examine its contents, the drivers also
provides a routine which will convert the real file id in the label
into a file pointer (of course, the leader address will not be filled
in).
Note: Real disk address 0 (equal virtual disk address 0) cannot be part
of any legal Alto file because the value 0 is reserved to terminate the
forward and backward chains in sector labels. However, disk address 0
Disks & Bfs April 10, 1982 4
is used for "booting" the Alto: when the boot key is pressed when no
keyboard keys are down, sector 0 is read in as a bootstrap loader. The
normal way to make a file the "boot file" is to first create a legal
Alto file with the bootstrap loader as the first data page (page 1),
and then to copy this page (label and data) into disk sector 0. Thus
the label in sector 0 points forward to the remainder of the boot file.
2.2. Legal Alto Disks
A legal disk is one on which every page is either part of a legal file,
or free, or "permanently bad." A free page has a file id of all ones,
and the rest of its label is indeterminate. A permanently bad page has
a file id with each of the three words set to -2, and the remainder of
the label indeterminate.
2.3. Alto Directory Files
A directory is a file for associating string names and FP's. It has
the directory bit set in its file id, and has the following format
(structure DV declared in AltoFileSys.D).
It is a sequence of entries. An entry contains a header and a body.
The length field of the header tells how many words there are in the
entry, including the header. The interpretation of the body depends on
the type, recorded in the header.
dvTypeFree=0: free entry. The body is uninterpreted.
dvTypeFile=1: file entry. The body consists of a file pointer,
followed by a Bcpl string containing the name of the file. The file
name must contain only upper and lower case letters, digits, and
characters in the string "+-.!$". They must terminate with a period
(".") and not be longer than maxLengthFn characters. If there are
an odd number of bytes in the name, the "garbage byte" must be 0.
The interpretation of exclamation mark (!) is special; if a file
name ends with ! followed only by digits (and the mandatory "."),
the digits specify a file version number.
The main directory is a file with its leader page stored in the disk
page with virtual address 1. There is an entry for the main directory
in the main directory, with the name SysDir. All other directories can
be reached by starting at the main directory.
2.4. Disk Descriptor
There is a file called DiskDescriptor entered in the main directory
which contains a disk descriptor structure which describes the disk and
tells which pages are free. The disk descriptor has two parts: a 16
word header which describes the shape of the disk, and a bit table
indexed by virtual disk address. The declaration of the header
structure is in AltoFileSys.D.
The "defaultVersionsKept" entry in the DiskDescriptor records the
number of old versions of files that should be retained by the system.
If this entry is 0, no version accounting is done: new files simply
replace old ones. Version numbers have been deimplemented.
Disks & Bfs April 10, 1982 5
The entry in the disk descriptor named "freePages" is used to maintain
a count of free pages on the disk. This is a hint about a hint: it is
computed when a disk is opened by counting the bits in the bit table,
and then incrementing and decrementing as pages are released and
allocated. However the bit table is itself just a collection of hints,
as explained below.
The bit table contains a "1" corresponding to each virtual disk address
that is believed to be occupied by a file, and "0" for free addresses.
These values are, however, only hints. Programs that assign new pages
should check to be sure that a page thought to be free is indeed so by
reading the label and checking to see that it describes a free page.
(The WriteDiskPages and CreateDiskFile procedures in the disk object
perform this checking for you.)
2.5. Oversights
If the Alto file system were to be designed again, several deficiencies
could be corrected:
Directory entries and label entries should have the same concept of
file identifier. Presently, we have filePointers and fileIds.
There is no reason why the last page of a file cannot contain 512
bytes.
It is unfortunate that the disk controller will not check an entry
of 0 in a label, because these values often arise (numChars of the
last page, page number of the leader page). Another don't care
value should be chosen: not a legal disk address; with enough high
order bits so that it will check numChars and page number fields.
The value used to terminate the chain of disk addresses stored in
the labels should not be a legal disk address. (It should also not
be zero, so that it may be checked.) If it is a legal address, and
if you try to run the disk at full speed using the trick of pointing
page i's label at page i+1's disk address in the command block, the
disk will try to read the page at the legal disk address represented
by the chain terminator. Only when this results in an error is end
of file detected. A terminator of zero has the undesirable property
that a seek to track 0 occurs whenever a chain runs into end-of-
file.
3. The Disk Object
In order to facilitate the interface between various low-level disk
drivers and higher-level software, we define a "disk object." A small
data structure defines a number of generic operations on a disk -- the
structure DSK is defined in "Disks.D." Each procedure takes the disk
structure as its first argument:
ActOnDiskPages: Used to read and write the data fields of pages of
an existing file.
WriteDiskPages: Used to read and write data fields of the pages of a
file, and to extend the file if needed.
Disks & Bfs April 10, 1982 6
DeleteDiskPages: Used to delete pages from the end of a file.
CreateDiskFile: Used to create a new disk file, and to build the
leader page correctly.
AssignDiskPage: Used to find a free disk page and return its virtual
disk address.
ReleaseDiskPage: Used to release a virtual disk address no longer
needed.
VirtualDiskDA: Converts a real disk address into a virtual disk
address.
RealDiskDA: Converts a virtual disk address into a real disk
address.
InitializeDiskCBZ: Initializes a Command Buffer Zone (CBZ) for
managing disk transfers.
DoDiskCommand: Queues a Command Buffer (CB) to initiate a one-page
transfer.
GetDiskCb: Obtains another CB, possibly waiting for an earlier
transfer to complete.
CloseDisk: Destroys the disk object.
In addition, there are several standard data entries in the DSK object:
fpSysDir: Pointer to the FP for the directory on the disk. (This
always has a constant format -- see discussion above.)
fpDiskDescriptor: Pointer to the FP for the file "DiskDescriptor" on
the disk.
fpWorkingDir: Pointer to the FP to use as the "working directory" on
this disk. This is usually the same as fpSysDir.
nameWorkingDir: Pointer to a Bcpl string that contains the name of
the working directory.
lnPageSize: This is the log (base 2) of the number of words in a
data page on this disk.
driveNumber: This entry identifies the drive number that this DSK
structure describes.
retryCount: This value gives the number of times the disk routines
should retry an operation before declaring it an error.
totalErrors: This value gives a cumulative count of the number of
disk errors encountered.
diskKd: This entry points to a copy of the DiskDescriptor in memory.
Because the bit table can get quite large, only the header needs to
be in memory. This header can be used, for example, to compute the
capacity of the disk.
Disks & Bfs April 10, 1982 7
lengthCBZ, lengthCB: The fixed overhead for a CBZ and the number of
additional words required per CB.
In addition to this standard information, a particular implementation
of a disk class may include other information in the structure.
4. Data Structures
The following data structures are part of the interface between the
user and the disk class routines:
pageNumber: as defined in the previous section. The page number is
represented by an integer.
DAs: a vector indexed by page number in which the ith entry contains
the virtual disk address of page i of the file, or one of two special
values (which are declared as manifest constants in Disks.D):
eofDA: this page is beyond the current end of the file;
fillInDA: the address of this page is not known.
Note that a particular call on the file system will only reference
certain elements of this vector, and the others do not have to exist.
Thus, reading page i will cause references only to DAs!i and DAs!(i+1),
so the user can have a two-word vector v to hold these quantities, and
pass v-i to the file system as DAs.
CAs: a vector indexed by page number in which the ith entry contains
the core address to or from which page i should be transfered. The
note for DAs applies here also.
fp (or filePtr): file pointer, described above. In most cases, the
leader page address is not used.
action: a magic number which specifies what the disk should do.
Possible values are declared as manifest constants in Disks.D:
DCreadD: check the header and label, read the data;
DCreadLD: check the header, read the label and data;
DCreadHLD: read the header, label, and data;
DCwriteD: check the header and label, write the data;
DCwriteLD: check the header, write the label and data;
DCwriteHLD: write the header, label, and data;
DCseekOnly: just seek to the specified track
DCdoNothing:
A particular implementation of the disk class may also make other
operations available by defining additional magic numbers.
5. Higher-level Subroutines
There are two high-level calls on the basic file system:
Disks & Bfs April 10, 1982 8
pageNumber = ActOnDiskPages(disk, CAs, DAs, filePtr, firstPage,
lastPage, action, lvNumChars, lastAction, fixedCA, cleanupRoutine,
lvErrorRoutine, returnOnCheckError, hintLastPage).
Parameters beyond "action" are optional and may be defaulted by
omitting them or making them 0.
Here firstPage and lastPage are the page numbers of the first and last
pages to be acted on (i.e. read or written, in normal use). This
routine does the specified action on each page and returns the page
number of the last page successfully acted on. This may be less than
lastPage if the file turns out to have fewer pages. DAs!firstPage must
contain a disk address, but any of DAs!(firstPage+1) through
DAs!(lastPage+1) may be fillInDA, in which case it will be replaced
with the actual disk address, as determined from the chain when the
labels are read. Note that the routine will fill in DAs!(lastPage+1),
so this word must exist.
The value of the numChars field in the label of the last page acted on
will be left in rv lvNumChars. If lastAction is supplied, it will be
used as the action for lastPage instead of action. If CAs eq 0,
fixedCA is used as the core address for all the data transfers. If
cleanupRoutine is supplied, it is called after the successful
completion of each disk command, as described below under "Lower-level
disk access". (Note: providing a cleanup routine defeats the automatic
filling in of disk addresses in DAs).
Disk transfers that generate errors are retried several times and then
the error routine is called with
rv lvErrorRoutine(lvErrorRoutine, cb, errorCode)
In other words, lvErrorRoutine is the address of a word which contains
the (address of the) routine to be called when there is an error. The
errorCode tells what kind of error it was; the standard error codes are
tabulated in a later section. The cb is the control block which caused
the error; its format depends on the particular implementation of the
drivers (Bfs: the structure CB in Bfs.D).
The intended use of lvErrorRoutine is this. A disk stream contains a
cell A, in a known place in the stream structure, which contains the
address of a routine which fields disk errors. The address of A is
passed as lvErrorRoutine. When the error routine is called, it gets
the address of A as a parameter, and by subtracting the known position
of A in the disk stream structure, it can obtain the address of the
stream structure, and thus determine which stream caused the error.
The default value of returnOnCheckError is false. If
returnOnCheckError is true and an error is encountered, ActOnDiskPages
will not retry a check error and then report an error. Instead, it
will return -(#100+i), where i is the page number of the last page
successfully transferred. This feature allows ActOnDiskPages to be
used when the user it not sure whether the disk address he has is
correct. It is used by the disk stream and directory routines which
take hints; they try to read from the page addressed by the hint with
returnOnCheckError true, and if they get a normal return they know that
the hint was good. On the other hand, if it was not good, they will
get the abnormal return just described, and can proceed to try again in
a more conservative way.
Disks & Bfs April 10, 1982 9
The hintLastPage argument, if supplied, indicates the page number of
what the caller believes to be the last page of the file (presumably
obtained from the hint in the leader page). If the hint is correct,
ActOnDiskPages will ensure that the disk controller does not chain past
the end of the file and seek to cylinder zero (as described earlier
under "Oversights"). If the hint is incorrect, the operation will
still be performed correctly, but perhaps with a loss in performance.
Note that the label is not rewritten by DCwriteD, so that the number of
characters per page will not change. If you need to change the label,
you should use WriteDiskPages unless you know what you are doing.
ActOnDiskPages can be used to both read and write a file as long as the
length of the file does not have to change. If it does, you must use
WriteDiskPages.
pageNumber = WriteDiskPages(disk, CAs, DAs, filePtr, firstPage,
lastPage, lastAction, lvNumChars, lastNumChars, fixedCA, nil,
lvErrorRoutine, nil, hintLastPage).
Arguments beyond lastPage are optional and may be defaulted by omitting
them or making them 0 (but lastNumChars is not defaulted if it is 0).
This routine writes the specified pages from CAs (or from fixedCA if
CAs is 0, as for ActOnDiskPages). It fills in DAs entries in the same
way as ActOnDiskPages, and also allocates enough new pages to complete
the specified write. The numChars field in the label of the last page
will be set to lastNumChars (which defaults to 512 [Trident]: 2048).
It is generally necessary that DAs!firstPage contain a disk address.
The only situation in which it is permissible for DAs!firstPage to
contain fillInDA is when firstPage is zero and no pages of the file yet
exist on the disk (i.e., when creating page zero of a new file).
In most cases, DAs!(firstPage-1) should have the value which you want
written into the backward chain pointer for firstPage, since this value
is needed whenever the label for firstPage needs to be rewritten. The
only case in which it doesn't need to be rewritten is when the page is
already allocated, the next page is not being allocated, and the
numChars field is not changing.
If lastPage already exists:
1) the old value of the numChars field of its label is left in rv
lvNumChars.
2) if lastAction is supplied, it is applied to lastPage instead of
DCwriteD. It defaults to DCwriteD.
WriteDiskPages handles one special case to help in "renaming" files,
i.e. in changing the FP (usually the serial number) of all the pages of
a file. To do this, use ActOnDiskPages to read a number of pages of
the file into memory and to build a DAs array of valid disk addresses.
Then a call to WriteDiskPages with lastAction=-1 will write labels and
data for pages firstPage through lastPage (DAs!(firstPage-1) and
DAs!(lastPage+1) are of course used in this writing process). The
numChars field of the label on the last page is set to lastNumChars.
To use this facility, the entire DAs array must be valid, i.e. no
entries may be fillInDA.
Disks & Bfs April 10, 1982 10
In addition to these two routines, there are two others which provide
more specialized services:
CreateDiskFile(disk, name, filePtr, dirFilePtr, word1 [0], useOldFp
[false], pageBuf[0])
Creates a new disk file and writes its leader page. It returns the
serial number and leader disk address in the FP structure filePtr. A
newly created file has one data page (page 1) with numChars eq 0.
The arguments beyond filePtr are optional, and have the following
significance:
If dirFilePtr is supplied, it should be a file pointer to the
directory which owns the file. This file pointer is written into
the leader page, and is used by the disk Scavenger to put the file
back into the directory if it becomes lost. It defaults to the root
directory, SysDir.
The value of word1 is "or"ed into the filePtr>>FP.serialNumber.word1
portion of the file pointer. This allows the directory and random
bits to be set in the file id.
If useOldFp is true, then filePtr already points to a legal file;
the purpose of calling CreateDiskFile is to re-write all the labels
of the existing file with the new serial number, and to re-
initialize the leader page. The data contents of the original file
are lost. Note that this process effectively "deletes" the file
described by filePtr when CreateDiskFile is called, and makes a new
file; the FP for the new file is returned in filePtr.
If pageBuf is supplied, it is written on the leader page of the new
file after setting the creation date and directory FP hint (if
supplied). If pageBuf is omitted, a minimal leader page is created.
DeleteDiskPages(disk, CA, firstDA, filePtr, firstPage, newFp,
hintLastPage)
Arguments beyond firstPage are optional. Deletes the pages of a file,
starting with the page whose number is firstPage and whose disk address
is firstDA. CA is a page-sized buffer which is clobbered by the
routine. hintLastPage is as described under ActOnDiskPages.
If newFp is supplied and nonzero, it (rather than freePageFp) is
installed as the FP of the file, and the pages are not deallocated.
6. Allocating Disk Space
The disk class also contains routines for allocating space and for
converting between virtual and real disk addresses. In most cases,
users need not call these routines directly, as the four routines given
above (ActOnDiskPages, WriteDiskPages, DeleteDiskPages, CreateDiskFile)
manage disk addresses and disk space internally.
AssignDiskPage(disk, virtualDA, nil) returns the virtual disk address
of the first free page following virtualDA, according to the bit table,
Disks & Bfs April 10, 1982 11
and sets the corresponding bit. It does not do any checking that the
page is actually free (but WriteDiskPages does). If there are no free
pages it returns -1. If it is called with three arguments, it returns
true if (virtualDA+1) is available without assigning it.
If virtualDA is eofDA, AssignDiskPage makes a free-choice assignment.
The disk object remembers the virtual DA of the last page assigned and
uses it as the first page to attempt to assign next time AssignDiskPage
is called with a virtualDA of eofDA. This means that you can force a
file to be created starting at a particular virtual address by means of
the following strategy:
ReleaseDiskPage(disk, AssignDiskPage(disk, desiredVDA-1))
CreateDiskFile(disk, ...) // or whatever (e.g., OpenFile)
ReleaseDiskPage(disk, virtualDA) marks the page as free in the bit
table. It does not write anything on the disk (but DeleteDiskPages
does).
VirtualDiskDA(disk, lvRealDA) returns the virtual disk address, given a
real disk address in rv lvRealDA. (The address, lvRealDA, is passed
because a real disk address may occupy more than 1 word.) This
procedure returns eofDA if the real disk address is zero (end-of-file),
and fillInDA if the real disk address does not correspond to a legal
virtual disk address in this file system.
RealDiskDA(disk, virtualDA, lvRealDA) computes the real disk address
and stores it in rv lvRealDA. The function returns true if the virtual
disk address is legal, i.e. within the bounds of disk addresses for the
given "disk." Otherwise, it returns false.
7. Lower-level Disk Access
The transfer routines described previously have the property that all
disk activity occurs during calls to the routines; the routines wait
for the requested disk transfers to complete before returning.
Consequently, disk transfers cannot conveniently be overlapped with
computation, and the number of pages transferred consecutively at full
disk speed is generally limited by the number of buffers that a caller
is able to supply in a single call.
It is also possible to use the disk routines at a lower level in order
to overlap transfers with computation and to transfer pages at the full
speed of the disk (assuming the file is consecutively allocated on the
disk and the amount of computation per page is kept relatively small).
The necessary generic disk operations and other information are
available to permit callers to operate the low-level disk routines in a
device-independent fashion for most applications.
This level makes used of a Command Block Zone (CBZ), part of whose
structure is public and defined in Disks.d, and the rest of which is
private to the implementation. The general idea is that a CBZ is set
up with empty disk command blocks in it. A free block is obtained from
the CBZ with GetDiskCb and sent to the disk with DoDiskCommand. When
it is sent to the disk, it is also put on the queue which GetDiskCb
uses, but GetDiskCb waits until the disk is done with the command
before returning it, and also checks for errors.
Disks & Bfs April 10, 1982 12
If you plan to use these routines, read the code for ActOnDiskPages to
find out how they are intended to be called. An example of use of
these routines in a disk-independent fashion (i.e., using only the
public definitions in Disks.d) may be found in the DiskStreamsScan
module of the Operating System. Only in unusual applications should it
be necessary to make use of the implementation-dependent information in
Bfs.d or Tfs.d.
InitializeDiskCBZ(disk, cbz, firstPage, length, retry, lvErrorRoutine).
CBZ is the address of a block of length words which can be used to
store CBs. It takes at least three CBs to run the disk at full speed;
the disk object contains the values DSK.lengthCBZ (fixed overhead) and
DSK.lengthCB (size of each command block) which may be used to compute
the required length (that is, length should be at least
lengthCBZ+3*lengthCB). FirstPage is used to initialize the currentPage
field of the cbz. Retry is a label used for an error return, as
described below. lvErrorRoutine is an error routine for unrecoverable
errors, described below; it defaults to a routine that simply invokes
SysErr. The arguments after firstPage can be omitted if an existing
CBZ is being reinitialized, and they will remain unchanged from the
previous initialization.
cb = GetDiskCb(disk, cbz, dontClear[false], returnIfNoCB[false])
returns the next CB for the CBZ. If the next CB is empty (i.e., it has
never been passed to DoDiskCommand), GetDiskCb simply zeroes it and
returns it. However, if the next CB is still on the disk command
queue, GetDiskCb waits until the disk has finished with it. Before
returning a CB, GetDiskCb checks for errors, and handles them as
described below. If there is no error, GetDiskCb updates the nextDA
and currentNumChars cells in the CBZ, then calls
cbz>>CBZ.cleanupRoutine(disk, cb, cbz). Next, unless dontClear is
true, the CB is zeroed. Finally, the CB is returned as the value of
GetDiskCb. If returnIfNoCB is true, GetDiskCb returns zero if there
are no CBs in the CBZ or the next CB is still on the disk command
queue.
If the next CB has suffered an error, then GetDiskCb instead takes the
following actions. First it increments cbz>>CBZ.errorCount. If this
number is ge the value disk>>DSK.retryCount, GetDiskCb calls the error
routine which was passed to InitializeDiskCBZ; the way this is done is
explained in the description of ActOnDiskPages above. (If the error
routine returns, GetDiskCb will proceed as if an error hadn't
occurred.) Otherwise, after doing a restore on the disk if errorCount
ge disk>>DSK.retryCount/2, it reinitializes the CBZ with firstPage
equal to the page with the error, and returns to cbz>>CBZ.retry (which
was initialized by InitializeDiskCBZ) instead of returning normally.
The idea is that the code following the retry label will retry all the
incomplete commands, starting with the one whose page number is
cbz>>CBZ.currentPage and whose disk address is cbz>>CBZ.errorDA.
DoDiskCommand(disk, cb, CA, DA, filePtr, pageNumber, action, nextCb)
Constructs a disk command in cb with data address CA, virtual disk
address DA, serial and version number taken from the virtual file id in
filePtr, page number taken from pageNumber, and disk command specified
by action. The nextCb argument is optional; if supplied and nonzero,
DoDiskCommand will "chain" the current CB's label address to nextCb, in
such a way that the DL.next word will fall into nextCb>>CB.diskAddress.
DoDiskCommand expects the cb to be zeroed, except that the following
Disks & Bfs April 10, 1982 13
fields may be preset; if they are zero the indicated default is
supplied:
labelAddress lv cb>>CB.label
numChars 0
If DA eq fillInDA, the real disk address in the command is not set (the
caller should have either set it explicitly or passed the CB as the
nextCb argument for a previous command). Actions are checked for
legality.
The public cells in the CBZ most likely to be of interest are the
following:
client: information of the caller's choosing (e.g., a pointer to a
related higher-level data structure such as a stream.)
cleanupRoutine: the cleanup routine called by GetDiskCb (defaulted
to Noop by InitializeDiskCBZ).
currentPage: set to the firstPage argument of InitializeDiskCBZ and
not touched by the other routines. (Note, however, that GetDiskCb
calls InitializeDiskCBZ when a retry is about to occur, so when
control arrives at the retry label, currentPage will be set to the
page number of the command that suffered the error.)
errorDA: set by GetDiskCb to the virtual disk address of the command
that suffered an error.
nextDA: set by GetDiskCb to the virtual disk address of the page
following the one whose CB is being returned. (This information is
obtained from the next pointer in the current page's label. Note
that errorDA and nextDA are actually the same cell, but they are
used in non-conflicting circumstances.)
currentNumChars: set by GetDiskCb to the numChars of the page whose
CB is being returned.
head: points to the first CB on GetDiskCb's queue; contains zero if
the queue is empty.
8. Error Codes
The following errors are generated by the BFS. Similar errors are
generated by other instances of a disk object.
1101 unrecoverable disk error
1102 disk full
1103 bad disk action
1104 control block queues fouled up
1105 attempt to create a file without creation ability
1106 can't create an essential file during NewDisk
1107 bit table problem during NewDisk
1108 attempt to access nonexistant bit table page
Disks & Bfs April 10, 1982 14
9. Implementation -- Bfs
The implementation expects a structure BFSDSK to be passed as the
"disk" argument to the routines. The initial portion of this structure
is the standard DSK structure followed by a copy of the DiskDescriptor
header and finally some private instance data for the disk in use.
(Note: The Alto operating system maintains a static sysDisk that points
to such a structure for disk drive 0.)
Bfs ("Basic File System") is the name for a package of routines that
implement the disk class for the standard Alto disks (either Diablo
Model 31 drives or a single Diablo Model 44 drive). The definitions
(in addition to those in AltoFileSys.D and Disks.D) are contained in
Bfs.D. The code comes in two "levels:" a "base" for reading and
writing existing files (implements ActOnDiskPages, RealDiskDA and
VirtualDiskDA only); and a "write" level for creating, deleting,
lengthening and shortening files (implements WriteDiskPages,
CreateDiskFile, DeleteDiskPages, AssignDiskPage, ReleaseDiskPage). The
source files BfsBase.Bcpl, Dvec.Bcpl and BfsMl.Asm comprise the base
level; files BfsWrite.Bcpl BfsCreate.bcpl, BfsClose.bcpl, and
BfsDDMgr.bcpl implement the write level.
BfsMakeFpFromLabel(fp, la) constructs a virtual file id in the file
pointer fp from the real file id in the label la.
disk = BFSInit(diskZone, allocate[false], driveNumber[0], ddMgr[0],
freshDisk[false], tempZone[diskZone]) returns a disk object for
driveNumber or zero. The permanent data structures for the disk are
allocated from diskZone; temporary free storage needed during the
initialization process is allocated from tempZone. If allocate is
true, the machinery for allocating and deallocating disk space is
enabled. If it is enabled, a small DDMgr object and a 256 word buffer
will be extracted from diskZone in order to buffer the bit table. A
single DDMgr, created by calling 'ddMgr = CreateDDMgr(zone)', can
manage both disks. If freshDisk is true, BFSInit does not attempt to
open and read the DiskDescriptor file. This operation is essential for
creating a virgin file system.
success = BFSNewDisk(zone, driveNum[0], nDisks[number spinning],
nTracks[physical size], dirLen[3000], nSectors[physical size]) creates
a virgin Alto file system on the specified drive and returns true if
successful. The zone must be capable of supplying about 1000 words of
storage. The logical size of the file system may be different from the
physical size of driveNum: it may span both disks (a 'double-disk file
system'), or it may occupy fewer tracks (a model 44 used as a model
31). The length in words of SysDir, the master directory, is specified
by dirLen. Some machines that emulate Altos implement 14 sectors per
track.
BFSExtendDisk(zone, disk, nDisks, nTracks) extends (i.e. adds pages to)
the filesystem on 'disk'. Presumably 'nDisks' or 'nTracks' or both is
bigger than the corresponding parameters currently in disk. A single
model 31 may be extended to a double model 31 or a single model 44 or a
double model 44, and a single model 44 may be extended to a double
model 44. The zone must be capable of supplying about 750 words of
storage.
0 = BFSClose(disk, dontFree[false]) destroys the disk object in an
Disks & Bfs April 10, 1982 15
orderly way. If dontFree is true, the ddMgr for the disk is not
destroyed; presumably it is still in use by the other disk. (Note that
this procedure is the one invoked by the CloseDisk generic operation.)
BFSWriteDiskDescriptor(disk) insures that any important state saved in
memory is correctly written on the disk.
virtualDA = BFSFindHole(disk, nPages) attempts to find a contiguous
hole nPages long in disk. It returns the virtual disk address of the
first page of a hole if successful, else -1.
BFSTryDisk(drive, track, sector[0]) returns true if a seek command to
the specified track on the specified drive is successful. Note that
the drive argument can contain an imbedded partition number. Seeks to
track zero will fail if the drive is not on line. Seeks to track
BFS31NTracks+1 will fail if the drive is a model 31.
10. Implementation -- Tfs
Operation and implementation of the Trident T80 disks is described in
separate documentation under the heading "TFS/TFU" in Alto Subsystems
documentation.
11. BFSTest
BFSTest is the test and utility program for the Basic File System. It
performs many of the same functions as TFU (in fact much of its code is
lifted from TFU), except that commands which are better provided by
other subsystems such as the Executive (copy, rename, delete, etc.) are
omitted. It has a conventional command scanner and implements the
following commands.
ERASE formats one or more disks as an Alto file system. It asks you to
specify the number of disks, cylinders and sectors. Any sectors
marked "incorrigable" (by the CERTIFY command, below) are not
included in the file system and will never again cause trouble
unless the disk is erased with DiEx. The OS erase command also
preserves this bad spot information.
EXERCISE creates, deletes, reads, writes and positions files the same
way that normal programs do, and checks the results which normal
programs do not do. These high-level operations cause patterns of
disk commands which are quite different from those generated by
lower-level tests such as DiEx.
Exercise assumes that a file system exists on DP0 (and perhaps
extends on to DP1). It creates as many test files (named
Test.001, Test.002, ...) as will fit in the file system, filling
each file with a carefully chosen test pattern. When it is done,
it deletes all of its files. One 'pass' consists of stepping
through the test files, performing a randomly chosen operation on
the file, and checking the results. The duration and throughness
of a pass depends on the amount of free space on the disks.
Disks & Bfs April 10, 1982 16
Ideally, the disk(s) under test have just been erased with the
ERASE command, below.
While running, exercise looks for commands from the keyboard. The
current commands are:
Q Quit Delete all test files and stop.
S StopOnError Wait until a character is typed.
All test files are 100 pages long. Each page of a file has the
page number in its first and last words and a data pattern in the
middle 254 words. The data pattern is constant throughout a file,
consisting of a single one-bit in a word of zeros or a single
zero-bit in a word of ones. Files are read and written with
ReadBlock and WriteBlock using buffers whose lengths are not
multiples of the page size. The operations are:
Write Write the entire file with the data pattern.
Read Read the entire file checking the data pattern.
Delete Delete the file, create it again and then write
it.
Copy Copy the file to some other randomly chosen
file. If both disks are being tested, one
third of the time pick a destination file on
the other disk.
Position Position to twenty randomly chosen pages in the
file. Check that the first word of the page is
indeed the page number. One third of the time
dirty the stream by writing the page number in
the last word of the page.
CERTIFY tests one or more disks for bad spots and marks such pages
"incorrigable" so that they will not be included in subsequent
file systems. Ideally, a disk should be certified before being
used. Certify can be stopped at any time by hitting any key.
A bad spot is any sector which gives three or more checksum
errors. If the Scavenger encounters a bad spot, it will also mark
the sector incorrigable. Alto and Dorado disks almost never have
bad spots; but Dolphin disks typically have a few, so CERTIFYing
is a must for trouble-free operation. Note that bad spot
information will be lost if a certified pack is written by
COPYDISK or DIEX.
CREATEFILE attempts to create a contiguous file of a specified size.
If it can't, it creates a file with a minimum number of page runs.
PARTITION allows you to set the disk partition on which BFSTest will
operate. This command is only available on Dolphins and Dorados.
A thorough, high-level "acceptance test" for the disk subsystem of an
Alto or Alto-emulating machine (i.e. a Dolphin or Dorado) consists of
at least 100 passes of CERTIFY with less than 5 bad spots (any bad
spots on cylinder 0 are unacceptable), followed by ERASE, followed by
at least 10 passes of EXERCISE with no errors.