Cedar Nucleus(Files): Access to per-volume data structures: root page and VAM
LogicalVolumeImpl.mesa
Andrew Birrell August 8, 1983 12:09 pm
Last Edited by: Levin, June 28, 1983 4:07 pm
DIRECTORY
Disk USING[ Channel, DoIO, invalid, Label, labelCheck, ok, PageNumber, PageCount, Request, SameDrive, Status ],
DiskFace USING[ DontCare, RelID, wordsPerPage ],
File USING[ Create, Error, FileID, FP, nullFP, Handle, NextVolume, Open, PageCount, PageNumber, PagesForWords, RC, Read, SetRoot, VolumeFile, VolumeFlusher, VolumeID, Write ],
FileInternal,
Process USING[ Pause, SecondsToTicks, Ticks ],
Rope USING[ Equal, FromRefText, ROPE ],
VolumeFormat USING[ AbsID, Attributes, LogicalPage, LogicalPageCount, LogicalRoot, LogicalRun, LRCurrentVersion, LRSeal, LVBootFile, nullDiskFileID, RunPageCount, VAMObject, VAMChunk, vamChunkPos, volumeLabelLength ],
PhysicalVolume USING[ SubVolumeDetails ],
VM USING[ AddressToPageNumber, Allocate, Interval, MakeUnchanged, PageCount, PageNumber, PageNumberToAddress, State, SwapIn, Unpin, WordsToPages],
VMSideDoor USING[ Run ];
LogicalVolumeImpl: CEDAR MONITOR LOCKS volume USING volume: Volume
IMPORTS Disk, File, Process, FileInternal, Rope, VM
EXPORTS DiskFace--RelID,AbsID,Attributes--, File, FileInternal
SHARES File =
BEGIN
-- ******** Data Types and minor subroutines ******** --
--DiskFace.--Attributes: PUBLIC TYPE = VolumeFormat.Attributes;
--DiskFace.--AbsID: PUBLIC TYPE = VolumeFormat.AbsID;
--File.--FileID: PUBLIC TYPE = FileInternal.FileID;
Volume: TYPE = REF VolumeObject;
--File.--VolumeObject: PUBLIC TYPE = FileInternal.VolumeObject;
PhysicalRun: TYPE = VMSideDoor.Run;
DoPinnedIO: UNSAFE PROC[channel: Disk.Channel, label: LONG POINTER TO Disk.Label, req: POINTER TO Disk.Request]
RETURNS[ status: Disk.Status, countDone: Disk.PageCount] = TRUSTED
BEGIN
interval: VM.Interval = [
page: VM.AddressToPageNumber[req.data],
count: VM.WordsToPages[
(IF req.incrementDataPtr THEN req.count ELSE 1)*DiskFace.wordsPerPage] ];
VM.SwapIn[interval: interval, kill: req.command.data=read, pin: TRUE];
[status, countDone] ← Disk.DoIO[channel, label, req ! UNWIND => VM.Unpin[interval] ];
VM.Unpin[interval];
END;
-- ******** Access to volume root page and volume's list of sub-volumes ******** --
volRoot: VolumeFormat.LogicalPage = [0]; -- logical page number of volume root page --
--File.--GetVolumeID: PUBLIC PROC[volume: Volume] RETURNS[id: File.VolumeID] =
{ RETURN[volume.id] };
LogRootLabel: PROC[id: File.VolumeID] RETURNS[Disk.Label] =
BEGIN
RETURN[ [
fileID: [abs[AbsID[id]]],
filePage: 0,
attributes: Attributes[logicalRoot],
dontCare: LOOPHOLE[LONG[0]]
] ]
END;
RootTransfer: INTERNAL PROC[volume: Volume, direction: {read, write} ]
RETURNS[why: File.RC] = TRUSTED
BEGIN
status: Disk.Status;
countDone: Disk.PageCount;
label: Disk.Label ← LogRootLabel[volume.id];
req: Disk.Request ← [
diskPage: volume.subVolumes.first.address,
data: volume.root,
incrementDataPtr: TRUE,
command: [header: verify, label: verify, data: IF direction = read THEN read ELSE write],
count: 1 ];
[status, countDone] ←
DoPinnedIO[volume.subVolumes.first.channel, @label, @req];
RETURN[ FileInternal.TranslateStatus[status] ]
END;
--FileInternal.--ReadRootPage: PUBLIC ENTRY PROC[volume: Volume] = TRUSTED
BEGIN
ENABLE UNWIND => NULL;
volume.root ← VM.PageNumberToAddress[VM.Allocate[
VM.WordsToPages[DiskFace.wordsPerPage]].page];
volume.rootStatus ← RootTransfer[volume, read];
IF volume.rootStatus = ok
AND (volume.root.seal # VolumeFormat.LRSeal
OR volume.root.version # VolumeFormat.LRCurrentVersion)
THEN volume.rootStatus ← inconsistent;
IF volume.rootStatus = ok
THEN TRUSTED{ volume.name ← GetName[@volume.root.label, volume.root.labelLength] };
IF volume.rootStatus = ok AND volume.root.type # cedar
THEN volume.rootStatus ← nonCedarVolume;
IF volume.rootStatus = ok
THEN BEGIN
ENABLE File.Error =>
BEGIN
volume.vamStatus ← SELECT why FROM
unknownFile, unknownPage => inconsistent,
ENDCASE => why;
CONTINUE
END;
volume.lastFileID ← volume.root.lastFileID;
ReadVAM[volume];
volume.vamStatus ← ok;
END;
END;
GetName: PROC[
chars: LONG POINTER TO PACKED ARRAY [0..VolumeFormat.volumeLabelLength) OF CHAR,
length: INT]
RETURNS[Rope.ROPE] = TRUSTED
BEGIN
text: REF TEXT = NEW[TEXT[length]];
FOR i: INT IN [0..length) DO text[i] ← chars[i] ENDLOOP;
text.length ← length;
RETURN[Rope.FromRefText[text]]
END;
--File.--GetVolumeName: PUBLIC ENTRY PROC[volume: Volume] RETURNS[Rope.ROPE] =
BEGIN
ENABLE UNWIND => NULL;
IF volume.rootStatus # ok AND volume.rootStatus # nonCedarVolume
THEN RETURN WITH ERROR File.Error[volume.rootStatus];
RETURN[volume.name]
END;
--File.--FindVolumeFromID: PUBLIC PROC[id: File.VolumeID] RETURNS[volume: Volume] =
BEGIN
volume ← NIL;
DO volume ← File.NextVolume[volume];
IF volume = NIL THEN EXIT;
IF GetVolumeID[volume] = id THEN EXIT;
ENDLOOP;
END;
--File.--FindVolumeFromName: PUBLIC PROC[name: Rope.ROPE] RETURNS[volume: Volume] =
BEGIN
volume ← NIL;
DO volume ← File.NextVolume[volume];
IF volume = NIL THEN EXIT;
IF Rope.Equal[GetVolumeName[volume ! File.Error => CONTINUE], name, FALSE]
THEN EXIT;
ENDLOOP;
END;
--FileInternal.--TranslateLogicalRun: PUBLIC --EXTERNAL-- PROC[logicalRun: VolumeFormat.LogicalRun, volume: Volume]
RETURNS[channel: Disk.Channel, diskPage: Disk.PageNumber] =
Accesses only immutable fields of the volume
BEGIN
FOR sv: LIST OF PhysicalVolume.SubVolumeDetails ← volume.subVolumes, sv.rest UNTIL sv = NIL
DO IF sv.first.start <= logicalRun.first
AND sv.first.start + sv.first.size >= logicalRun.first + logicalRun.size
THEN RETURN[channel: sv.first.channel,
diskPage: [sv.first.address + (logicalRun.first - sv.first.start)]
];
REPEAT FINISHED => RETURN WITH ERROR File.Error[inconsistent]
ENDLOOP;
END;
--FileInternal.--RecordRootFile: PUBLIC ENTRY PROC[volume: Volume, root: File.VolumeFile, fp: File.FP, page: File.PageNumber, id: DiskFace.RelID, link: DiskFace.DontCare, channel: Disk.Channel] = TRUSTED
BEGIN
ENABLE UNWIND => NULL;
why: File.RC;
IF volume.rootStatus # ok THEN RETURN WITH ERROR File.Error[volume.rootStatus];
IF NOT Disk.SameDrive[channel, volume.subVolumes.first.channel]
THEN RETURN WITH ERROR File.Error[mixedDevices];
If root = VAM then I hope you know what you're doing!
volume.root.rootFile[root] ← [fp: fp, page: page];
IF root IN [FIRST[VolumeFormat.LVBootFile]..LAST[VolumeFormat.LVBootFile]]
THEN volume.root.bootingInfo[root] ← [fID: [rel[id]], firstPage: page, firstLink: link];
why ← RootTransfer[volume, write];
IF why # ok THEN RETURN WITH ERROR File.Error[why];
END;
--File.--GetRoot: PUBLIC ENTRY PROC[volume: Volume, root: File.VolumeFile]
RETURNS[fp: File.FP, page: File.PageNumber ← [0]] = TRUSTED
BEGIN
ENABLE UNWIND => NULL;
IF volume.rootStatus # ok THEN RETURN WITH ERROR File.Error[volume.rootStatus];
[fp: fp, page: page] ← volume.root.rootFile[root];
END;
--File.--MarkDebugger: PUBLIC ENTRY PROC[volume: Volume, isDebugger: BOOL] = TRUSTED
BEGIN
ENABLE UNWIND => NULL;
why: File.RC;
IF volume.rootStatus # ok THEN RETURN WITH ERROR File.Error[volume.rootStatus];
volume.root.coCedar ← isDebugger;
why ← RootTransfer[volume, write];
IF why # ok THEN RETURN WITH ERROR File.Error[why];
END;
--File.--IsDebugger: PUBLIC ENTRY PROC[volume: Volume] RETURNS[BOOL] = TRUSTED
BEGIN
ENABLE UNWIND => NULL;
IF volume.rootStatus # ok THEN RETURN WITH ERROR File.Error[volume.rootStatus];
RETURN[volume.root.coCedar]
END;
EraseRoot: INTERNAL PROC[volume: Volume] = TRUSTED
BEGIN
volume.root.bootingInfo ← ALL[VolumeFormat.nullDiskFileID];
volume.root.rootFile ← ALL[];
END;
idGroupSize: INT = 100; -- number if id's to allocate at a time.
--FileInternal.--NewID: PUBLIC ENTRY PROC[volume: Volume] RETURNS [FileID] = TRUSTED
BEGIN
ENABLE UNWIND => NULL;
IF volume.rootStatus # ok THEN RETURN WITH ERROR File.Error[volume.rootStatus];
DO
lastRecorded: FileID = volume.root.lastFileID;
why: File.RC;
IF volume.lastFileID < lastRecorded THEN EXIT;
volume.root.lastFileID ← FileID[lastRecorded + idGroupSize];
why ← RootTransfer[volume, write];
IF why # ok THEN RETURN WITH ERROR File.Error[why];
ENDLOOP -- This is a loop only to recover from garbage ID's --;
RETURN[ volume.lastFileID ← [volume.lastFileID + 1] ]
END;
-- ******** Volume Allocation Map ******** --
VAM: TYPE = FileInternal.VAM;
PageBits: TYPE = MACHINE DEPENDENT RECORD[ls(0): CARDINAL, ms(1): CARDINAL];
VAMChunks: PROC[pages: VolumeFormat.LogicalPageCount] RETURNS[CARDINAL] = TRUSTED
{ OPEN p: LOOPHOLE[pages+LAST[CARDINAL]-1, PageBits]; RETURN[p.ms] };
VAMWords: PROC[pages: VolumeFormat.LogicalPageCount] RETURNS[INT] =
-- SIZE[VAMObject[VAMChunks[pages]]], but compiler can't handle it --
{ RETURN[VolumeFormat.vamChunkPos + VAMChunks[pages]*4096] };
VAMFilePages: PROC[pages: VolumeFormat.LogicalPageCount] RETURNS[File.PageCount] = INLINE
{ RETURN[File.PagesForWords[VAMWords[pages]]] };
VAMVMPages: PROC[pages: VolumeFormat.LogicalPageCount] RETURNS[VM.PageCount] = INLINE
{ RETURN[VM.WordsToPages[VAMWords[pages]]] };
Used: PROC[vam: VAM, page: VolumeFormat.LogicalPage] RETURNS[BOOL] = TRUSTED INLINE
-- vam.used[p.ms][p.ls]], but the compiler can't handle it! --
{ OPEN p: LOOPHOLE[page, PageBits];
RETURN[LOOPHOLE[@vam.used + p.ms*SIZE[VolumeFormat.VAMChunk],
LONG POINTER TO VolumeFormat.VAMChunk][p.ls]] };
SetUsed: PROC[vam: VAM, page: VolumeFormat.LogicalPage, inUse: BOOL] = TRUSTED INLINE
-- vam.used[p.ms][p.ls]], but the compiler can't handle it! --
{ OPEN p: LOOPHOLE[page, PageBits];
LOOPHOLE[@vam.used + p.ms*SIZE[VolumeFormat.VAMChunk],
LONG POINTER TO VolumeFormat.VAMChunk][p.ls] ← inUse };
AllocVAM: INTERNAL PROC[volume: Volume] = TRUSTED
BEGIN
IF volume.vam = NIL
THEN BEGIN
volume.vam ← VM.PageNumberToAddress[VM.Allocate[VAMVMPages[volume.size]].page];
volume.vam.size ← volume.size;
END;
SetUsed[volume.vam, volRoot, TRUE];
volume.vam.rover ← [0];
volume.free ← 0;
END;
ReadVAM: INTERNAL PROC[volume: Volume] = TRUSTED
BEGIN
this: VolumeFormat.LogicalPage ← [0];
IF volume.rootStatus # ok THEN ERROR; -- checked by our caller
volume.vamFile ←
File.Open[volume, volume.root.rootFile[VAM].fp --File.Error is caught by our caller--];
AllocVAM[volume];
File.Read[volume.vamFile, [0], VAMFilePages[volume.size], volume.vam];
volume.free ← 0;
DO IF this = volume.vam.size THEN EXIT;
IF NOT Used[volume.vam, this] THEN volume.free ← volume.free+1;
this ← [this+1];
ENDLOOP;
END;
--File.--GetVolumePages: PUBLIC ENTRY PROC[volume: Volume] RETURNS[size, free, freeboard: INT] =
BEGIN
ENABLE UNWIND => NULL;
IF volume.rootStatus # ok THEN RETURN WITH ERROR File.Error[volume.rootStatus];
RETURN[size: volume.size, free: volume.free, freeboard: volume.freeboard]
END;
--File.--SetFlusher: PUBLIC ENTRY PROC[volume: Volume, flusher: File.VolumeFlusher, data: REF ANY] =
BEGIN
ENABLE UNWIND => NULL;
volume.flusherData ← data; volume.flusher ← flusher;
IF volume.freeboard = 0 THEN volume.freeboard ← MIN[volume.size/5, 1000];
END;
--File.--GetFlusher: PUBLIC ENTRY PROC[volume: Volume] RETURNS[File.VolumeFlusher, REF ANY] =
BEGIN
ENABLE UNWIND => NULL;
RETURN[volume.flusher, volume.flusherData]
END;
--File.--SetFreeboard: PUBLIC ENTRY PROC[volume: Volume, freeboard: INT] =
BEGIN
ENABLE UNWIND => NULL;
volume.freeboard ← freeboard;
END;
--FileInternal.--Alloc: PUBLIC ENTRY PROC[volume: Volume, first: VolumeFormat.LogicalPage,
size: VolumeFormat.LogicalPageCount]
RETURNS[given: VolumeFormat.LogicalRun] = TRUSTED
BEGIN
ENABLE UNWIND => NULL;
Restrict run length to LAST[CARDINAL], to maximize runs per run-table page
reqSize: VolumeFormat.RunPageCount = MIN[size,LAST[VolumeFormat.RunPageCount]];
vam: VAM = volume.vam;
IF volume.vamStatus # ok THEN RETURN WITH ERROR File.Error[volume.vamStatus];
IF volume.free < size THEN RETURN WITH ERROR File.Error[volumeFull];
volume.vamChanged ← TRUE;
-- Restrict run length to LAST[CARDINAL], to maximize runs per run-table page --
-- TEMP! Returns first free run found --
WHILE Used[vam, vam.rover]
DO vam.rover ← [vam.rover+1]; IF vam.rover = vam.size THEN vam.rover ← [0] ENDLOOP;
given ← [first: vam.rover, size: 0];
UNTIL Used[vam, vam.rover] OR vam.rover = vam.size OR given.size = reqSize
DO given.size ← given.size+1; vam.rover ← [vam.rover+1] ENDLOOP;
FOR i: INT IN [0..given.size) DO SetUsed[vam, [given.first+i], TRUE] ENDLOOP;
volume.free ← volume.free - given.size;
END;
--FileInternal.--Free: PUBLIC ENTRY PROC[volume: Volume, logicalRun: VolumeFormat.LogicalRun] =
BEGIN
ENABLE UNWIND => NULL;
IF volume.vamStatus # ok THEN RETURN WITH ERROR File.Error[volume.vamStatus];
volume.vamChanged ← TRUE;
FOR i: VolumeFormat.RunPageCount IN [0..logicalRun.size)
DO SetUsed[volume.vam, [logicalRun.first + i], FALSE] ENDLOOP;
volume.free ← volume.free + logicalRun.size;
END;
--FileInternal.--Flush: PUBLIC PROC[volume: Volume, lack: VolumeFormat.LogicalPageCount] RETURNS [BOOL] =
BEGIN
flusher: File.VolumeFlusher;
data: REF ANY;
[flusher, data] ← GetFlusher[volume];
IF flusher # NIL AND flusher[volume, lack, data] THEN RETURN[TRUE];
IF GetVolumePages[volume].free >= lack THEN RETURN[TRUE];
RETURN[FALSE]
END;
-- ******** Creation and writing of the VAM file ******** --
This is messy, because there is a recursion through the top-level file operations, particularly File.Create. So we must tread very carefully to avoid recursing onto our own monitor lock. Note that File.Create does not call Commit.
vamFileRelease: CONDITION;
GrabVAMFile: ENTRY PROC[volume: Volume] RETURNS [file: File.Handle] = TRUSTED
BEGIN
ENABLE UNWIND => NULL;
DO
IF volume.vamStatus # ok THEN RETURN WITH ERROR File.Error[volume.vamStatus];
IF (file ← volume.vamFile) # NIL THEN { volume.vamFile ← NIL; EXIT };
WAIT vamFileRelease; -- because we must be in the process of erasing the volume
ENDLOOP;
volume.vamChanged ← FALSE; -- because our caller is about to write it to disk
END;
ReleaseVAMFile: ENTRY PROC[volume: Volume, file: File.Handle, changed: BOOL] = TRUSTED
BEGIN
ENABLE UNWIND => NULL;
volume.vamChanged ← volume.vamChanged OR changed--indicates if commit failed--;
IF (volume.vamFile ← file) = NIL THEN volume.vamStatus ← inconsistent;
BROADCAST vamFileRelease;
END;
--FileInternal.--Commit: PUBLIC PROC[volume: Volume] = TRUSTED
BEGIN
-- Ensure VAM is up to date on disk --
-- Assumes volume.vam is vm-page-aligned. --
vamFile: File.Handle ← GrabVAMFile[volume]; -- raises File.Error if vamFile isn't ok.
InnerCommit[volume, vamFile !
File.Error => { ReleaseVAMFile[volume, vamFile, TRUE]; vamFile ← NIL }; -- release our lock
UNWIND => IF vamFile # NIL THEN ReleaseVAMFile[volume, vamFile, TRUE]
];
ReleaseVAMFile[volume, vamFile, FALSE];
END;
InnerCommit: PROC[volume: Volume, vamFile: File.Handle] = TRUSTED
BEGIN
filePageCount: File.PageCount = VAMFilePages[volume.size];
vmPagesPerFilePage: INT = VM.WordsToPages[DiskFace.wordsPerPage];
FOR filePage: File.PageNumber ← [0], [filePage+1] UNTIL filePage = filePageCount
DO fileBaseAddr: LONG POINTER = LOOPHOLE[volume.vam + filePage * DiskFace.wordsPerPage];
baseVMPage: VM.PageNumber = VM.AddressToPageNumber[fileBaseAddr];
FOR i: INT IN [0..vmPagesPerFilePage)
DO IF VM.State[baseVMPage+i].dataState = changed
THEN BEGIN
VM.MakeUnchanged[[page: baseVMPage, count: vmPagesPerFilePage]];
File.Write[vamFile, filePage, 1, fileBaseAddr];
EXIT
END;
ENDLOOP;
ENDLOOP;
END;
--File.--EraseVolume: PUBLIC PROC[volume: Volume] = TRUSTED
BEGIN
EntryErase[volume];
We now own the (not-yet-created) volume.vamFile, but we're outside our monitor so File.Create won't deadlock!
BEGIN
ENABLE UNWIND => ReleaseVAMFile[volume, NIL, TRUE];-- vamState ← inconsistent
vamFile: File.Handle ← NIL;
FOR sv: LIST OF PhysicalVolume.SubVolumeDetails ← volume.subVolumes, sv.rest UNTIL sv = NIL
DO IF volRoot >= sv.first.start AND volRoot < sv.first.start + sv.first.size
THEN BEGIN
Avoid overwriting volume root page!
FileInternal.FreeRun[[first: sv.first.start, size: volRoot-sv.first.start], volume];
FileInternal.FreeRun[[first: [volRoot+1], size: sv.first.size-(volRoot-sv.first.start)-1], volume];
END
ELSE FileInternal.FreeRun[[first: sv.first.start, size: sv.first.size], volume];
ENDLOOP;
vamFile ← File.Create[volume, VAMFilePages[volume.size]];
InnerCommit[volume, vamFile];
File.SetRoot[VAM, vamFile];
ReleaseVAMFile[volume, vamFile, FALSE];
END;
END;
EntryErase: ENTRY PROC[volume: Volume] = TRUSTED
BEGIN
ENABLE UNWIND => NULL;
WHILE volume.vamStatus = ok AND volume.vamFile = NIL DO WAIT vamFileRelease ENDLOOP;
IF volume.rootStatus # ok THEN RETURN WITH ERROR File.Error[volume.rootStatus];
volume.vamStatus ← inconsistent;
volume.vamFile ← NIL;
EraseRoot[volume];
AllocVAM[volume];
volume.vamStatus ← ok; -- but we still own the (not-yet-created) volume.vamFile
END;
CommitVAMFiles: PROC =
BEGIN
commitPause: Process.Ticks ← Process.SecondsToTicks[1];
DO
FOR this: Volume ← File.NextVolume[NIL,FALSE], File.NextVolume[this,FALSE]
UNTIL this = NIL
DO IF this.vamChanged--in monitor!-- THEN Commit[this ! File.Error => CONTINUE] ENDLOOP;
Process.Pause[commitPause];
ENDLOOP;
END;
vamCommiter: PROCESS = FORK CommitVAMFiles[];
END.