
<<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.