FSFileSpaceImpl.mesa
Last Edited by: Schroeder, November 15, 1983 1:28 pm
DIRECTORY
BasicTime USING [GMT, Period],
BTree USING [Error],
File USING [Delete, Error, FP, Handle, Open, SetFlusher, Volume],
FS USING [Error],
FSBackdoor USING [EntryPtr, EntryType, MakeFName, Version],
FSDir USING [AcquireOldGName, DeleteEntry, EnumerateEntries],
FSFileOps USING [GetNameBodyAndVersion, VolumeDesc],
FSLock USING [ActiveFile, ReleaseRecord],
FSReport USING [ReportRemote],
Rope USING [ROPE, Text];
FSFileSpaceImpl: CEDAR MONITOR
IMPORTS BasicTime, BTree, File, FS, FSBackdoor, FSDir, FSFileOps, FSLock, FSReport
EXPORTS FSFileOps
= BEGIN
Space management variables and types
UseRecord: TYPE = RECORD[next: REF UseRecord, fp: File.FP, used: BasicTime.GMT];
LRUObject: TYPE = RECORD[
state: {new, started, dead} ← new,
vDesc: FSFileOps.VolumeDesc ← NIL,
first, last: REF UseRecord ← NIL,
count, flushed, error, deleted, superseded, open, gaveUp: INT ← 0
];
svLRU: REF LRUObject ← NIL;
Exported to FSFileOps
RegisterVolumeFlusher: PUBLIC ENTRY PROC [svDesc: FSFileOps.VolumeDesc] =
BEGIN
svLRU ← NEW [ LRUObject ];
svLRU.vDesc ← svDesc;
File.SetFlusher[svLRU.vDesc.vol, MakePagesAvailable, svLRU];
END;
RecordUsage: PUBLIC ENTRY PROC [fp: File.FP, time: BasicTime.GMT] =
BEGIN
IF svLRU # NIL AND svLRU.state = started
THEN BEGIN
u: REF UseRecord = NEW [ UseRecord ← [NIL, fp, time] ];
IF svLRU.first = NIL
THEN svLRU.first ← svLRU.last ← u
ELSE BEGIN
svLRU.last.next ← u;
svLRU.last ← u
END;
svLRU.count ← svLRU.count + 1;
END
END;
Internal procedures
MakePagesAvailable: PROC [volume: File.Volume, nPages: INT, clientInfo: REF] RETURNS [ok: BOOLEAN] =
BEGIN
vLRU: REF LRUObject = NARROW [ clientInfo ];
ok ← FALSE;
BEGIN
ENABLE BTree.Error, File.Error => {Count[vLRU, dead]; CONTINUE};
currentCount: INT = GetCount[vLRU];
THROUGH [0 .. currentCount) DO
victim: REF UseRecord = RemoveFirst[vLRU];
IF victim = NIL THEN EXIT -- time to stop
ELSE SELECT TryToFlush[vLRU, victim] FROM
flushed => RETURN[TRUE];
open => AddLast[vLRU, victim];
ENDCASE;
ENDLOOP;
Count[vLRU, gaveUp];
END;
END;
GetCount: ENTRY PROC [vLRU: REF LRUObject] RETURNS [INT] =
BEGIN
GetFPandUsed: UNSAFE PROC [entry: FSBackdoor.EntryPtr] RETURNS [accept, stop: BOOLEAN] = UNCHECKED
BEGIN
WITH e: entry^ SELECT FROM
cached => vLRU.first ← NEW [ UseRecord ← [vLRU.first, e.fp, e.used] ];
ENDCASE => ERROR;
vLRU.count ← vLRU.count + 1;
RETURN [accept: FALSE, stop: FALSE];
END;
SELECT vLRU.state FROM
started => NULL;
new => BEGIN
start: Rope.Text = "[";
FSDir.EnumerateEntries[vLRU.vDesc, start, all, GetFPandUsed, NIL];
[vLRU.first, vLRU.last] ← LRUOrder[vLRU.first];
vLRU.state ← started;
END;
ENDCASE => RETURN [0]; -- dead
RETURN [svLRU.count]
END;
RemoveFirst: ENTRY PROC [vLRU: REF LRUObject] RETURNS [u: REF UseRecord] =
BEGIN
u ← vLRU.first;
IF u = NIL THEN RETURN;
vLRU.first ← u.next;
IF vLRU.first = NIL
THEN vLRU.last ← NIL
ELSE u.next ← NIL;
vLRU.count ← svLRU.count - 1;
END;
AddLast: ENTRY PROC [vLRU: REF LRUObject, u: REF UseRecord] =
BEGIN
IF vLRU.first = NIL
THEN vLRU.first ← u
ELSE vLRU.last.next ← u;
vLRU.last ← u;
vLRU.count ← vLRU.count + 1;
END;
Count: ENTRY PROC [vLRU: REF LRUObject, event: {flushed, error, deleted, superseded, open, gaveUp, dead}] =
BEGIN
SELECT event FROM
flushed => vLRU.flushed ← vLRU.flushed + 1;
error => vLRU.error ← vLRU.error + 1;
deleted => vLRU.deleted ← vLRU.deleted + 1;
superseded => vLRU.superseded ← vLRU.superseded + 1;
open => vLRU.open ← vLRU.open + 1;
gaveUp => vLRU.gaveUp ← vLRU.gaveUp + 1;
dead => vLRU.state ← dead;
ENDCASE => ERROR;
END;
TryToFlush: PROC [vLRU: REF LRUObject, victim: REF UseRecord] RETURNS [result: {open, failed, flushed}] =
BEGIN
t: FSBackdoor.EntryType;
dirUsed: BasicTime.GMT;
aF: FSLock.ActiveFile;
entryFP: File.FP;
h: File.Handle;
nameBody: Rope.Text;
version: FSBackdoor.Version;
result ← flushed;
h ← File.Open[vLRU.vDesc.vol, victim.fp
! File.Error => BEGIN
Count[vLRU, IF why = unknownFile THEN deleted ELSE error];
result ← failed;
CONTINUE
END ];
IF result # flushed THEN RETURN;
[nameBody, version] ← FSFileOps.GetNameBodyAndVersion[h
! FS.Error => BEGIN
Count[vLRU, IF error.code = $badFP THEN deleted ELSE error];
result ← failed;
CONTINUE
END ];
IF result # flushed THEN RETURN;
[t, dirUsed, entryFP, aF] ← FSDir.AcquireOldGName[vLRU.vDesc, nameBody, version];
IF t = notFound THEN { Count[vLRU, deleted]; result ← failed; RETURN };
IF aF = NIL OR aF.fileLock # none
THEN { FSLock.ReleaseRecord[aF]; Count[vLRU, open]; result ← open; RETURN };
IF entryFP # victim.fp -- wierd case, but I think it can happen
THEN { FSLock.ReleaseRecord[aF]; Count[vLRU, deleted]; result ← failed; RETURN} ;
IF BasicTime.Period[from: dirUsed, to: victim.used ] < 0
THEN { FSLock.ReleaseRecord[aF]; Count[vLRU, superseded]; result ← failed; RETURN };
BEGIN
fName: Rope.ROPE = FSBackdoor.MakeFName[nameBody, version];
FSReport.ReportRemote[startFlushing, fName];
FSDir.DeleteEntry[vLRU.vDesc, nameBody, version
! BTree.Error, File.Error =>
{FSLock.ReleaseRecord[aF]; FSReport.ReportRemote[endFlushing, fName]}
];
FSLock.ReleaseRecord[aF];
File.Delete[ h
! File.Error => { Count[vLRU, error]; result ← failed; CONTINUE } ];
FSReport.ReportRemote[endFlushing, fName];
END;
IF result = flushed
THEN Count[vLRU, flushed];
END;
LRUOrder: INTERNAL PROC [list: REF UseRecord] RETURNS [first, last: REF UseRecord] =
BEGIN
Merge: PROC [list1, list2: REF UseRecord] RETURNS [mergeStart: REF UseRecord] =
BEGIN
IF list1 = NIL THEN {mergeStart ← list2; RETURN};
IF list2 = NIL THEN {mergeStart ← list1; RETURN};
IF BasicTime.Period[from: list1.used, to: list2.used] > 0
THEN {mergeEnd ← list1; list1 ← list1.next}
ELSE {mergeEnd ← list2; list2 ← list2.next};
mergeStart ← mergeEnd;
DO
IF list1 = NIL THEN {mergeEnd.next ← list2; EXIT};
IF list2 = NIL THEN {mergeEnd.next ← list1; EXIT};
IF BasicTime.Period[from: list1.used, to: list2.used] > 0
THEN {mergeEnd.next ← list1; list1 ← list1.next}
ELSE {mergeEnd.next ← list2; list2 ← list2.next};
mergeEnd ← mergeEnd.next;
ENDLOOP;
END;
maxLists: CARDINAL = 22; -- bits in word-address - 2
lists: ARRAY [0 .. maxLists] OF REF UseRecord ← ALL [NIL];
mergeEnd: REF UseRecord ← list;
UNTIL list = NIL DO
i: CARDINAL ← 0;
temp: REF UseRecord ← list; -- first element from list
list ← list.next; -- remove first element from list
temp.next ← NIL;
UNTIL lists[i] = NIL DO
temp ← Merge[temp, lists[i]];
lists[i] ← NIL;
i ← i+1;
ENDLOOP;
lists[i] ← temp;
ENDLOOP;
first ← NIL;
FOR i: CARDINAL IN [0 .. maxLists] DO
first ← Merge[first, lists[i]];
lists[i] ← NIL;
ENDLOOP;
last ← NIL;
FOR mergeEnd ← mergeEnd, mergeEnd.next UNTIL mergeEnd = NIL DO
last ← mergeEnd;
ENDLOOP;
END;
END.