-- CachedSpaceImpl.mesa (last edited by: McJones on: September 24, 1980 2:47 PM)

-- last edited by: Paul Rovner on: February 9, 1983 3:10 pm

-- Things to consider:
-- 1) To allow multi-MDS, move global data to monitored record

DIRECTORY
CachedSpace,
Frame USING [Alloc],
PilotSwitches USING [switches --.u--],
RuntimeInternal USING [MakeFsi],
SwapperPrograms;

CachedSpaceImpl: MONITOR
IMPORTS Frame, PilotSwitches, RuntimeInternal
EXPORTS CachedSpace, SwapperPrograms =
BEGIN OPEN CachedSpace;

CacheEntry: TYPE = RECORD [pCENext: PCE, desc: Desc];
PCE: TYPE = POINTER TO CacheEntry;
ICE: TYPE = [0..200--PDR, was 60--); -- algorithm assumes at least two entries

-- Monitor data:
rgCE: ARRAY ICE OF CacheEntry;
pCEMru: PCE;
pCEFree: PCE;

-- Interpretation of handles is not "strict": page may be any page of space
FindCacheEntry: INTERNAL PROC [space: Handle]
RETURNS [found: BOOLEAN, pCE: PCE] =
BEGIN
pCECur, pCEPrev: PCE;
FOR pCECur ← pCEMru, pCECur.pCENext WHILE pCECur # NIL DO
OPEN pCECur;
IF space.level = desc.level AND space.page IN
[desc.interval.page..desc.interval.page + desc.interval.count) THEN
GO TO Found;
pCEPrev ← pCECur;
REPEAT
Found =>
BEGIN
IF pCECur # pCEMru THEN
BEGIN
pCEPrev.pCENext ← pCENext;
pCENext ← pCEMru;
pCEMru ← pCECur
END;
RETURN[TRUE, pCECur]
END;
FINISHED => RETURN[FALSE, NIL];
ENDLOOP
END;

Delete: PUBLIC ENTRY PROC [space: Handle] =
BEGIN
found: BOOLEAN;
pCE: PCE;
[found, pCE] ← FindCacheEntry[space]; -- Assume pCEMru=pCE
IF found THEN
BEGIN --assert--
IF pCE.desc.dPinned THEN ERROR;
pCEMru ← pCE.pCENext;
pCE.pCENext ← pCEFree;
pCEFree ← pCE
END
END;

Get: PUBLIC ENTRY PROC [pDescResult: PDesc, space: Handle] =
BEGIN
found: BOOLEAN;
pCE: PCE;
[found, pCE] ← FindCacheEntry[space];
IF found THEN pDescResult↑ ← pCE.desc ELSE pDescResult.state ← missing
END;

Insert: PUBLIC ENTRY PROC [pDescVictim: PDesc, pDesc: PDesc] =
BEGIN
pCE, pCECur, pCEPrev: PCE;
IF FindCacheEntry[Handle[level: pDesc.level, page: pDesc.interval.page]].found THEN
ERROR; -- Assertion --
pDescVictim.dDirty ← FALSE;
IF pCEFree ~= NIL THEN -- Free cache entry is available; use it
{ pCE ← pCEFree; pCEFree ← pCEFree.pCENext }
ELSE
IF PilotSwitches.switches.u = down THEN
-- if utilityPilot, don’t mess with other entries.
pCE ← LOOPHOLE[Frame.Alloc[RuntimeInternal.MakeFsi[SIZE[CacheEntry]]]]
ELSE
BEGIN
-- Replace lru element, which can’t be same as mru since free chain is empty
pCE ← NIL;
FOR pCECur ← pCEMru, pCECur.pCENext WHILE pCECur.pCENext ~= NIL DO
IF ~pCECur.pCENext.desc.dPinned THEN
BEGIN pCE ← pCECur.pCENext; pCEPrev ← pCECur END
ENDLOOP;
IF pCE = NIL THEN ERROR; -- no unpinned entries => death
pCEPrev.pCENext ← pCE.pCENext;
IF pCE.desc.dDirty THEN pDescVictim↑ ← pCE.desc;
END;
pCE.pCENext ← pCEMru;
pCEMru ← pCE;
pCE.desc ← pDesc↑
END;

Update: PUBLIC ENTRY PROC [pDesc: PDesc] RETURNS [found: BOOLEAN] =
BEGIN
pCE: PCE;
[found, pCE] ← FindCacheEntry[
Handle[level: pDesc.level, page: pDesc.interval.page]];
IF found THEN { pCE.desc ← pDesc↑; pCE.desc.dDirty ← TRUE }
END;

BEGIN
pCE: PCE;
pCE ← pCEFree ← @rgCE[FIRST[ICE]];
THROUGH [FIRST[ICE]..LAST[ICE]) DO
pCE.pCENext ← pCE + SIZE[CacheEntry]; pCE ← pCE.pCENext
ENDLOOP;
rgCE[LAST[ICE]].pCENext ← pCEMru ← NIL
END

END.

June 1, 1978 3:00 PMMcJonesCreate file
June 8, 1978 10:32 AMMcJonesUpdate didn’t mark cache entry dirty
June 27, 1978 11:19 AMMcJonesAdd consistency check for no replaceable cache entries
September 9, 1978 2:55 PMMcJonesSuppress clearing of dDirty in Insert
August 29, 1979 4:51 PMLadnerInstall instrumentation
March 16, 1980 6:39 PMForrestTry expand cache hack again
May 7, 1980 1:30 PMForrestFrameOps=>Frame
July 11, 1980 4:45 PMGobbelIncrease size from 32 to 42 (?)
August 29, 1980 5:10 PMForrestRemove instrumentation
September 24, 1980 2:47 PMMcJonesIncrease size from 42 to 60