LogicalVolumeImpl.mesa - Access to per-volume data structures: root page and VAM
Copyright © 1985 by Xerox Corporation. All rights reserved.
Andrew Birrell December 8, 1983 9:48 am
Levin, September 22, 1983 3:32 pm
Bob Hagmann, March 19, 1985 3:06:49 pm PST
Doug Wyatt, February 27, 1985 10:03:29 am PST
Russ Atkinson (RRA) May 14, 1985 1:10:00 pm PDT
DIRECTORY
BootFile USING [ Location ],
Disk USING [ Channel, DoIO, DriveAttributes, 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, VolumeFile, VolumeID, Write ],
FileBackdoor USING [ SetRoot, VolumeFlusher],
FileInternal,
PhysicalVolume USING [ Physical, PhysicalRC, SubVolumeDetails ],
Process USING [ Detach, MsecToTicks, Pause, SecondsToTicks, Ticks ],
ProcessorFace USING [ GetClockPulses, microsecondsPerHundredPulses ],
Rope USING [ Equal, Fetch, FromRefText, Length, ROPE ],
VolumeFormat USING [ AbsID, Attributes, LogicalPage, LogicalPageCount, LogicalRoot, LogicalRun, LRCurrentVersion, LRSeal, LVBootFile, nullDiskFileID, RunPageCount, VAMObject, VAMChunk, vamChunkPos, volumeLabelLength ],
VM USING [ AddressForPageNumber, Allocate, Interval, MakeUnchanged, PageCount, PageNumber, PageNumberForAddress, PagesForWords, State, SwapIn, Unpin],
VMBacking USING [ Run ];
LogicalVolumeImpl: CEDAR MONITOR LOCKS volume USING volume: Volume
IMPORTS Disk, File, Process, ProcessorFace, FileBackdoor, FileInternal, Rope, VM
EXPORTS DiskFace--RelID,AbsID,Attributes--, File, FileBackdoor, FileInternal, PhysicalVolume--SetPhysicalRoot--
SHARES File = {
ROPE: TYPE = Rope.ROPE;
******** 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 = VMBacking.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 {
interval: VM.Interval = [
page: VM.PageNumberForAddress[req.data],
count: VM.PagesForWords[
(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];
};
notCheckpointing: CONDITION;
--FileInternal.--LockVolume: PUBLIC ENTRY PROC [volume: Volume] = {
Called before a checkpoint; unlock by calling ReadRootPage
WHILE volume.checkpointing DO WAIT notCheckpointing ENDLOOP;
volume.vamFile ← NIL; -- cf. GrabVAMFile
volume.checkpointing ← TRUE;
};
******** 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] = {
RETURN[ [
fileID: [abs[AbsID[id]]],
filePage: 0,
attributes: Attributes[logicalRoot],
dontCare: LOOPHOLE[LONG[0]]
] ]
};
RootTransfer: INTERNAL PROC [volume: Volume, direction: {read, write, init} ] RETURNS [why: File.RC] = TRUSTED {
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: SELECT direction FROM
read => [header: verify, label: verify, data: read],
write => [header: verify, label: verify, data: write],
init => [header: verify, label: write, data: write],
ENDCASE => ERROR,
count: 1 ];
[status, countDone] ← DoPinnedIO[volume.subVolumes.first.channel, @label, @req];
RETURN[ FileInternal.TranslateStatus[status] ]
};
--FileInternal.--ReadRootPage: PUBLIC ENTRY PROC [volume: Volume] = TRUSTED {
ENABLE UNWIND => NULL;
IF volume.root = NIL THEN
volume.root ← VM.AddressForPageNumber[VM.Allocate[VM.PagesForWords[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 {
ENABLE File.Error => {
volume.vamStatus ← SELECT why FROM
unknownFile, unknownPage => inconsistent,
ENDCASE => why;
CONTINUE
};
volume.lastFileID ← volume.root.lastFileID;
ReadVAM[volume];
volume.vamStatus ← ok;
}
ELSE volume.vamStatus ← inconsistent;
volume.checkpointing ← FALSE;
BROADCAST notCheckpointing;
ConsiderFlushing[volume];
};
--FileInternal.--InitRootPage: PUBLIC ENTRY PROC [volume: Volume, name: ROPE] RETURNS [File.RC] = TRUSTED {
ENABLE UNWIND => NULL;
IF volume.root = NIL THEN volume.root ← VM.AddressForPageNumber[VM.Allocate[
VM.PagesForWords[DiskFace.wordsPerPage]].page];
volume.root^ ← [
vID: volume.id,
labelLength: MIN[name.Length[], VolumeFormat.volumeLabelLength],
volumeSize: volume.size
see also the defaults in the declaration of VolumeFormat.LogicalRoot
];
FOR i: CARDINAL IN [0..volume.root.labelLength) DO
volume.root.label[i] ← name.Fetch[i];
ENDLOOP;
volume.rootStatus ← RootTransfer[volume, init];
IF volume.rootStatus = ok THEN [] ← FileInternal.InitLogicalMarkers[volume];
volume.name ← name;
volume.lastFileID ← volume.root.lastFileID;
volume.vamStatus ← inconsistent; -- until someone calls EraseVolume
volume.checkpointing ← FALSE;
BROADCAST notCheckpointing;
ConsiderFlushing[volume];
RETURN[volume.rootStatus]
};
GetName: PROC [ chars: LONG POINTER TO PACKED ARRAY [0..VolumeFormat.volumeLabelLength) OF CHAR, length: INT] RETURNS [ROPE] = TRUSTED {
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]]
};
--File.--GetVolumeName: PUBLIC ENTRY PROC [volume: Volume] RETURNS [ROPE] = {
ENABLE UNWIND => NULL;
IF volume.rootStatus # ok AND volume.rootStatus # nonCedarVolume THEN
RETURN WITH ERROR File.Error[volume.rootStatus];
RETURN[volume.name]
};
--File.--FindVolumeFromID: PUBLIC PROC [id: File.VolumeID] RETURNS [volume: Volume] = {
volume ← NIL;
DO volume ← File.NextVolume[volume];
IF volume = NIL THEN EXIT;
IF GetVolumeID[volume] = id THEN EXIT;
ENDLOOP;
};
--File.--FindVolumeFromName: PUBLIC PROC [name: ROPE] RETURNS [volume: Volume] = {
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;
};
--File.--LogicalInfo: PUBLIC ENTRY PROC [volume: Volume] RETURNS [ id: File.VolumeID, size: INT, rootStatus: File.RC, name: ROPE, vamStatus: File.RC, free: INT, freeboard: INT] = {
{name, vamStatus, free, freeboard} only valid if rootStatus is ok or nonCedarVolume
{free, freeboard} only valid if vamStatus is ok
ENABLE UNWIND => NULL;
WHILE volume.checkpointing DO WAIT notCheckpointing ENDLOOP;
RETURN[
id: volume.id,
size: volume.size,
rootStatus: volume.rootStatus,
name: volume.name,
vamStatus: volume.vamStatus,
free: volume.free,
freeboard: volume.freeboard]
};
--FileInternal.--TranslateLogicalRun: PUBLIC --EXTERNAL-- PROC [logicalRun: VolumeFormat.LogicalRun, volume: Volume] RETURNS [channel: Disk.Channel, diskPage: Disk.PageNumber] = {
Accesses only immutable fields of the volume
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 THEN
RETURN [channel: sv.first.channel, diskPage: [sv.first.address + (logicalRun.first - sv.first.start)] ];
REPEAT FINISHED => RETURN WITH ERROR File.Error[inconsistent]
ENDLOOP;
};
--PhysicalVolume.--GetPhysical: PUBLIC PROC [volume: Volume, page: VolumeFormat.LogicalPage ← [0]] RETURNS [PhysicalVolume.Physical] = {
FOR sv: LIST OF PhysicalVolume.SubVolumeDetails ← volume.subVolumes, sv.rest UNTIL sv = NIL DO
IF sv.first.start <= page AND sv.first.start + sv.first.size > page THEN
RETURN[sv.first.physical];
ENDLOOP;
RETURN[NIL]
};
--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 {
ENABLE UNWIND => NULL;
why: File.RC;
WHILE volume.checkpointing DO WAIT notCheckpointing ENDLOOP;
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 why ← FileInternal.WriteLogicalMarkers[volume];
IF why # ok THEN RETURN WITH ERROR File.Error[why, page];
};
--FileBackdoor.--GetRoot: PUBLIC ENTRY PROC [volume: Volume, root: File.VolumeFile] RETURNS [fp: File.FP, page: File.PageNumber ← [0]] = TRUSTED {
ENABLE UNWIND => NULL;
WHILE volume.checkpointing DO WAIT notCheckpointing ENDLOOP;
IF volume.rootStatus # ok THEN RETURN WITH ERROR File.Error[volume.rootStatus];
[fp: fp, page: page] ← volume.root.rootFile[root];
};
--FileInternal.--GetLogicalLocation: PUBLIC ENTRY PROC [volume: Volume, root: VolumeFormat.LVBootFile] RETURNS [location: BootFile.Location] = TRUSTED {
ENABLE UNWIND => NULL;
WHILE volume.checkpointing DO WAIT notCheckpointing ENDLOOP;
IF volume.rootStatus # ok AND volume.rootStatus # nonCedarVolume THEN
RETURN WITH ERROR File.Error[volume.rootStatus];
location.diskFileID ← volume.root.bootingInfo[root];
[type: location.deviceType, ordinal: location.deviceOrdinal] ←
Disk.DriveAttributes[volume.subVolumes.first.channel];
};
--PhysicalVolume.--SetPhysicalRoot: PUBLIC ENTRY PROC [volume: Volume, root: File.VolumeFile] = TRUSTED {
ENABLE UNWIND => NULL;
physRC: PhysicalVolume.PhysicalRC;
WHILE volume.checkpointing DO WAIT notCheckpointing ENDLOOP;
IF volume.rootStatus # ok AND volume.rootStatus # nonCedarVolume THEN
RETURN WITH ERROR File.Error[volume.rootStatus];
physRC ← FileInternal.SetPhysicalLocation[volume.subVolumes.first.physical,
root, volume.root.bootingInfo[root]];
IF physRC # ok THEN
RETURN WITH ERROR File.Error[physRC, volume.root.bootingInfo[root].firstPage];
};
--FileBackdoor.--MarkDebugger: PUBLIC ENTRY PROC [volume: Volume, isDebugger: BOOL] = TRUSTED {
ENABLE UNWIND => NULL;
why: File.RC;
WHILE volume.checkpointing DO WAIT notCheckpointing ENDLOOP;
IF volume.rootStatus # ok THEN RETURN WITH ERROR File.Error[volume.rootStatus];
volume.root.coCedar ← isDebugger;
why ← RootTransfer[volume, write];
IF why = ok THEN why ← FileInternal.WriteLogicalMarkers[volume];
IF why # ok THEN RETURN WITH ERROR File.Error[why];
};
--FileBackdoor.--IsDebugger: PUBLIC ENTRY PROC [volume: Volume] RETURNS [BOOL] = TRUSTED {
ENABLE UNWIND => NULL;
WHILE volume.checkpointing DO WAIT notCheckpointing ENDLOOP;
IF volume.rootStatus = nonCedarVolume THEN RETURN[volume.root.type # pilot];
IF volume.rootStatus # ok THEN RETURN WITH ERROR File.Error[volume.rootStatus];
RETURN[volume.root.coCedar]
};
EraseRoot: INTERNAL PROC [volume: Volume] = TRUSTED {
volume.root.bootingInfo ← ALL[VolumeFormat.nullDiskFileID];
volume.root.rootFile ← ALL[];
};
idGroupSize: INT = 100; -- number if id's to allocate at a time.
--FileInternal.--NewID: PUBLIC ENTRY PROC [volume: Volume] RETURNS [FileID] = TRUSTED {
ENABLE UNWIND => NULL;
WHILE volume.checkpointing DO WAIT notCheckpointing ENDLOOP;
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] ]
};
******** 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.PagesForWords[VAMWords[pages]]];
};
IsUsed: PUBLIC ENTRY PROC [volume: Volume, page: VolumeFormat.LogicalPage] RETURNS [inUse: BOOL] = {
RETURN[Used[volume.vam, page]];
};
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]];
};
SetPageUsed: PUBLIC ENTRY PROC [volume: Volume, page: VolumeFormat.LogicalPage, inUse: BOOL] RETURNS [wasInUse: BOOL] = {
wasInUse ← Used[volume.vam, page];
SetUsed[volume: volume, page: page, inUse: inUse];
volume.vamChanged ← TRUE;
};
SetUsed: INTERNAL PROC [volume: Volume, 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];
chunk: LONG POINTER TO VolumeFormat.VAMChunk =
LOOPHOLE[@volume.vam.used + p.ms*SIZE[VolumeFormat.VAMChunk]];
IF chunk[p.ls] # inUse THEN {
chunk[p.ls] ← inUse;
IF inUse THEN volume.free ← volume.free-1 ELSE volume.free ← volume.free+1;
};
};
AllocVAM: INTERNAL PROC [volume: Volume] = TRUSTED {
IF volume.vam = NIL THEN {
words: INT = VAMWords[volume.size];
volume.vam ← VM.AddressForPageNumber[VM.Allocate[VM.PagesForWords[words]].page];
volume.vam.size ← volume.size;
};
volume.vam.rover ← [0];
};
ReadVAM: INTERNAL PROC [volume: Volume] = TRUSTED {
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];
SetUsed[volume, volRoot, TRUE];
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;
BROADCAST vamFileRelease; -- significant if we called GrabVAMFile for a checkpoint
};
--FileBackdoor.--GetVolumePages: PUBLIC ENTRY PROC [volume: Volume] RETURNS [size, free, freeboard: INT] = {
ENABLE UNWIND => NULL;
WHILE volume.checkpointing DO WAIT notCheckpointing ENDLOOP;
IF volume.rootStatus # ok THEN RETURN WITH ERROR File.Error[volume.rootStatus];
RETURN[size: volume.size, free: volume.free, freeboard: volume.freeboard]
};
--FileBackdoor.--SetFlusher: PUBLIC ENTRY PROC [volume: Volume, flusher: FileBackdoor.VolumeFlusher, data: REF ANY] = {
ENABLE UNWIND => NULL;
volume.flusherData ← data; volume.flusher ← flusher;
IF volume.freeboard = 0 THEN volume.freeboard ← MIN[volume.size/5, 1000];
ConsiderFlushing[volume];
};
ConsiderFlushing: INTERNAL PROC [volume: Volume] = {
IF volume.rootStatus = ok
AND volume.free < volume.freeboard - volume.freeboard / 10 -- be sure it's worth while
AND volume.flusher # NIL
AND NOT volume.flushing
THEN TRUSTED{
volume.flushing ← TRUE;
Process.Detach[ FORK FlusherProcess[volume] ];
}
};
FlusherProcess: PROC [volume: Volume] = {
DO
flusher: FileBackdoor.VolumeFlusher;
data: REF ANY;
lack: VolumeFormat.LogicalPageCount;
continue: BOOL;
urgent: BOOL;
Examine: ENTRY PROC [volume: Volume] = {
flusher ← volume.flusher;
data ← volume.flusherData;
lack ← MAX[volume.freeboard - volume.free, 0];
continue ← volume.free < volume.freeboard AND volume.flusher # NIL;
urgent ← volume.free < volume.freeboard / 2;
IF NOT continue THEN volume.flushing ← FALSE;
};
start: LONG CARDINAL ← ProcessorFace.GetClockPulses[];
elapsed: LONG CARDINAL;
progress: BOOL;
Examine[volume];
IF NOT continue THEN EXIT;
progress ← flusher[volume, lack, data];
elapsed ← ProcessorFace.GetClockPulses[] - start;
IF progress
THEN {
IF NOT urgent
THEN Process.Pause[Process.MsecToTicks[
MIN[(elapsed+99)/100 * ProcessorFace.microsecondsPerHundredPulses, 500]]];
}
ELSE Process.Pause[Process.MsecToTicks[1000]];
ENDLOOP;
};
--FileBackdoor.--GetFlusher: PUBLIC ENTRY PROC [volume: Volume] RETURNS [FileBackdoor.VolumeFlusher, REF ANY] = {
ENABLE UNWIND => NULL;
RETURN[volume.flusher, volume.flusherData]
};
--FileInternal.--Flush: PUBLIC PROC [volume: Volume, lack: VolumeFormat.LogicalPageCount] RETURNS [BOOL] = {
flusher: FileBackdoor.VolumeFlusher;
data: REF ANY;
[flusher, data] ← GetFlusher[volume];
IF flusher # NIL AND flusher[volume, lack, data] THEN RETURN[TRUE];
RETURN[FALSE]
};
--FileBackdoor.--SetFreeboard: PUBLIC ENTRY PROC [volume: Volume, freeboard: INT] = {
ENABLE UNWIND => NULL;
volume.freeboard ← freeboard;
ConsiderFlushing[volume];
};
--FileInternal.--FindLargestFreeBlockInBiggestSubVolume: PUBLIC ENTRY PROC [volume: Volume] RETURNS [first: VolumeFormat.LogicalPage ← [0], count: VolumeFormat.LogicalPageCount ← 0, subVolume: PhysicalVolume.SubVolumeDetails ← NIL] = TRUSTED{
Special routine to find the largest free piece of disk for allocating the VM Backing File on biggest sub-volume
vam: VAM;
pos: INT ;
logicalPos: VolumeFormat.LogicalPage;
currentFirst: INT ;
vamLast: INT ;
vam ← volume.vam;
FOR sv: LIST OF PhysicalVolume.SubVolumeDetails ← volume.subVolumes, sv.rest UNTIL sv = NIL DO
IF subVolume = NIL OR sv.first.size > subVolume.size THEN subVolume ← sv.first;
ENDLOOP;
vamLast ← subVolume.start + subVolume.size ;
currentFirst ← vamLast + 1 ;
FOR pos IN [ subVolume.start..vamLast ) DO
logicalPos ← [pos];
IF Used[vam, logicalPos] OR pos = vamLast - 1
THEN {
IF pos-currentFirst >= count
THEN {
first ← [currentFirst] ;
count ← pos-currentFirst+1;
}
ELSE currentFirst ← vamLast + 1;
}
ELSE IF currentFirst = vamLast + 1 THEN currentFirst ← pos ;
ENDLOOP;
};
--FileInternal.--Alloc: PUBLIC ENTRY PROC [volume: Volume, first: VolumeFormat.LogicalPage, size, min: VolumeFormat.LogicalPageCount] RETURNS [given: VolumeFormat.LogicalRun] = TRUSTED {
ENABLE UNWIND => NULL;
Restrict run length to LAST[CARDINAL], to maximize runs per run-table page
reqSize: VolumeFormat.RunPageCount = MIN[size,LAST[VolumeFormat.RunPageCount]];
pos: VolumeFormat.LogicalPage;
vam: VAM;
WHILE volume.checkpointing DO WAIT notCheckpointing ENDLOOP;
IF volume.vamStatus # ok THEN RETURN WITH ERROR File.Error[volume.vamStatus];
IF volume.free < size THEN RETURN WITH ERROR File.Error[volumeFull];
IF size = 0 THEN RETURN[[first: first, size: 0]]; -- main algorithm gives at least one page
vam ← volume.vam;
pos ← IF first = 0 THEN vam.rover ELSE first;
min ← MAX[ MIN[min, reqSize], 1 ]; -- otherwise the algorithm doesn't work!
Loop probing for a free page at "min" intervals
THROUGH [0 .. (vam.size+min-1)/min] DO
IF pos >= vam.size THEN pos ← [0];
IF NOT Used[vam, pos] THEN {
Expand around "pos" to see if there's a run of size at least "min"
start, end: VolumeFormat.LogicalPage ← pos;
given.size ← 1;
WHILE start > 0 AND given.size < reqSize
DO IF Used[vam, [start-1]] THEN EXIT;
start ← [start-1]; given.size ← given.size + 1;
ENDLOOP;
WHILE end < vam.size-1 AND given.size < reqSize
DO IF Used[vam, [end+1]] THEN EXIT;
end ← [end+1]; given.size ← given.size + 1;
ENDLOOP;
IF given.size >= min THEN { given.first ← start; EXIT };
};
pos ← [pos+min];
REPEAT FINISHED => RETURN WITH ERROR File.Error[volumeFull]
ENDLOOP;
volume.vamChanged ← TRUE;
FOR i: INT IN [0..given.size) DO SetUsed[volume, [given.first+i], TRUE] ENDLOOP;
IF first = 0 THEN vam.rover ← given.first;
ConsiderFlushing[volume];
};
--FileInternal.--Free: PUBLIC ENTRY PROC [volume: Volume, logicalRun: VolumeFormat.LogicalRun] = {
ENABLE UNWIND => NULL;
WHILE volume.checkpointing DO WAIT notCheckpointing ENDLOOP;
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, [logicalRun.first + i], FALSE];
ENDLOOP;
};
******** 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 {
ENABLE UNWIND => NULL;
DO
WHILE volume.checkpointing DO WAIT notCheckpointing ENDLOOP;
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
};
ReleaseVAMFile: ENTRY PROC [volume: Volume, file: File.Handle, changed: BOOL] = TRUSTED {
ENABLE UNWIND => NULL;
volume.vamChanged ← volume.vamChanged OR changed--indicates if commit failed--;
IF (volume.vamFile ← file) = NIL THEN volume.vamStatus ← inconsistent;
BROADCAST vamFileRelease;
};
--FileInternal.--Commit: PUBLIC PROC [volume: Volume] = TRUSTED {
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];
};
InnerCommit: PROC [volume: Volume, vamFile: File.Handle] = TRUSTED {
filePageCount: File.PageCount = VAMFilePages[volume.size];
vmPagesPerFilePage: INT = VM.PagesForWords[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.PageNumberForAddress[fileBaseAddr];
FOR i: INT IN [0..vmPagesPerFilePage) DO IF VM.State[baseVMPage+i].dataState = changed THEN {
VM.MakeUnchanged[[page: baseVMPage, count: vmPagesPerFilePage]];
File.Write[vamFile, filePage, 1, fileBaseAddr];
EXIT
};
ENDLOOP;
ENDLOOP;
};
--FileBackdoor.--EraseVolume: PUBLIC PROC [volume: Volume] = TRUSTED {
EntryErase[volume];
We now own the (not-yet-created) volume.vamFile, but we're outside our monitor so File.Create won't deadlock!
{
ENABLE UNWIND => ReleaseVAMFile[volume, NIL, TRUE];-- vamState ← inconsistent
vamFile: File.Handle ← NIL;
NoteBad: PROC [bad: VolumeFormat.LogicalPage] = CHECKED {
Silly: ENTRY PROC [volume: Volume] = { SetUsed[volume, bad, TRUE] };
Silly[volume]
};
LongFree: PROC [first: VolumeFormat.LogicalPage, size: INT] = TRUSTED {
FileInternal.FreeRun is restricted to LAST[CARDINAL] pages
WHILE size > 0 DO
amount: CARDINAL = MIN[size, LAST[VolumeFormat.RunPageCount]];
FileInternal.FreeRun[[first: first, size: amount], volume];
first ← [first+amount];
size ← size - amount;
ENDLOOP;
};
FOR sv: LIST OF PhysicalVolume.SubVolumeDetails ← volume.subVolumes, sv.rest UNTIL sv = NIL DO
Don't free root (!), nor first page of sub-volumes (to break up runs)
IF volRoot >= sv.first.start AND volRoot < sv.first.start + sv.first.size
THEN {
Avoid overwriting volume root page!
IF volRoot > 0 THEN LongFree[first: [sv.first.start+1], size: volRoot-sv.first.start-1];
LongFree[first: [volRoot+1], size: sv.first.size-(volRoot-sv.first.start)-1];
}
ELSE LongFree[first: [sv.first.start+1], size: sv.first.size-1];
Note: ideally, we shouldn't write free labels on bad pages, but it doesn't matter much
FileInternal.GetBadPages[sv.first, NoteBad];
ENDLOOP;
vamFile ← File.Create[volume, VAMFilePages[volume.size]];
InnerCommit[volume, vamFile];
FileBackdoor.SetRoot[VAM, vamFile];
ReleaseVAMFile[volume, vamFile, FALSE];
};
};
EntryErase: ENTRY PROC [volume: Volume] = TRUSTED {
ENABLE UNWIND => NULL;
WHILE volume.checkpointing DO WAIT notCheckpointing ENDLOOP;
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.free ← volume.vam.size; -- to prevent underflow in SetUsed
FOR i: INT IN [0..volume.vam.size) DO SetUsed[volume, [i], TRUE] ENDLOOP;
volume.free ← 0;
volume.vamStatus ← ok; -- but we still own the (not-yet-created) volume.vamFile
};
CommitVAMFiles: PROC = {
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;
};
TRUSTED {
Process.Detach[FORK CommitVAMFiles[]];
};
}.
Bob Hagmann January 29, 1985 1:55:14 pm PST
Cedar 6.0 conversion- change to FileBackdoor interface
Bob Hagmann March 19, 1985 3:06:49 pm PST
changes to: IsUsed