DIRECTORY BasicTime USING [earliestGMT, GMT, Period], BTree USING [Error], File USING [Delete, Error, FP, Handle, Open, Volume], FileBackdoor USING [SetFlusher], 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, FileBackdoor, 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: REF LRU _ NEW[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; FileBackdoor.SetFlusher[lru.vDesc.vol, MakePagesAvailable, NIL]; }; }; RecordUsage: PUBLIC PROC [fp: File.FP, time: GMT] = {}; OldestLruDate: PUBLIC ENTRY PROC RETURNS [date: BasicTime.GMT _ BasicTime.earliestGMT] = { IF lru.first # NIL THEN RETURN[lru.first.used]; }; 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 = { FileBackdoor.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. Bob Hagmann May 3, 1985 8:31:08 am PDT Russ Atkinson (RRA) October 17, 1985 1:33:23 pm PDT 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 Bob Hagmann January 29, 1985 3:43:06 pm PST Cedar 6.0 interface changes, } Bob Hagmann May 3, 1985 8:31:08 am PDT changes to: RecordUsage, OldestLruDate, DIRECTORY ʉ– "cedar" style˜šœ™Jšœ Ïmœ1™M˜MšžœžœžœŸ&˜JMšœ˜—Mšœ˜—š  œžœžœ˜Mšœ'žœžœ˜1Mšœžœžœ(˜8Mšœ˜—š   œžœžœžœžœ˜.šžœ žœžœ˜Mšœ™š   œžœžœžœžœž œ˜ašžœ žœž˜šœ ˜ Mšœ žœ+˜:M˜Mšœ˜—Mšžœžœ˜—Mšžœ žœžœ˜$Mšœ˜—M˜Mšœ:žœ˜?Mšœ ˜ M˜(Mšœ˜Mšœ˜—šž˜Mšœžœ˜"Mš žœ žœžœžœŸ˜*Mšœ˜Mšœžœ˜Mšžœžœžœžœ˜'Mšžœ˜—Mšžœžœ˜Mšœ˜—š   œž œžœ žœžœ˜>Mšœžœ˜ M˜Mšœ žœ˜ Mšœ˜Mšœžœ˜Mšœ˜M˜M˜šœ!˜!šœ˜Mšžœ˜Mšžœ˜ Mšžœ˜Mšžœ˜ Mšœ˜——˜7šœžœ ˜Mšžœ˜Mšžœ˜ Mšžœ˜Mšžœ˜ Mšœ˜——MšœP˜PMšžœ žœ žœžœ˜Bšžœžœžœ˜(Mšœ˜Mšœ˜Mšžœ˜ Mšœ˜—šžœžœ˜Mšœ%™%Mšœ˜Mšœ˜Mšžœ˜ Mšœ˜—šžœ1žœ˜:Mšœ˜Mšœ"˜"Mšžœ˜ Mšœ˜—Mšœ0˜0Mšœ,˜,šœ.˜.šœ˜MšœE˜E—Mšœ˜—M˜šœ˜šœ˜MšœDžœ ˜Q—Mšœ˜—Mšœ*˜*Mšœ˜Mšžœžœ˜Mšžœ žœžœ˜Mšœ˜—š  œžœžœ žœ žœ˜Gš  œžœžœ žœžœ˜QMšœžœ ˜Mšžœ žœžœžœ˜1Mšžœ žœžœžœ˜1šžœ7˜9Mšžœ)˜-Mšžœ*˜.—Mšœ˜šž˜Mšžœ žœžœžœ˜-Mšžœ žœžœžœ˜-šžœ7˜9Mšžœ'˜+Mšžœ(˜,—Mšœ˜Mšžœ˜—Mšœ˜—Mšœ žœŸ˜4Mš œžœžœžœ žœžœ˜:šžœžœž˜Mšœžœ˜Mšœ ˜ Mšœ˜Mšœ žœ˜šžœ žœž˜Mšœ˜Mšœ žœ˜M˜Mšžœ˜—Mšœ˜Mšžœ˜—Mšœžœ˜ šžœžœžœž˜%Mšœ˜Mšœ žœ˜Mšžœ˜—Mšœ˜——Mšœ˜M˜™+KšœÏr™—K™™&Kšœ ¡%™1—K™K™—…—|ÿ