-- FileCacheImpl.mesa (last edited by: Luniewski on: February 6, 1981 10:13 AM)
-- Last Edited by: Levin, December 8, 1982 9:45 pm
-- Last Edited by: Paul Rovner, February 16, 1983 2:53 pm
DIRECTORY
Environment USING [Base, wordsPerPage],
File USING [ID, nullID, PageNumber],
FileCache USING [PinnedAction],
FileInternal USING [Descriptor, FilePtr, PageGroup, ReadOnlyFilePtr],
FilerPrograms USING [],
Process USING [DisableAborts],
ResidentHeap USING [first64K, MakeNode],
SystemInternal USING [UniversalID],
Volume USING [ID],
Zone USING [nil];
FileCacheImpl: MONITOR
IMPORTS Process, ResidentHeap, Zone
EXPORTS FileCache, FilerPrograms =
BEGIN OPEN FileInternal;
-- General cache mechanism
Base: TYPE = Environment.Base;
base: Base = ResidentHeap.first64K; -- base pointer for CEptr's
Cache: TYPE = POINTER TO CacheRecord;
CacheRecord: TYPE = RECORD [
mru: CEptr, -- most recently used entry (head of lru chain)
free: CEptr, -- head of free chain
CleanUp: CacheCleanUpProc, -- proc to cleanup when an entry is replaced
cacheType: CacheType];
CacheType: TYPE = {file, pageGroup};
CacheEntry: TYPE = RECORD [
-- carefully arranged to not waste bits
next: CEptr, -- next entry in lru chain
pinned: BOOLEAN, -- TRUE if this cache entry is pinned
refCnt: [0..37777B), -- number of readlocks set by FindCacheEntry
body:
SELECT COMPUTED CacheType FROM
file => [fd: Descriptor, pgList: PageGroupCEptr],
pageGroup => [group: PageGroup, fileCacheEntry: FileCEptr],
ENDCASE];
CEptr: TYPE = Base RELATIVE POINTER TO CacheEntry;
FileCEptr: TYPE = Base RELATIVE POINTER TO file CacheEntry;
PageGroupCEptr: TYPE = Base RELATIVE POINTER TO pageGroup CacheEntry;
nilCEptr: CEptr = Zone.nil;
nilFileCEptr: FileCEptr = LOOPHOLE[nilCEptr];
nilPageGroupCEptr: PageGroupCEptr = LOOPHOLE[nilCEptr];
CacheCleanUpProc: TYPE = PROCEDURE [cePtr: CEptr];
NoCleanUp: CacheCleanUpProc; -- null case indicator (unbound control link)
returned: CONDITION;
-- Key for cache searches
CacheKey: TYPE = RECORD [
SELECT OVERLAID CacheType FROM
file => [fileID: File.ID],
pageGroup => [fileCacheEntry: FileCEptr, filePage: File.PageNumber],
ENDCASE];
-- The following code calculates the number of file cache entries to initially create. As the initial cache is allocated as one chunk out of the resident heap, it is best if the initial file cache use as close to an integral number of pages as possible.
PageSize: CARDINAL = Environment.wordsPerPage; -- for conciseness below
FCESize: CARDINAL = SIZE[file CacheEntry];
PGESize: CARDINAL = SIZE[pageGroup CacheEntry];
ResidentHeapImplOverhead: CARDINAL = 2;
-- Must be at least as large as the actual overhead imposed by ResidentHeapImpl
NumPages: CARDINAL =
(FCacheMinimumSize*FCESize + PGCacheMinimumSize*PGESize +
ResidentHeapImplOverhead + PageSize - 1)/PageSize;
-- number of pages to allocate initially
Slop: CARDINAL =
NumPages*PageSize - ResidentHeapImplOverhead - FCacheMinimumSize*FCESize -
PGCacheMinimumSize*PGESize;
-- extra space to be allocated as equally as possible to file and page group cache entries
FirstExtraFCEs: CARDINAL = (Slop/2)/FCESize;
FirstExtraPGEs: CARDINAL = (Slop/2)/PGESize;
LastSlop: CARDINAL = Slop - FirstExtraFCEs*FCESize - FirstExtraPGEs*PGESize;
ExtraFCEs: CARDINAL =
IF FCESize > PGESize THEN FirstExtraFCEs
ELSE FirstExtraFCEs + LastSlop/FCESize;
ExtraPGEs: CARDINAL =
IF PGESize >= FCESize THEN FirstExtraPGEs
ELSE FirstExtraPGEs + LastSlop/PGESize;
-- File descriptor cache
FCache: Cache;
FCacheRecord: CacheRecord;
FCacheIndex: TYPE = [0..FCacheSize);
-- There are 4 pinned entries for each logical volume of the correct type, 1 for physical volumes, and 1 for logical volumes of the "wrong" type.
FCacheMinimumSize: CARDINAL = 200--PDR was 40--; -- must be 2 or greater
FCacheSize: CARDINAL = FCacheMinimumSize + ExtraFCEs;
FCacheCleanUp: INTERNAL CacheCleanUpProc =
BEGIN -- flush corresponding entries from page group cache
WHILE RemoveCacheEntry[PGCache, cePtr] DO NULL ENDLOOP
END;
-- Page Group cache
PGCache: Cache;
PGCacheRecord: CacheRecord;
PGCacheIndex: TYPE = [0..PGCacheSize);
PGCacheMinimumSize: CARDINAL = 220--PDR was 50--; -- must be 2 or greater
PGCacheSize: CARDINAL = PGCacheMinimumSize + ExtraPGEs;
GetFilePtrs: PUBLIC ENTRY PROCEDURE [count: CARDINAL, fileID: File.ID]
RETURNS [success: BOOLEAN, fD: FileInternal.FilePtr] =
BEGIN
fEntry: CEptr;
key: CacheKey ← [file[fileID]];
[success, fEntry] ← FindCacheEntry[get, count, FCache, @key];
IF success THEN WITH base[fEntry] SELECT file FROM file => fD ← @fd; ENDCASE;
END;
ReturnFilePtrs: PUBLIC ENTRY PROCEDURE [
count: CARDINAL, fD: FileInternal.ReadOnlyFilePtr] =
BEGIN
key: CacheKey ← [file[fD.fileID]];
[] ← FindCacheEntry[return, count, FCache, @key];
END;
SetFile: PUBLIC ENTRY PROCEDURE [fd: Descriptor, pinned: BOOLEAN] =
BEGIN
fEntry: CEptr;
key: CacheKey ← [file[fd.fileID]];
ce: CacheEntry ← [nilCEptr, pinned, 0, file[fd, nilPageGroupCEptr]];
SetCacheEntry[FCache, @ce];
fEntry ← FindCacheEntry[locate, 0, FCache, @key].ceptr;
WITH fE: base[fEntry] SELECT file FROM file => fE.fd ← fd; ENDCASE;
END;
FlushFile: PUBLIC ENTRY PROCEDURE [fileID: File.ID] =
BEGIN
found: BOOLEAN;
fEntry: CEptr;
key: CacheKey ← [file[fileID]];
[found, fEntry] ← FindCacheEntry[locate, 0, FCache, @key];
IF found THEN [] ← RemoveCacheEntry[FCache, fEntry];
END;
GetPageGroup: PUBLIC ENTRY PROCEDURE [
fileID: File.ID, filePage: File.PageNumber]
RETURNS [success: BOOLEAN, pg: PageGroup] =
BEGIN
fEntry, pgEntry: CEptr;
key: CacheKey ← [file [fileID]];
[success, fEntry] ← FindCacheEntry[locate, 0, FCache, @key];
IF ~success THEN RETURN;
key ← [pageGroup[LOOPHOLE[fEntry], filePage]];
[success, pgEntry] ← FindCacheEntry[locate, 0, PGCache, @key];
IF success THEN
WITH base[pgEntry] SELECT pageGroup FROM pageGroup => pg ← group; ENDCASE;
END;
SetPageGroup: PUBLIC ENTRY PROCEDURE [
fileID: File.ID, group: PageGroup, pinned: BOOLEAN] =
BEGIN
success: BOOLEAN;
fEntry: CEptr;
key: CacheKey ← [file[fileID]];
ce: CacheEntry;
[success, fEntry] ← FindCacheEntry[locate, 0, FCache, @key];
IF ~success THEN ERROR;
ce ← [nilCEptr, pinned, 0, pageGroup[group, LOOPHOLE[fEntry]]];
SetCacheEntry[PGCache, @ce];
END;
FlushFilesOnVolume: PUBLIC ENTRY PROCEDURE [
lvID: Volume.ID, pin: FileCache.PinnedAction] =
BEGIN
foundAny: BOOLEAN ← TRUE;
WHILE foundAny DO
foundAny ← FALSE;
FOR current: CEptr ← FCache.mru, base[current].next
WHILE current ~= nilCEptr DO
WITH fileEntry: base[current] SELECT FCache.cacheType FROM
file =>
IF fileEntry.fd.volumeID = lvID THEN
IF fileEntry.pinned AND pin = error THEN ERROR
ELSE IF NOT (fileEntry.pinned AND pin = keep) THEN
BEGIN
foundAny ← TRUE;
[] ← RemoveCacheEntry[FCache, current]
END;
ENDCASE => ERROR;
ENDLOOP;
ENDLOOP;
END;
-- Utility routines
IsMatch: INTERNAL PROCEDURE [
cacheType: CacheType, key: POINTER TO CacheKey, entry: CEptr]
RETURNS [BOOLEAN] = INLINE
BEGIN
RETURN[
WITH base[entry] SELECT cacheType FROM
file => -- compare the two file ID's for equality
LOOPHOLE[key.fileID, SystemInternal.UniversalID].sequence =
LOOPHOLE[fd.fileID, SystemInternal.UniversalID].sequence AND
LOOPHOLE[key.fileID, SystemInternal.UniversalID].processor.c =
LOOPHOLE[fd.fileID, SystemInternal.UniversalID].processor.c AND
LOOPHOLE[key.fileID, SystemInternal.UniversalID].processor.b =
LOOPHOLE[fd.fileID, SystemInternal.UniversalID].processor.b AND
LOOPHOLE[key.fileID, SystemInternal.UniversalID].processor.a =
LOOPHOLE[fd.fileID, SystemInternal.UniversalID].processor.a,
pageGroup => key.fileCacheEntry = fileCacheEntry AND
key.filePage IN [group.filePage..group.nextFilePage),
ENDCASE => -- never happens-- FALSE];
END;
GetMru: PROCEDURE [cacheType: CacheType, key: POINTER TO CacheKey]
RETURNS [LONG POINTER TO CEptr] = INLINE
BEGIN
RETURN[
SELECT cacheType FROM
file => @FCache.mru,
pageGroup => LOOPHOLE[@(base[key.fileCacheEntry]).pgList]
ENDCASE => ERROR]
END;
-- FindCacheEntry searches for an entry in the indicated cache having the indicated key, and returns the specified number of pointers to it (i.e. a pointer that may be copied that many times). If the pointers will be passed outside the monitor, op = get, and a later matching call with op = return must occur when the client discards the pointers; these adjust the refCnt of the entry appropriately. If only the contents of the entry are passed outside the monitor, op = locate, and the refCnt is not incremented.
lastMissedFileID: File.ID ← File.nullID; -- last file ID searched for and missed
FindCacheEntry: INTERNAL PROCEDURE [
op: {get, return, locate}, count: CARDINAL, cache: Cache,
key: POINTER TO CacheKey]
RETURNS [success: BOOLEAN, ceptr: CEptr] =
BEGIN OPEN cache;
current: CEptr;
mru: LONG POINTER TO CEptr;
previous: CEptr;
-- If this is a file search, see if we KNOW that this file entry is not here
SELECT cacheType FROM
file => -- compare the two file ID's for equality
IF LOOPHOLE[key.fileID, SystemInternal.UniversalID].sequence =
LOOPHOLE[lastMissedFileID, SystemInternal.UniversalID].sequence
THEN IF LOOPHOLE[key.fileID, SystemInternal.UniversalID].processor =
LOOPHOLE[lastMissedFileID, SystemInternal.UniversalID].processor
THEN RETURN[FALSE, nilCEptr];
ENDCASE;
previous ← nilCEptr;
mru ← GetMru[cacheType, key];
current ← mru↑;
WHILE current ~= nilCEptr DO
OPEN base[current];
IF IsMatch[cacheType, key, current] THEN -- found the matching cache entry
BEGIN
IF previous ~= nilCEptr THEN -- promote it to mru
{base[previous].next ← next; next ← mru↑; mru↑ ← current};
SELECT op FROM
get => refCnt ← refCnt + count;
return => IF (refCnt ← refCnt - count) = 0 THEN BROADCAST returned;
ENDCASE;
SELECT cacheType FROM
file => lastMissedFileID ← File.nullID;
ENDCASE;
RETURN[TRUE, current]
END;
previous ← current;
current ← next;
ENDLOOP;
SELECT cacheType FROM
file => lastMissedFileID ← key.fileID;
ENDCASE;
RETURN[FALSE, nilCEptr];
END;
SetCacheEntry: INTERNAL PROCEDURE [
cache: Cache, newEntry: POINTER TO CacheEntry] =
BEGIN OPEN cache;
entry, lastPtr, previous: CEptr;
key: CacheKey;
spliceOutMru, spliceInMru: LONG POINTER TO CEptr;
-- Set key and keep the "cache" of recently missed guys up to date
WITH newEntry SELECT cacheType FROM
file => BEGIN
key ← CacheKey[file[fd.fileID]];
IF LOOPHOLE[fd.fileID, SystemInternal.UniversalID].sequence =
LOOPHOLE[lastMissedFileID, SystemInternal.UniversalID].sequence
THEN IF LOOPHOLE[fd.fileID, SystemInternal.UniversalID].processor =
LOOPHOLE[lastMissedFileID, SystemInternal.UniversalID].processor
THEN lastMissedFileID ← File.nullID;
END;
pageGroup => key ← CacheKey[pageGroup[fileCacheEntry, group.filePage]];
ENDCASE;
previous ← nilCEptr;
spliceInMru ← GetMru[cacheType, @key];
spliceOutMru ← NIL;
FOR current: CEptr ← spliceInMru↑, base[current].next
WHILE current ~= nilCEptr DO
IF IsMatch[cacheType, @key, current] THEN
BEGIN
base[current].refCnt ← base[current].refCnt + newEntry.refCnt;
base[current].pinned ← base[current].pinned OR newEntry.pinned;
IF previous ~= nilCEptr THEN
BEGIN
-- must move current to mru (ELSE clause would be to move mru (= current) to
-- mru - a no-op).
base[previous].next ← base[current].next;
base[current].next ← spliceInMru↑;
spliceInMru↑ ← current;
END;
RETURN;
END;
previous ← current;
ENDLOOP;
IF free ~= nilCEptr THEN -- Steal a free entry if they exist
BEGIN entry ← free; free ← base[free].next; END
ELSE
BEGIN -- Must find the LRU replacable entry
entry ← lastPtr ← previous ← nilCEptr;
SELECT cacheType FROM
file =>
FOR fPtr: FileCEptr ← LOOPHOLE[(spliceOutMru ← spliceInMru)↑],
LOOPHOLE[base[fPtr].next] WHILE fPtr ~= nilCEptr DO
IF base[fPtr].refCnt = 0 AND ~base[fPtr].pinned THEN {
previous ← lastPtr; entry ← fPtr};
lastPtr ← fPtr;
ENDLOOP;
pageGroup =>
FOR fPtr: FileCEptr ← LOOPHOLE[FCache.mru], LOOPHOLE[base[fPtr].next]
WHILE fPtr ~= nilCEptr DO
lastPtr ← nilCEptr;
FOR pgPtr: PageGroupCEptr ← base[fPtr].pgList, LOOPHOLE[base[
pgPtr].next] WHILE pgPtr ~= nilCEptr DO
IF base[pgPtr].refCnt = 0 AND ~base[pgPtr].pinned THEN
BEGIN
spliceOutMru ← LOOPHOLE[@(base[fPtr]).pgList];
previous ← lastPtr;
entry ← pgPtr;
END;
lastPtr ← pgPtr;
ENDLOOP;
ENDLOOP;
ENDCASE => ERROR;
IF entry = nilCEptr THEN
SELECT cacheType FROM -- make a new cache entry
file => entry ← ResidentHeap.MakeNode[SIZE[file CacheEntry]].node;
pageGroup =>
entry ← ResidentHeap.MakeNode[SIZE[pageGroup CacheEntry]].node;
ENDCASE => ERROR
ELSE
BEGIN -- remove the LRU entry (= entry)
IF CleanUp # NoCleanUp THEN CleanUp[entry]; -- clean up for removal
-- Splice this entry ouyt of the list, special casing if it is MRU
IF previous ~= nilCEptr THEN base[previous].next ← base[entry].next
ELSE spliceOutMru↑ ← base[entry].next;
END;
END;
WITH newEntry SELECT cacheType FROM
file =>
base[entry] ←
[next: spliceInMru↑, pinned: newEntry.pinned, refCnt: newEntry.refCnt,
body: file[fd: fd, pgList: nilPageGroupCEptr]];
pageGroup =>
base[entry] ←
[next: spliceInMru↑, pinned: newEntry.pinned, refCnt: newEntry.refCnt,
body: pageGroup[group: group, fileCacheEntry: fileCacheEntry]];
ENDCASE;
spliceInMru↑ ← entry; -- Complete splicing in the entry as MRU
END;
RemoveCacheEntry: INTERNAL PROCEDURE [cache: Cache, fce: CEptr]
RETURNS [success: BOOLEAN] =
BEGIN OPEN cache;
current, previous: CEptr;
mru: LONG POINTER TO CEptr ←
IF cacheType = file THEN @FCache.mru
ELSE LOOPHOLE[@(base[LOOPHOLE[fce, FileCEptr]]).pgList];
DO
current ← mru↑; -- start search with most-recently-used
WHILE current ~= nilCEptr DO
IF WITH base[current] SELECT cacheType FROM
file => current = fce,
pageGroup => fileCacheEntry = fce,
ENDCASE => FALSE -- (never happens)
THEN EXIT;
previous ← current;
current ← base[current].next; -- advance down LRU chain
REPEAT FINISHED => RETURN[FALSE]; -- search failed
ENDLOOP;
IF base[current].refCnt = 0 THEN EXIT;
WAIT returned; -- entry busy: try again when activity subsides
ENDLOOP;
IF CleanUp ~= NoCleanUp THEN CleanUp[current]; -- clean up entry for removal
IF current = mru↑ -- remove current from lru chain
THEN mru↑ ← base[current].next
ELSE base[previous].next ← base[current].next;
base[current].next ← free;
free ← current; -- put on free chain
RETURN[TRUE];
END;
Initialize: PROCEDURE =
BEGIN
FCacheArray: LONG DESCRIPTOR FOR ARRAY FCacheIndex OF file CacheEntry;
PGCacheArray: LONG DESCRIPTOR FOR
ARRAY PGCacheIndex OF pageGroup CacheEntry;
node: CEptr;
i: CARDINAL;
Process.DisableAborts[@returned];
node ← ResidentHeap.MakeNode[ -- storage for the initial caches
NumPages*PageSize-ResidentHeapImplOverhead, a1].node;
FCache ← @FCacheRecord;
FCache.cacheType ← file;
FCache.mru ← nilCEptr;
FCache.CleanUp ← FCacheCleanUp;
FCache.free ← node;
FCacheArray ← DESCRIPTOR[@base[FCache.free], FCacheSize];
FOR i IN FCacheIndex DO
-- set up free chain
FCacheArray[i].next ←
IF i = LAST[FCacheIndex] THEN nilCEptr ELSE (node ← node + FCESize)
ENDLOOP;
node ← node + FCESize;
-- start the page group cache after the last file cache entry
PGCache ← @PGCacheRecord;
PGCache.cacheType ← pageGroup;
PGCache.mru ← nilCEptr;
PGCache.CleanUp ← NoCleanUp;
PGCache.free ← node;
PGCacheArray ← DESCRIPTOR[@base[PGCache.free], PGCacheSize];
FOR i IN PGCacheIndex DO
-- set up free chain
PGCacheArray[i].next ←
IF i = LAST[PGCacheIndex] THEN nilCEptr ELSE (node ← node + PGESize)
ENDLOOP;
END;
Initialize[];
END.
LOG
Time: April 20, 1978 3:09 PM By: Redell Action: Created file
Time: May 4, 1978 1:32 PM By: Redell Action: bug: get free entry => refCnt ← 0
Time: July 25, 1978 1:31 PM By: Redell Action: clean crash if cache fills up with pinned entries.
Time: September 11, 1978 5:42 PM By: Redell Action: Fixed flush to wait if I/O in progress. Re-did lost edits to expand cache size to 32 entries(!)
Time: August 29, 1979 4:49 PM By: Ladner Action: installed cache instrumentation
Time: February 14, 1980 7:39 PM By: Gobbel Action: Fixed bug in UtilityPilot mode operation: forgot to zero refcnt when getting a new entry
Time: May 16, 1980 9:39 AM By: Luniewski Action: FrameOps -> Frame.
Time: May 23, 1980 12:08 PM By: Luniewski Action: Added FlushFilesOnVolume and CacheEntry.pinned field. Modified to use ResidentHeap for cache storage and relative pointers for internal cache pointers.
Time: September 3, 1980 2:07 PM By: Luniewski Action: Speeded up algorithm by adding a fast pre-search to SetCacheEntry, chaining page group entries off of the corresponding file cache entry and adding an internal, INLINE, UID comparer program. Deleted performance monitoring code. Diabled aborts on condition variable.
Time: September 17, 1980 4:10 PM By: Yokota Action: mru is converted to spliceInMru and spliceOutMru.
Time: December 1, 1980 4:16 PM By: Luniewski Action: Made initial allocation request correct. Expanded UIDCompare inline because the compiler did a lousy job of it (the algorithm also was changed to take advantage of the definition of a UID as a processor ID and a sequence nr. by comapring the sequence nr.'s first).
Time: February 6, 1981 10:13 AM By: Luniewski Action: Make ReturnFilePtrs take a FileInternal.ReadOnlyFilePtr as first step towards haveing the external interface deal with these exclusively.
Time: December 8, 1982 9:44 pm By: Levin Action: SetFile now ensures that the argument descriptor appears in the cache. Previously, if an entry for the file appeared, the size and attributes were not updated.