-- file SymbolCache.Mesa
-- last edited by Satterthwaite, October 23, 1978 9:15 AM
DIRECTORY
AltoDefs: FROM "altodefs" USING [PageSize],
SegmentDefs: FROM "segmentdefs" USING [
FileSegmentAddress, FileSegmentHandle, InsufficientVM, InvalidFP, SwapIn,
SwapOut, Unlock],
Symbols: FROM "symbols" USING [HTIndex, HTRecord],
SymbolPack: FROM "symbolpack" USING [
bb, cacheInfo, ctxb, extb, fgTable, hashVec, ht, link, ltb, mdb, notifier,
NullNotifier, seb, sourceFile, ssb, stHandle, tb],
SymbolSegment: FROM "symbolsegment" USING [FGHeader, STHeader],
SymbolTable: FROM "symboltable" USING [Base, Handle],
SystemDefs: FROM "systemdefs" USING [AllocateHeapNode],
Table: FROM "table" USING [Base];
SymbolCache: PROGRAM
IMPORTS initial: SymbolPack, SegmentDefs, SystemDefs
EXPORTS SymbolTable SHARES SymbolTable =
BEGIN
OPEN SegmentDefs;
-- public interface
Missing: PUBLIC ERROR [FileSegmentHandle] = CODE;
TableForSegment: PUBLIC PROCEDURE [seg: FileSegmentHandle] RETURNS [SymbolTable.Handle] =
BEGIN
RETURN [SymbolTable.Handle[seg]]
END;
SegmentForTable: PUBLIC PROCEDURE [table: SymbolTable.Handle] RETURNS [FileSegmentHandle] =
BEGIN
RETURN [table.segment]
END;
IllegalBase: PUBLIC ERROR [base: SymbolTable.Base] = CODE;
Acquire: PUBLIC PROCEDURE [handle: SymbolTable.Handle]
RETURNS [base: SymbolTable.Base] =
BEGIN
node: CachePointer;
IF freeTables = NIL
THEN BEGIN base ← NEW initial; START base END
ELSE BEGIN base ← freeTables; freeTables ← freeTables.link END;
node ← MakeCacheEntry[handle];
base.link ← busyTables; busyTables ← base;
InstallTable[base, node];
END;
Release: PUBLIC PROCEDURE [base: SymbolTable.Base] =
BEGIN
node: CachePointer;
cacheNode: CachePointer = base.cacheInfo;
prev, table: SymbolTable.Base;
FOR node ← header.next, node.next UNTIL node = cacheNode
DO
IF node = free THEN ERROR IllegalBase[base];
ENDLOOP;
prev ← NIL;
FOR table ← busyTables, table.link UNTIL table = NIL
DO
IF table = base THEN
BEGIN
IF prev # NIL
THEN prev.link ← table.link
ELSE busyTables ← table.link;
EXIT
END;
prev ← table;
REPEAT
FINISHED => ERROR IllegalBase[base];
ENDLOOP;
FreeCacheEntry[cacheNode];
base.link ← freeTables; freeTables ← base;
END;
busyTables: SymbolTable.Base ← NIL;
freeTables: SymbolTable.Base ← initial;
cachePageLimit: CARDINAL ← 0;
CacheSize: PUBLIC PROCEDURE RETURNS [pages: CARDINAL] =
BEGIN
RETURN [cachePageLimit]
END;
SetCacheSize: PUBLIC PROCEDURE [pages: CARDINAL] =
BEGIN
cachePageLimit ← pages; TrimCache[cachePageLimit];
END;
suspended: BOOLEAN;
SuspendCache: PUBLIC PROCEDURE =
BEGIN
node: CachePointer;
WHILE unused # free DO ClearNode[unused ← unused.prev] ENDLOOP;
suspended ← TRUE;
FOR node ← header.next, node.next UNTIL node = free
DO Unlock[node.table]; SwapOut[node.table] ENDLOOP;
END;
RestartCache: PUBLIC PROCEDURE =
BEGIN
node: CachePointer;
base: SymbolTable.Base;
IF ~suspended THEN ERROR;
FOR node ← header.next, node.next UNTIL node = free
DO SwapIn[node.table] ENDLOOP;
FOR base ← busyTables, base.link UNTIL base = NIL
DO SetBases[base, base.cacheInfo]; base.notifier[base] ENDLOOP;
suspended ← FALSE;
END;
-- internal cache management
CacheNodes: CARDINAL = 15;
MaxCacheNodes: CARDINAL = 255;
LockTime: CARDINAL = 1;
CacheNode: TYPE = RECORD[
prev, next: CachePointer,
table: SymbolTable.Handle,
locked: BOOLEAN,
timeLeft: [0..LockTime],
refCount: [0..MaxCacheNodes]];
CachePointer: TYPE = POINTER TO CacheNode;
header, free, unused: CachePointer;
lockedPages: CARDINAL;
-- C A C H E O R G A N I Z A T I O N
-- The cache keeps track of segments in CacheNodes. The CacheNodes are
-- kept in a doubly-linked list and organized in three groups, separated
-- by three pointers: header, free, and unused. Ordered by the link
-- next, the list is organized as follows:
-- (header .. free) nodes attached to frames,
-- [free .. unused) nodes with segment but no frame,
-- [unused .. header) empty and available,
MakeCacheEntry: PROCEDURE [handle: SymbolTable.Handle] RETURNS [node: CachePointer] =
BEGIN
FOR node ← header.next, node.next UNTIL node = free
DO
IF node.table = handle THEN GO TO allocated;
REPEAT
allocated => NULL;
FINISHED =>
BEGIN
AgeNodes[];
FOR node ← free, node.next UNTIL node = unused
DO
IF node.table = handle THEN GO TO unflushed;
REPEAT
unflushed => Detach[node];
FINISHED =>
BEGIN node ← GetEmptyNode[]; node.table ← handle END;
ENDLOOP;
IF ~node.locked
THEN
BEGIN
retried: BOOLEAN ← FALSE;
TrimCache[MAX[cachePageLimit, handle.pages] - handle.pages];
SwapIn[handle !
InvalidFP => ERROR Missing[handle];
InsufficientVM =>
IF ~retried THEN
BEGIN
SuspendCache[]; RestartCache[]; retried ← TRUE; RESUME
END];
node.locked ← TRUE;
lockedPages ← lockedPages + handle.pages;
END;
Insert[node, free];
END;
ENDLOOP;
node.refCount ← node.refCount+1; RETURN
END;
FreeCacheEntry: PROCEDURE [node: CachePointer] =
BEGIN
IF (node.refCount ← node.refCount-1) = 0
THEN
BEGIN
Detach[node]; node.timeLeft ← LockTime;
Insert[node, free]; free ← node;
END;
END;
GetEmptyNode: PROCEDURE RETURNS [node: CachePointer] =
BEGIN
IF free = header
THEN node ← SystemDefs.AllocateHeapNode[SIZE[CacheNode]]
ELSE
BEGIN
IF unused = header THEN ClearNode[unused ← unused.prev];
node ← unused; Detach[node];
END;
node.refCount ← 0; node.locked ← FALSE;
RETURN
END;
Detach: PROCEDURE [node: CachePointer] =
BEGIN
IF node = free THEN free ← free.next;
IF node = unused THEN unused ← unused.next;
node.prev.next ← node.next; node.next.prev ← node.prev;
END;
Insert: PROCEDURE [node, position: CachePointer] =
BEGIN
node.prev ← position.prev; node.prev.next ← node;
node.next ← position; position.prev ← node;
END;
TrimCache: PROCEDURE [size: CARDINAL] =
BEGIN
WHILE (lockedPages > size OR size = 0) AND unused # free
DO ReleaseLock[unused ← unused.prev] ENDLOOP;
END;
AgeNodes: PROCEDURE =
BEGIN
node: CachePointer;
FOR node ← free, node.next UNTIL node = unused OR node.timeLeft = 0
DO
IF (node.timeLeft ← node.timeLeft-1) = 0 THEN ReleaseLock[node];
ENDLOOP;
END;
ReleaseLock: PROCEDURE [node: CachePointer] =
BEGIN
IF node.locked
THEN
BEGIN
Unlock[node.table]; node.locked ← FALSE;
lockedPages ← lockedPages - node.table.pages;
END;
END;
ClearNode: PROCEDURE [node: CachePointer] =
BEGIN
ReleaseLock[node]; -- SwapOut[node.table];
END;
-- symbol table setup
InstallTable: PROCEDURE [base: SymbolTable.Base, node: CachePointer] =
BEGIN
SetBases[base, node]; base.notifier ← base.NullNotifier; RETURN
END;
SetBases: PROCEDURE [base: SymbolTable.Base, node: CachePointer] =
BEGIN
b: POINTER = FileSegmentAddress[node.table];
tB: Table.Base = LOOPHOLE[b];
p: POINTER TO SymbolSegment.STHeader = b;
q: POINTER TO SymbolSegment.FGHeader;
base.cacheInfo ← node;
base.hashVec ←
DESCRIPTOR[b+p.hvBlock.offset, p.hvBlock.size/SIZE[Symbols.HTIndex]];
base.ht ←
DESCRIPTOR[b+p.htBlock.offset, p.htBlock.size/SIZE[Symbols.HTRecord]];
base.ssb ← b + p.ssBlock.offset;
base.seb ← tB + p.seBlock.offset;
base.ctxb ← tB + p.ctxBlock.offset;
base.mdb ← tB + p.mdBlock.offset;
base.bb ← tB + p.bodyBlock.offset;
base.tb ← tB + p.treeBlock.offset;
base.ltb ← tB + p.litBlock.offset;
base.extb ← tB + p.extBlock.offset;
base.stHandle ← p;
IF p.fgRelPgBase = 0 THEN base.sourceFile ← NIL
ELSE
BEGIN
q ← b + p.fgRelPgBase*AltoDefs.PageSize;
base.sourceFile ← LOOPHOLE[@q.sourceFile];
base.fgTable ← DESCRIPTOR[
b + p.fgRelPgBase*AltoDefs.PageSize + q.offset, q.length];
END;
END;
-- initialization
CacheEntries: ARRAY [0..CacheNodes] OF CacheNode;
Init: PROCEDURE =
BEGIN
j: INTEGER [0..CacheNodes];
START initial; initial.link ← NIL;
FOR j IN [0..CacheNodes]
DO
CacheEntries[j].next ← @CacheEntries[IF j=CacheNodes THEN 0 ELSE j+1];
CacheEntries[j].prev ← @CacheEntries[IF j=0 THEN CacheNodes ELSE j-1];
ENDLOOP;
header ← @CacheEntries[0];
free ← unused ← header.next;
lockedPages ← 0; suspended ← FALSE;
END;
Init[];
END.