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 , useOldFp [false], pageBuf) 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, ddMgr, 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, nDisks[number spinning], nTracks[physical size], dirLen, 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) 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.