-- file SymbolCache.Mesa
-- last edited by Bruce, August 27, 1980 6:21 PM
DIRECTORY
AltoDefs: TYPE USING [PageSize],
SegmentDefs USING [FileSegmentObject, InsufficientVM],
Segments: TYPE USING [
Address, SHandle, SegmentAddress, SwapIn, SwapOut, Unlock, SwapProblem],
Symbols: TYPE USING [HTIndex, HTRecord, MDIndex],
SymbolPack: TYPE USING [
bb, cacheInfo, ctxb, extb, extLimit, fgTable, hashVec, ht, link, ltb,
mainCtx, mdb, mdLimit, notifier, NullNotifier, seb, sourceFile, ssb,
stHandle, tb],
SymbolSegment: TYPE USING [ExtIndex, FGHeader, STHeader],
SymbolTable: TYPE USING [Base],
Storage: TYPE USING [Node],
Table: TYPE USING [Base];
SymbolCache: PROGRAM
IMPORTS initial: SymbolPack, SegmentDefs, Segments, Storage
EXPORTS SymbolTable =
BEGIN
-- public interface
Object: PUBLIC TYPE = SegmentDefs.FileSegmentObject;
Handle: TYPE = Segments.SHandle;
Missing: PUBLIC ERROR [Handle] = CODE;
TableForSegment: PUBLIC PROC [seg: Segments.SHandle] RETURNS [Handle] = {
RETURN [seg]};
SegmentForTable: PUBLIC PROC [table: Handle] RETURNS [Segments.SHandle] = {
RETURN [table]};
IllegalBase: PUBLIC ERROR [base: SymbolTable.Base] = CODE;
Acquire: PUBLIC PROC [handle: Handle] RETURNS [base: SymbolTable.Base] = {
node: CachePointer;
IF freeTables = NIL
THEN {base ← NEW initial; START base}
ELSE {base ← freeTables; freeTables ← freeTables.link};
node ← MakeCacheEntry[handle];
base.link ← busyTables; busyTables ← base;
InstallTable[base, node]};
Release: PUBLIC PROC [base: SymbolTable.Base] = {
node: CachePointer;
cacheNode: CachePointer = base.cacheInfo;
prev: SymbolTable.Base;
FOR node ← header.next, node.next UNTIL node = cacheNode
DO IF node = free THEN ERROR IllegalBase[base] ENDLOOP;
prev ← NIL;
FOR table: SymbolTable.Base ← busyTables, table.link UNTIL table = NIL
DO
IF table = base
THEN {
IF prev # NIL THEN prev.link ← table.link ELSE busyTables ← table.link;
EXIT};
prev ← table;
REPEAT
FINISHED => ERROR IllegalBase[base];
ENDLOOP;
FreeCacheEntry[cacheNode];
base.link ← freeTables; freeTables ← base};
busyTables: SymbolTable.Base ← NIL;
freeTables: SymbolTable.Base ← initial;
cachePageLimit: CARDINAL ← 0;
CacheSize: PUBLIC PROC RETURNS [pages: CARDINAL] = {RETURN [cachePageLimit]};
SetCacheSize: PUBLIC PROC [pages: CARDINAL] = {
cachePageLimit ← pages; TrimCache[cachePageLimit]};
suspended: BOOLEAN;
SuspendCache: PUBLIC PROC = {
WHILE unused # free DO ClearNode[unused ← unused.prev] ENDLOOP;
suspended ← TRUE;
FOR node: CachePointer ← header.next, node.next UNTIL node = free
DO Segments.Unlock[node.table]; Segments.SwapOut[node.table] ENDLOOP};
RestartCache: PUBLIC PROC = {
IF ~suspended THEN ERROR;
FOR node: CachePointer ← header.next, node.next UNTIL node = free
DO Segments.SwapIn[node.table] ENDLOOP;
FOR base: SymbolTable.Base ← busyTables, base.link UNTIL base = NIL
DO SetBases[base, base.cacheInfo]; base.notifier[base] ENDLOOP;
suspended ← FALSE};
-- internal cache management
CacheNodes: CARDINAL = 15;
MaxCacheNodes: CARDINAL = 255;
LockTime: CARDINAL = 1;
CacheNode: TYPE = RECORD[
prev, next: CachePointer,
table: Handle,
locked: BOOLEAN,
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: PROC [handle: Handle] RETURNS [node: CachePointer] = {
FOR node ← header.next, node.next UNTIL node = free
DO
IF node.table = handle THEN GO TO allocated;
REPEAT
allocated => NULL;
FINISHED => {
FOR node ← free, node.next UNTIL node = unused
DO
IF node.table = handle THEN GO TO unflushed;
REPEAT
unflushed => Detach[node];
FINISHED => {node ← GetEmptyNode[]; node.table ← handle};
ENDLOOP;
IF ~node.locked
THEN {
retried: BOOLEAN ← FALSE;
TrimCache[MAX[cachePageLimit, handle.pages] - handle.pages];
Segments.SwapIn[handle !
Segments.SwapProblem[] => ERROR Missing[handle];
SegmentDefs.InsufficientVM =>
IF ~retried THEN {SuspendCache[]; RestartCache[]; retried ← TRUE; RESUME}];
node.locked ← TRUE;
lockedPages ← lockedPages + handle.pages};
Insert[node, free]};
ENDLOOP;
node.refCount ← node.refCount+1; RETURN};
FreeCacheEntry: PROC [node: CachePointer] = {
IF (node.refCount ← node.refCount-1) = 0
THEN {
Detach[node]; ReleaseLock[node];
Insert[node, free]; free ← node}};
GetEmptyNode: PROC RETURNS [node: CachePointer] = {
IF free = header
THEN node ← Storage.Node[SIZE[CacheNode]]
ELSE {
IF unused = header THEN ClearNode[unused ← unused.prev];
node ← unused; Detach[node]};
node.refCount ← 0; node.locked ← FALSE;
RETURN};
Detach: PROC [node: CachePointer] = {
IF node = free THEN free ← free.next;
IF node = unused THEN unused ← unused.next;
node.prev.next ← node.next; node.next.prev ← node.prev};
Insert: PROC [node, position: CachePointer] = {
node.prev ← position.prev; node.prev.next ← node;
node.next ← position; position.prev ← node};
TrimCache: PROC [size: CARDINAL] = {
WHILE (lockedPages > size OR size = 0) AND unused # free
DO ReleaseLock[unused ← unused.prev] ENDLOOP};
ReleaseLock: PROC [node: CachePointer] = {
IF node.locked
THEN {
node.table.inuse ← TRUE;
Segments.Unlock[node.table]; node.locked ← FALSE;
lockedPages ← lockedPages - node.table.pages}};
ClearNode: PROC [node: CachePointer] = {
ReleaseLock[node]; --Segments.SwapOut[node.table]--};
-- symbol table setup
InstallTable: PROC [base: SymbolTable.Base, node: CachePointer] = {
SetBases[base, node]; base.notifier ← base.NullNotifier};
SetBases: PROC [base: SymbolTable.Base, node: CachePointer] = {
b: Segments.Address = Segments.SegmentAddress[node.table];
tB: Table.Base = LOOPHOLE[b];
p: LONG POINTER TO SymbolSegment.STHeader = b;
q: LONG POINTER TO SymbolSegment.FGHeader;
base.cacheInfo ← node;
base.hashVec ← b+p.hvBlock.offset;
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.mdLimit ← FIRST[Symbols.MDIndex] + p.mdBlock.size;
base.extLimit ← FIRST[SymbolSegment.ExtIndex] + p.extBlock.size;
base.mainCtx ← p.outerCtx; base.stHandle ← p;
IF p.fgRelPgBase = 0 OR node.table.pages <= p.fgRelPgBase
THEN {base.sourceFile ← NIL; base.fgTable ← NIL}
ELSE {
offset: CARDINAL = LOOPHOLE[
@(NIL[POINTER TO SymbolSegment.FGHeader]).sourceFile];
q ← b + p.fgRelPgBase*AltoDefs.PageSize;
base.sourceFile ← (b + p.fgRelPgBase*AltoDefs.PageSize) + offset;
base.fgTable ← DESCRIPTOR[
b + p.fgRelPgBase*AltoDefs.PageSize + q.offset, q.length]}};
-- initialization
CacheEntries: ARRAY [0..CacheNodes] OF CacheNode;
Init: PROC = {
START initial; initial.link ← NIL;
FOR j: INTEGER [0..CacheNodes] 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};
Init[];
END.