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 = { GMT: TYPE = BasicTime.GMT; ROPE: TYPE = Rope.ROPE; UseRecord: TYPE = RECORD[next: REF UseRecord, fp: File.FP, used: GMT]; LRU: TYPE = RECORD[ vDesc: FSFileOps.VolumeDesc _ NIL, first: REF UseRecord _ NIL, killed, -- times killed sorts, -- number of lru lists made since last killed count, -- initial length of last lru list made cumCount, flushed, error, deleted, superseded, open: INT _ 0 -- since killed ]; lru: LRU; RegisterVolumeFlusher: PUBLIC ENTRY PROC [svDesc: FSFileOps.VolumeDesc] = { ENABLE UNWIND => NULL; IF svDesc = NIL THEN { -- kill any existing volume flusher IF lru.vDesc # NIL THEN KillFlusher[]; -- already is a volume flusher } ELSE { -- establish a new volume flusher lru.vDesc _ svDesc; File.SetFlusher[lru.vDesc.vol, MakePagesAvailable, NIL]; }; }; RecordUsage: PUBLIC PROC [fp: File.FP, time: GMT] = {}; MakePagesAvailable: ENTRY PROC [volume: File.Volume, nPages: INT, clientInfo: REF] RETURNS [ok: BOOL] = { ENABLE UNWIND => NULL; ok _ FALSE; IF lru.vDesc # NIL THEN { ENABLE BTree.Error, File.Error => { KillFlusher[]; CONTINUE }; ok _ FlushAnother[]; IF NOT ok THEN ok _ FlushAnother[]; -- make another lru list and try again }; }; KillFlusher: INTERNAL PROC = { File.SetFlusher[lru.vDesc.vol, NIL, NIL]; lru _ [NIL, NIL, lru.killed+1, 0, 0, 0, 0, 0, 0, 0, 0]; }; FlushAnother: INTERNAL PROC RETURNS [BOOL] = { IF lru.first = NIL THEN { GetFPandUsed: UNSAFE PROC [entry: FSBackdoor.EntryPtr] RETURNS [accept, stop: BOOL] = UNCHECKED { WITH e: entry^ SELECT FROM cached => { lru.first _ NEW [ UseRecord _ [lru.first, e.fp, e.used] ]; lru.count _ lru.count+1; }; ENDCASE => ERROR; RETURN [accept: FALSE, stop: FALSE]; }; lru.count _ 0; FSDir.EnumerateEntries[lru.vDesc, "[", all, GetFPandUsed, NIL]; lru.first _ LRUOrder[lru.first]; lru.cumCount _ lru.cumCount + lru.count; lru.sorts _ lru.sorts+1; }; DO victim: REF UseRecord = lru.first; IF victim = NIL THEN EXIT; -- time to stop lru.first _ victim.next; victim.next _ NIL; IF TryVictim[victim] THEN RETURN[TRUE]; ENDLOOP; RETURN [FALSE]; }; TryVictim: INTERNAL PROC [v: REF UseRecord] RETURNS [BOOL] = { fName: ROPE; t: FSBackdoor.EntryType; dirUsed: GMT; aF: FSLock.ActiveFile; entryFP: File.FP; h: File.Handle; nameBody: Rope.Text; version: FSBackdoor.Version; h _ File.Open[lru.vDesc.vol, v.fp ! File.Error => { IF why = unknownFile THEN lru.deleted _ lru.deleted+1 ELSE lru.error _ lru.error+1; GOTO failed; } ]; [nameBody, version] _ FSFileOps.GetNameBodyAndVersion[h ! FS.Error => { IF error.code = $badFP THEN lru.deleted _ lru.deleted+1 ELSE lru.error _ lru.error+1; GOTO failed; } ]; [t, dirUsed, entryFP, aF] _ FSDir.AcquireOldGName[lru.vDesc, nameBody, version]; IF t = notFound THEN { lru.deleted _ lru.deleted+1; GOTO failed }; IF aF = NIL OR aF.fileLock # none THEN { FSLock.ReleaseRecord[aF]; lru.open _ lru.open+1; GOTO failed; }; IF entryFP # v.fp THEN { FSLock.ReleaseRecord[aF]; lru.deleted _ lru.deleted+1; GOTO failed; }; IF BasicTime.Period[from: dirUsed, to: v.used ] < 0 THEN { FSLock.ReleaseRecord[aF]; lru.superseded _ lru.superseded+1; GOTO failed; }; fName _ FSBackdoor.MakeFName[nameBody, version]; FSReport.ReportRemote[startFlushing, fName]; FSDir.DeleteEntry[lru.vDesc, nameBody, version ! BTree.Error, File.Error => { FSLock.ReleaseRecord[aF]; FSReport.ReportRemote[endFlushing, fName] } ]; FSLock.ReleaseRecord[aF]; File.Delete[ h ! File.Error => { lru.error _ lru.error+1; FSReport.ReportRemote[endFlushing, fName]; GOTO failed } ]; FSReport.ReportRemote[endFlushing, fName]; lru.flushed _ lru.flushed+1; RETURN [TRUE]; EXITS failed => RETURN [FALSE]; }; LRUOrder: PROC [list: REF UseRecord] RETURNS [first: REF UseRecord] = { Merge: PROC [list1, list2: REF UseRecord] RETURNS [mergeStart: REF UseRecord] = { end: REF UseRecord; 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 {mergeStart _ list1; list1 _ list1.next} ELSE {mergeStart _ list2; list2 _ list2.next}; end _ mergeStart; DO IF list1 = NIL THEN {end.next _ list2; EXIT}; IF list2 = NIL THEN {end.next _ list1; EXIT}; IF BasicTime.Period[from: list1.used, to: list2.used] > 0 THEN {end.next _ list1; list1 _ list1.next} ELSE {end.next _ list2; list2 _ list2.next}; end _ end.next; ENDLOOP; }; maxLists: CARDINAL = 22; -- bits in word-address - 2 lists: ARRAY [0 .. maxLists] OF REF UseRecord _ ALL [NIL]; UNTIL list = NIL DO i: CARDINAL _ 0; first _ list; list _ list.next; first.next _ NIL; UNTIL lists[i] = NIL DO first _ Merge[first, lists[i]]; lists[i] _ NIL; i _ i+1; ENDLOOP; lists[i] _ first; ENDLOOP; first _ NIL; FOR i: CARDINAL IN [0 .. maxLists] DO first _ Merge[first, lists[i]]; lists[i] _ NIL; ENDLOOP; }; }. (FSFileSpaceImpl.mesa Copyright c 1984 by Xerox Corporation. All rights reserved. Russ Atkinson, November 7, 1984 11:13:05 am PST Space management variables and types Exported to FSFileOps Internal procedures flusher is turned on build a new LRU list wierd case, but I think it can happen Κ– "cedar" style˜šœ™Jšœ Οmœ1™L˜LšžœžœžœŸ&˜JLšœ˜—Lšœ˜—š  œžœžœ˜Lšœžœžœ˜)Lšœžœžœ(˜7Lšœ˜—š   œžœžœžœžœ˜.šžœ žœžœ˜Lšœ™š   œžœžœžœžœž œ˜ašžœ žœž˜šœ ˜ Lšœ žœ+˜:L˜Lšœ˜—Lšžœžœ˜—Lšžœ žœžœ˜$Lšœ˜—L˜Lšœ:žœ˜?Lšœ ˜ L˜(Lšœ˜Lšœ˜—šž˜Lšœžœ˜"Lš žœ žœžœžœŸ˜*Lšœ˜Lšœžœ˜Lšžœžœžœžœ˜'Lšžœ˜—Lšžœžœ˜Lšœ˜—š   œž œžœ žœžœ˜>Lšœžœ˜ L˜Lšœ žœ˜ Lšœ˜Lšœžœ˜Lšœ˜L˜L˜šœ!˜!šœ˜Lšžœ˜Lšžœ˜ Lšžœ˜Lšžœ˜ Lšœ˜——˜7šœžœ ˜Lšžœ˜Lšžœ˜ Lšžœ˜Lšžœ˜ Lšœ˜——LšœP˜PLšžœ žœ žœžœ˜Bšžœžœžœ˜(Lšœ˜Lšœ˜Lšžœ˜ Lšœ˜—šžœžœ˜Lšœ%™%Lšœ˜Lšœ˜Lšžœ˜ Lšœ˜—šžœ1žœ˜:Lšœ˜Lšœ"˜"Lšžœ˜ Lšœ˜—Lšœ0˜0Lšœ,˜,šœ.˜.šœ˜LšœE˜E—Lšœ˜—L˜šœ˜šœ˜LšœDžœ ˜Q—Lšœ˜—Lšœ*˜*Lšœ˜Lšžœžœ˜Lšžœ žœžœ˜Lšœ˜—š  œžœžœ žœ žœ˜Gš  œžœžœ žœžœ˜QLšœžœ ˜Lšžœ žœžœžœ˜1Lšžœ žœžœžœ˜1šžœ7˜9Lšžœ)˜-Lšžœ*˜.—Lšœ˜šž˜Lšžœ žœžœžœ˜-Lšžœ žœžœžœ˜-šžœ7˜9Lšžœ'˜+Lšžœ(˜,—Lšœ˜Lšžœ˜—Lšœ˜—Lšœ žœŸ˜4Lš œžœžœžœ žœžœ˜:šžœžœž˜Lšœžœ˜Lšœ ˜ Lšœ˜Lšœ žœ˜šžœ žœž˜Lšœ˜Lšœ žœ˜L˜Lšžœ˜—Lšœ˜Lšžœ˜—Lšœžœ˜ šžœžœžœž˜%Lšœ˜Lšœ žœ˜Lšžœ˜—Lšœ˜——Lšœ˜L˜—…—žΦ