DIRECTORY Rope USING[ ROPE ]; NewFile: CEDAR DEFINITIONS = BEGIN RC: TYPE = { -- extension of "Reason" for internal use. ok, wentOffline, -- volume is not accessible (some drive has been offline) inconsistent, -- the volume's (or file's) permanent data structures look inconsistent software, -- i.e. label-check. The page on disk is not the one the software expected. hardware, -- the disk hardware/microcode detected a hard disk error unknownFile, -- the file does not exist (possibly deleted since it was opened) unknownPage, -- the page would be beyond the end of the file volumeFull, -- the volume has no free pages (and one is needed!) fragmented, -- the file requires too many non-contiguous areas of disk ( > 84 today ) mixedDevices -- a bootable file is not entirely on one device, or not on correct device }; Reason: TYPE = RC[SUCC[ok]..LAST[RC]]; -- error reason Error: ERROR[why: Reason]; VolumeID: TYPE[5]; NullVolumeRep: PRIVATE TYPE = RECORD[a,b,c,d,e:CARDINAL]; nullVolumeID: VolumeID = LOOPHOLE[NullVolumeRep[a:0,b:0,c:0,d:0,e:0]]; Volume: TYPE = REF VolumeObject; VolumeObject: TYPE; VolumeFile: TYPE = MACHINE DEPENDENT { -- root files of a volume checkpoint(0), microcode(1), germ(2), bootFile(3), debugger(4), -- outload file -- debuggee(5), -- outload file -- VM(6), -- virtual memory backing file -- VAM(7), -- volume allocation map -- client(8), -- client directory system root file -- alpine(9), -- for use by Alpine file servers -- (15) -- spare root page slots -- }; FP: TYPE = MACHINE DEPENDENT RECORD[ id(0): FileID, da(2): DA ]; FileID: TYPE[2]; DA: TYPE[2]; NullFileIDRep: PRIVATE TYPE = RECORD[a,b:CARDINAL]; NullDARep: PRIVATE TYPE = RECORD[a,b:CARDINAL]; nullDA: PRIVATE DA = LOOPHOLE[NullDARep[0,0]]; nullFP: FP = [id: nullFileID, da: nullDA]; nullFileID: FileID = LOOPHOLE[NullFileIDRep[0,0]]; PageNumber: TYPE = RECORD[INT]; PageCount: TYPE = INT; Add: PROC[p: PageNumber, n: PageCount] RETURNS[PageNumber] = INLINE { RETURN[ [p+n] ] }; -- "n" may be negative -- wordsPerPage: INT = 256; PagesForWords: PROC[w: INT] RETURNS[PageCount] = INLINE { RETURN[ (w+wordsPerPage-1) / wordsPerPage ] }; Handle: TYPE = REF Object; Object: TYPE; propertyWords: INT = 256; -- the number of words in a file's property storage. PropertyStorage: TYPE = LONG POINTER TO ARRAY [0..propertyWords) OF WORD; NextVolume: PROC[volume: Volume, wait: BOOL _ FALSE] RETURNS[Volume]; GetVolumeID: PROC[volume: Volume] RETURNS[id: VolumeID]; GetVolumeName: PROC[volume: Volume] RETURNS[Rope.ROPE]; GetVolumePages: PROC[volume: Volume] RETURNS[size, free: INT]; FindVolumeFromID: PROC[id: VolumeID] RETURNS[Volume]; FindVolumeFromName: PROC[name: Rope.ROPE] RETURNS[Volume]; SystemVolume: PROC RETURNS[Volume]; SetRoot: PROC[root: VolumeFile, file: Handle, page: PageNumber _ [0]]; GetRoot: PROC[volume: Volume, root: VolumeFile] RETURNS[fp: FP, page: PageNumber]; EraseVolume: PROC[volume: Volume]; Open: PROC[volume: Volume, fp: FP] RETURNS[Handle]; Create: PROC[volume: Volume, size: PageCount] RETURNS[Handle]; Delete: PROC[file: Handle]; Info: PROC[file: Handle] RETURNS[volume: Volume, fp: FP, size: PageCount]; SetSize: PROC[file: Handle, size: PageCount]; Read: UNSAFE PROC[file: Handle, from: PageNumber, nPages: PageCount, to: LONG POINTER]; Write: PROC[file: Handle, to: PageNumber, nPages: PageCount, from: LONG POINTER]; GetProperties: PROC[file: Handle] RETURNS[PropertyStorage]; WriteProperties: PROC[file: Handle]; END. Implementation Notes Pages, Labels and Data Structures A volume consists of a set of pages. Each page has a label and data. The data is what is transferred during the Read and Write operations, and is where properties are stored, and is where the system's permanent data structures are stored. The truth about the pages of a volume is recorded solely in the labels of the pages. Two forms of permanent data structure are used as hints for accessing the volume: a single volume allocation map (VAM) and a run-table for each file. The VAM is itself a file, whose data pages contain a bitmap indicating which pages of the volume are (probably) free. The run-table represents the set of pages which (probably) constitute the pages of the file. This set of pages is, in sequence: the file properties, the run-table itself, and the data pages of the file. The FP of a file consists of a volume-relative UID (2 words) plus the disk address of the file's first page. The labels of the pages of a file contain the file's UID, plus an identification of the page number relative to the file. The disk allocator attempts to allocate contiguous pages as far as possible. The file's property pages and the first page of the run-table are contiguous on disk. The run-table of a file indicates the set of runs of contiguous pages constituting the file, giving for each run its disk address and length. In this discussion, all disk addresses are relative to a logical volume. Maintaining the Hints To maintain the status of the VAM as a hint, the implementation maintains the invariant that the VAM on disk describes a superset of the free pages. That is, all free pages are marked so in the VAM, but some pages marked free in the VAM may actually be in use. The hint is verified by checking the label of a page before actually allocating. When freeing pages, the appropriate region of the VAM is written back to disk before marking the pages' labels as free. When allocating pages, the pages' labels are rewritten as being in use before writing the appropriate region of the VAM. This has the property of never losing pages. Note that when allocating pages, we can delay rewriting the VAM at the possible cost of having some invalid hints if we crash before rewriting it. To maintain the status of a file's run-table as a hint, the implementation maintains the invariant that the run-table on disk describes a superset of the pages of the file. That is, all the pages of the file are recorded in the run-table, but some pages in the run-table may no longer be part of the file. The hint is verified by checking the label of the last page of the file. If the run-table in fact describes too many pages, the hint can be corrected because the run-table will include the correct last page of the file: this can be found by binary chop of the run-table. When extending (or creating) a file, its run-table is written to disk before writing the labels of the new pages (NB: tricky for the first page of the run-table itself!). When contracting the file, the pages are marked as free before rewriting the run-table. When contracting, we can delay rewriting the run-table, but this doesn't seem worth the effort (considering the rarity of file contractions). The VAM and the run-tables can be reconstructed completely by reading the label of every page of the volume. Operations The VAM of an open volume is kept in virtual memory, as is the run-table of an open file. The disk operations for opening a file are: - read the run-table. - verify the label of the last page of the file (delayable). To extend a file: - choose the pages from the VAM, verifying each with a check-label disk operation. - write the new run-table. - write the new labels of the pages - write the VAM (delayable). This amounts to (2N+2) disk page transfers for allocating N pages, hopefully 4 disk requests. To contract a file: - write the VAM indicating the freed pages - write the page labels marking them as free - write the run-table (delayable, but probably synchronous). This amounts to (N+2) disk page transfers for freeing N pages, hopefully 3 disk requests. To delete a file: - write the VAM indicating the freed pages - write the page labels indicating them as free (run-table first). Cedar Nucleus (files): Public interface. File: NewFile.mesa Last edited by: Andrew Birrell, April 28, 1983 2:52 pm Introduction This interface provides for creating, accessing and deleting files. Files are permanent objects recorded on backing storage. The backing storage consists of (logical) volumes. Each file consists of a number of pages allocated on a particular volume. There are provisions for a root file in a volume, intended to be the origin of a higher level directory system. The data pages of a file can be read and written. Files can be extended or contracted. Files also have properties (recorded in leader pages which are otherwise invisible to clients of this interface). This interface allows the entire property storage of a file to be read or written. The structure and contents of that storage are beyond this interface. A volume is identified by a unique identifier, or by a human sensible string. Files are identified by an FP, which identifies a file uniquely relative to the volume on which it is allocated. Data pages within a file are numbered consecutively from 0. This interface does not provide for creating, formatting, initializing or scavenging volumes. Errors This error may be raised by most of the procedures. The possible values of "why" are detailed with each procedure. This error is raised after releasing internal locks: the facilities of this interface may be used from catch-phrases. For debugging, extra information may be available in the frame that raises this error. Types and Constants The permanent identification of a logical volume. Universally permanently unique. Guaranteed to be the UID of no volume. The runtime representation of a volume. NIL never represents a valid volume. The permanent identification of a file. "id" is permanently unique relative to a volume. Guaranteed to be the FP of no file. Guaranteed to be the FileID of no file. Actually, [0..LAST[INT]). The file-relative number of a data page. The first data page of a file is numbered 0. Actually [0..LAST[INT]]. Represents file sizes. The number of words in each data page of a file. Might not equal VM.wordsPerPage. Should really say "DiskFace.wordsPerPage", but we don't want that compilation dependency. The runtime representation of a file. NIL never represents a valid file. Volumes The enumerator for volumes. This gives the volumes in time sequence of the containing physical volumes coming online (omitting volumes that are no longer online). A "VolumeObject" is created when the requisite containing physical volumes all come online, and remains valid until one of them goes offline. NextVolume[NIL] gives the first currently valid volume. If there are no more volumes and "wait" is FALSE, returns NIL. If there are no more volumes and "wait" is TRUE, waits until a new "VolumeObject" is created. Note that this enumeration includes volumes which may raise Error[inconsistent, software, hardware] if you try to access them, and a volume may go offline immediately after it has been returned by this enumeration. ! no errors Returns the volume's permanent UID. ! Error[wentOffline, inconsistent, software, hardware] Returns the human-sensible name of this volume (not necessarily unique). ! Error[wentOffline, inconsistent, software, hardware] Returns the present size and free page count of this volume. Obtain the handle for accessing the specified volume, by enumerating with "NextVolume" and "GetVolumeID", omitting volumes no longer online. If no suitable volume is found, then NIL is returned. Obtain the handle for accessing the specified volume, by enumerating with "NextVolume" and "GetVolumeName", omitting volumes no longer online and volumes that raise an error in GetVolumeName. If no suitable volume is found, then NIL is returned. Obtain the handle for accessing the volume which was booted to start this run. Returns NIL if there is no such volume. ! Error[wentOffline, unknownFile, inconsistent, software, hardware, mixedDevices] Installs the file as a root file of its volume, for subsequent access by GetRoot or when inloading/booting. "page", if provided, is the page number of the first data page used for inloading/booting from this file. ! Error[wentOffline, inconsistent, software, hardware] Returns the appropriate root file of the volume, or nullFP if no root has been installed. ! Error[wentOffline, inconsistent, software, hardware] Initialises the entire volume. This implicitly deletes every file on that volume, and sets all its volume root files to nullFP (except the VAM). Makes no assumptions about the previous contents of the volume. Error[inconsistent] probably indicates that a containing physical volume needs to be scavenged. Files ! Error[wentOffline, unknownFile, inconsistent, software, hardware] Prepares for runtime access to the file. Verifies that the FP is for an existing file, and reports "unknownFile" if not. Note that there is no Close operation, since it would have no effect. ! Error[wentOffline, volumeFull, fragmented, inconsistent, software, hardware] Creates a file having the given number of data pages and zero properties. ! Error[wentOffline, unknownFile, inconsistent, software, hardware] Destroys the file. ! Error[unknownFile] The size is the page number of data pages in the file. That is, a file with no data pages has size 0. ! Error[wentOffline, unknownFile, volumeFull, fragmented, inconsistent, software, hardware] Extends or contracts the file (synchronously). ! Error[wentOffline, unknownFile, unknownPage, inconsistent, software, hardware] Copies pages from the file starting at "from" into the VM specified by "to". ! Error[wentOffline, unknownFile, unknownPage, inconsistent, software, hardware] Copies pages from the VM specified by "from" into the file starting at "to". ! Error[unknownFile] Returns storage containing the properties of a file. The property storage is uninterpreted at this level and lives as long as the file handle. This call never involves disk IO. ! Error[wentOffline, unknownFile, inconsistent, software, hardware] Writes the property storage of the file back to disk, Κm˜headšœ)™)Jšœ™Jšœ6™6—šœ ™ JšœΤ™ΤJ™Jšœό™όJ™Jšœ]™]J˜šΟk ˜ Jšœœœ˜—J˜Jšœ œ œ˜J˜Jš˜—šœ™šœœΟc*˜7Jšœ˜Jšœ ž9˜FJšœžG˜UJšœ žL˜VJšœ ž9˜CJšœ žA˜NJšœ ž/˜Jšœ6™6Jšœ<™<—J˜šŸœœœ ˜5JšœΓ™Γ—J˜šŸœœ œœ ˜:Jšœφ™φ—J˜šŸ œœœ ˜#Jšœw™w—J˜šŸœœ9˜FJšœQ™QJšœΦ™Φ—J˜šŸœœ#œœ˜RJšœ6™6JšœY™Y—J˜šŸ œœ˜"Jšœ6™6Jšœ³™³——šœ™šŸœœœœ ˜3JšœC™CJšœΐ™ΐ—J˜šŸœœ"œ ˜>JšœN™NJšœI™I—J˜šŸœœ˜JšœC™CJšœ™—J˜šŸœœœœ˜JJšœ™Jšœf™f—J˜šŸœœ ˜-Jšœ[™[Jšœ.™.—J˜š Ÿœœœ8œœ˜WJšœP™PJšœL™L—J˜šŸœœ8œœ˜QJšœP™PJšœL™L—J˜šŸ œœœ˜;Jšœ™Jšœ²™²—J˜šŸœœ˜$JšœC™CJšœ5™5—J˜Jšœ˜—˜˜!Ibodyš œΊœ&œΑœ)œqœΏ˜‰ —˜Lšœœ@œ_œ$œžœΈœmœS˜ŒLšœΈœž˜ΨLšœœe˜l—˜ LšœœR˜YL˜€Lš œ/œ‚œ œ'œ"˜’Lšœ!œ™œ$œ"˜…Lšœœ_˜———…—`=Υ