DIRECTORY
PrincOps: TYPE USING [wordsPerPage],
FS: TYPE USING [Read, OpenFile, SameFile],
FileSegment: TYPE USING [Span],
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 [Base, ExtIndex, FGHeader, STHeader],
SymbolTable: TYPE USING [Base, Handle, anySpan],
VM: TYPE USING [Free, Allocate, AddressForPageNumber, Interval, CantAllocate];

SymbolCache: MONITOR  -- protects the cache of global frames for symbol tables
IMPORTS initial: SymbolPack, FS, VM
EXPORTS SymbolTable = {


Handle: TYPE = SymbolTable.Handle;

Missing: PUBLIC ERROR [Handle] = CODE;
IllegalBase: PUBLIC ERROR [base: SymbolTable.Base] = CODE;


Acquire: PUBLIC ENTRY PROC [handle: Handle] RETURNS [base: SymbolTable.Base] = {
ENABLE UNWIND => NULL;
node: CachePointer;
interval: VM.Interval;
{
node _ MakeCacheEntry[handle
! VM.CantAllocate => {interval _ bestInterval; GOTO cantAllocate}];
IF freeTables = NIL
THEN {base _ NEW initial; START base; Bump[@stats.nNew]}
ELSE {base _ freeTables; freeTables _ freeTables.link};
base.link _ busyTables;  busyTables _ base;
InstallTable[base, node];
EXITS
cantAllocate => RETURN WITH ERROR VM.CantAllocate[interval];
};
Bump[@stats.nAcquire];
};

Release: PUBLIC ENTRY PROC [base: SymbolTable.Base] = {
ENABLE UNWIND => {NULL};
cacheNode: CachePointer = LOOPHOLE[base.cacheInfo, CachePointer];  -- XXX BEWARE
prev: SymbolTable.Base;
FOR node: CachePointer _ header.next, node.next UNTIL node = cacheNode DO
IF node = free THEN RETURN WITH 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 => RETURN WITH ERROR IllegalBase[base];
ENDLOOP;
FreeCacheEntry[cacheNode];
base.link _ freeTables;  freeTables _ base;  Bump[@stats.nRelease]};


Locked: PUBLIC ERROR [handle: SymbolTable.Handle, nLocks: NAT] = CODE;

Forget: PUBLIC ENTRY PROC [handle: SymbolTable.Handle] = {ENABLE UNWIND => NULL;
FID: PROC [h: SymbolTable.Handle] RETURNS [FS.OpenFile] = INLINE {RETURN [[h.file]]};
OverLap: PROC [s1, s2: FileSegment.Span] RETURNS [BOOL] = INLINE {
RETURN [IF s1.base <= s2.base
THEN s1.base + s1.pages > s2.base
ELSE s1.base < s2.base + s2.pages];
};

nLocks: INT _ 0;
prev: CachePointer;
FOR node: CachePointer _ unused.prev, prev UNTIL node = header DO
prev _ node.prev;
IF FS.SameFile[FID[handle], FID[node.table]]
AND (handle.span = SymbolTable.anySpan OR OverLap[handle.span, node.table.span])
THEN {
IF node.refCount # 0
THEN nLocks _ nLocks + node.refCount
ELSE ReleaseCacheEntry[node];
};
ENDLOOP;
IF nLocks # 0 THEN RETURN WITH ERROR Locked[handle, nLocks];
};

BaseToHandle: PUBLIC ENTRY PROC [base: SymbolTable.Base]
RETURNS [SymbolTable.Handle] = {
ENABLE UNWIND => NULL;
cacheNode: CachePointer = LOOPHOLE[base.cacheInfo, CachePointer];  -- XXX BEWARE
RETURN[cacheNode.table];
};


busyTables: SymbolTable.Base _ NIL;
freeTables: SymbolTable.Base _ initial;

cachePageLimit: INT _ 0;  -- number of pages for symbol tables

CacheSize: PUBLIC PROC RETURNS [pages: CARDINAL] = {RETURN [cachePageLimit]};

SetCacheSize: PUBLIC ENTRY PROC [pages: CARDINAL] = {
ENABLE UNWIND => NULL;
cachePageLimit _ pages;
};



takingStatistics: BOOL = TRUE;
Count: TYPE = INT _ 0;
stats: RECORD [nAcquire, nNew, nRelease: Count] _ [];

Bump: PROC [p: POINTER TO Count, delta: Count _ 1] = INLINE {
IF takingStatistics THEN p^ _ p^ + delta};



initialNodes: NAT = 15;
maxNodes: NAT = 255;

CacheNode: TYPE = RECORD [
prev, next: CachePointer,
table: Handle,
space: VM.Interval _ [0, 0],
refCount: INT _ 0,
nUses: INT _ 0];

CachePointer: TYPE = REF CacheNode;

header, free, unused: CachePointer;
nNodes: [0..maxNodes];
mappedPages: INT;




MakeCacheEntry: INTERNAL PROC [handle: Handle] RETURNS [node: CachePointer] = {
FOR node _ header.next, node.next UNTIL node = free DO
IF node.table = handle THEN GOTO allocated;
REPEAT
allocated =>  NULL;
FINISHED => {
FOR node _ free, node.next UNTIL node = unused DO
IF node.table = handle THEN GOTO unflushed;
REPEAT
unflushed => {IF node = free THEN free _ node.next;  Detach[node]};
FINISHED => {node _ GetEmptyNode[];  node.table _ handle};
ENDLOOP;
IF node.space = [0, 0] THEN {
pages: INT = handle.span.pages;
node.space _ TrimCache[pages];
FS.Read[
file: [node.table.file], 
from: node.table.span.base,
nPages: pages,
to: VM.AddressForPageNumber[node.space.page]];
};
Insert[node, free];
};
ENDLOOP;
node.refCount _ node.refCount+1;  node.nUses _ node.nUses + 1;
RETURN};

FreeCacheEntry: INTERNAL PROC [node: CachePointer] = {
IF (node.refCount _ node.refCount-1) = 0 THEN {
position: CachePointer;
Detach[node];
FOR position _ free, position.next UNTIL position = unused DO
IF node.nUses >= position.nUses THEN EXIT;
ENDLOOP;
Insert[node, position];
IF position = free THEN free _ node}};

ReleaseCacheEntry: INTERNAL PROC [node: CachePointer] = {
IF node = free THEN free _ node.next;
ClearNode[node];
Detach[node];
Insert[node, unused]; unused _ node};

GetEmptyNode: INTERNAL PROC RETURNS [node: CachePointer] = {
IF free = header OR (unused = header AND nNodes < maxNodes) THEN {
node _ NEW[CacheNode];  nNodes _ nNodes + 1}
ELSE {
node _ unused;
IF node = header THEN {
IF node = free THEN free _ node.prev;
unused _ node.prev;  ClearNode[node]};
unused _ node.next;
IF node = free THEN free _ node.next;
Detach[node]};
RETURN};

Detach: INTERNAL PROC [node: CachePointer] = {
node.prev.next _ node.next;  node.next.prev _ node.prev};

Insert: INTERNAL PROC [node, position: CachePointer] = {
node.prev _ position.prev;  node.prev.next _ node;
node.next _ position;  position.prev _ node};

TrimCache: INTERNAL PROC [pages: INT] RETURNS[space: VM.Interval _ [0, 0]] = {  
UNTIL mappedPages <= cachePageLimit DO
IF unused = free THEN EXIT;
ClearNode[unused _ unused.prev];
ENDLOOP;
space _ VM.Allocate[count: pages ! VM.CantAllocate => CONTINUE];
IF space = [0, 0]
THEN {
UNTIL unused = free DO ClearNode[unused _ unused.prev] ENDLOOP;
space _ VM.Allocate[count: pages];
};
mappedPages _ mappedPages + pages;
};

ClearNode: INTERNAL PROC [node: CachePointer] = {
IF node.space # [0, 0] THEN {
mappedPages _ mappedPages - node.space.count;
VM.Free[node.space];
node.space _ [0, 0];
};
node.refCount _ node.nUses _ 0;
};



InstallTable: INTERNAL PROC [base: SymbolTable.Base, node: CachePointer] = {
SetBases[base, node];  base.notifier _ base.NullNotifier};

SetBases: INTERNAL PROC [base: SymbolTable.Base, node: CachePointer] = {
b: LONG POINTER = VM.AddressForPageNumber[node.space.page];
tB: SymbolSegment.Base = LOOPHOLE[b];
p: LONG POINTER TO SymbolSegment.STHeader = b;
q: LONG POINTER TO SymbolSegment.FGHeader;
base.cacheInfo _ LOOPHOLE[node, LONG POINTER];  -- XXX BEWARE
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.span.pages <= p.fgRelPgBase THEN {
base.sourceFile _ NIL; base.fgTable _ NIL}
ELSE {
offset: CARDINAL = LOOPHOLE[@(NIL[POINTER TO SymbolSegment.FGHeader]).sourceFile];
q _ b + p.fgRelPgBase*PrincOps.wordsPerPage;
base.sourceFile _ (b + p.fgRelPgBase*PrincOps.wordsPerPage) + offset;
base.fgTable _ DESCRIPTOR[b + p.fgRelPgBase*PrincOps.wordsPerPage + q.offset, q.length]}};


Init: ENTRY PROC = {
START initial;  initial.link _ NIL;
header _ NEW[CacheNode];
header.next _ header.prev _ header;
nNodes _ 1;
THROUGH [1..initialNodes] DO
node: CachePointer _ NEW[CacheNode];
Insert[node, header];
nNodes _ nNodes + 1;
ENDLOOP;
free _ unused _ header.next;
mappedPages _ 0};

Init[];

}.


¢file SymbolCache.mesa
last edited by Satterthwaite, May 24, 1982 10:31 am
last edited by Paul Rovner, November 17, 1983 2:23 pm
public interface
statistics
internal cache management
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,
symbol table setup
initialization
�Ê
¤˜J˜Jš
œ™Jš
œ3™3Jš
œ5™5J˜š
Ïk	˜	Jšœ
�œ
�œ˜$Jš�œ�œ
�œ˜*Jšœ
�œ
�œ˜Jšœ	�œ
�œ˜1šœ�œ
�œ˜J˜EJ˜DJ˜—Jšœ�œ
�œ&˜?Jšœ
�œ
�œ˜0Jš�œ�œ
�œ@˜NJ˜—šœ
�œÏc8˜NJš�œ�œ�˜#Jš�œ˜J˜Jš
œ™J˜Jšœ�œ˜"J˜Jšœ	�œ
�œ�œ
˜&Jšœ
�œ
�œ�œ
˜:J˜J˜š
Ïnœ�œ
�œ
�œ�œ˜PJš�œ
�œ�œ
˜J˜Jš
œ˜š
œ
˜
š
œ˜Jšœ�œ+�œ˜C—š�œ�˜Jš�œ	�œ
�œ˜8Jš�œ3˜7—J˜+J˜š
�˜Jš	œ�œ
�œ
�œ
�œ˜<——Jš
œ˜Jš
œ˜Jš
œ˜J˜—šŸœ�œ
�œ
�œ˜7Jš�œ
�œ�œ˜Jšœ�œ!ž
˜PJ˜š�œ-�œ�˜IJš�œ
�œ
�œ
�œ
�œ�œ
˜@—Jšœ�œ
˜š�œ2�œ	�œ
�˜Iš�œ�œ˜Jš
�œ�œ
�œ�œ�œ˜N—J˜
š
�˜Jš�œ�œ
�œ
�œ˜0—Jš�œ
˜—J˜J˜DJ˜J˜—Jš	œ�œ
�œ&�œ�œ
˜FJ˜šŸœ�œ
�œ
�œ!�œ
�œ�œ
˜PJš�œ�œ�œ�œ
�œ�œ
˜Uš
Ÿœ�œ�œ�œ�œ˜Bš�œ�œ˜Jš�œ˜!Jš�œ˜#J˜J˜——Jšœ�œ˜J˜š�œ(�œ�˜AJ˜š�œ
�œ
�œ
�œ
˜,Jš�œ$�œ'˜Pš�œ˜š�œ˜Jš�œ ˜$Jš�œ˜—J˜——Jš�œ
˜—Jš
�œ�œ
�œ
�œ
�œ˜<J˜J˜—šŸœ�œ
�œ
�œ˜8Jš�œ˜ Jš�œ
�œ�œ
˜Jšœ�œ!ž
˜PJš�œ˜J˜J˜J˜—Jšœ�œ
˜#J˜'J˜Jšœ�œž$˜>J˜JšŸ	œ�œ
�œ
�œ	�œ�œ˜MJ˜š
Ÿœ�œ
�œ
�œ	�œ˜5Jš�œ
�œ�œ
˜J˜J˜J˜J˜——Jš
œ
™
˜Jšœ�œ�œ
˜Jšœ�œ�œ˜Jšœ�œ(˜5J˜š
Ÿœ�œ�œ
�œ�œ˜=Jš�œ�œ˜*J˜J˜——Jš
œ™˜Jšœ�œ˜Jšœ
�œ˜J˜šœ�œ�œ˜J˜J˜Jšœ�œ˜Jšœ
�œ˜Jšœ�œ˜J˜—Jšœ�œ�œ˜#J˜J˜#J˜Jšœ
�œ
˜J˜J˜Jš
œ#™#J˜Jš
œD™DJš
œE™EJš
œA™AJš
œ'™'Jš
œ9™9Jš
œ@™@Jš
œ.™.J˜šŸœ�œ
�œ�œ˜Oš�œ�œ
�˜6Jš�œ�œ
�œ˜+š
�˜Jšœ�œ
˜š�œ˜
š�œ�œ�˜1Jš�œ�œ
�œ˜+š
�˜Jšœ�œ
�œ"˜CJš�œ2˜:—Jš�œ
˜—š�œ�œ˜Jšœ�œ˜J˜š�œ˜J˜J˜J˜Jšœ�œ(˜.—J˜—J˜J˜——Jš�œ
˜—J˜>Jš�œ˜J˜—šŸœ�œ
�œ˜6š�œ'�œ˜/J˜J˜
š�œ �œ�˜=Jš�œ�œ
�œ
˜*Jš�œ
˜—J˜Jš�œ�œ˜&J˜——šŸœ�œ
�œ˜9Jš�œ
�œ˜%J˜J˜
J˜%J˜—šŸœ�œ
�œ
�œ˜<š�œ�œ�œ�œ˜BJšœ�œ"˜,—š�œ˜J˜š�œ�œ˜Jš�œ
�œ˜%J˜&—J˜Jš�œ
�œ˜%J˜—Jš�œ˜J˜—šŸœ�œ
�œ˜.J˜9J˜—šŸœ�œ
�œ#˜8J˜2J˜-J˜—šŸ	œ�œ
�œ	�œ�œ�œ˜Pš�œ�˜&Jš�œ�œ
�œ
˜J˜ —Jš�œ
˜Jšœ�œ�œ�œ˜@š�œ˜š�œ˜Jš�œ�œ!�œ
˜?Jšœ�œ˜"Jš
œ˜——Jš
œ"˜"J˜J˜—šŸ	œ�œ
�œ˜1š�œ�œ˜J˜-Jš�œ˜J˜J˜—J˜J˜J˜J˜——Jš
œ™˜šŸœ�œ
�œ1˜LJ˜:J˜—šŸœ�œ
�œ1˜HJšœ�œ
�œ�œ'˜;Jšœ�œ˜%Jšœ�œ
�œ
�œ˜.Jšœ�œ
�œ
�œ˜*Jšœ�œ�œ
�œž
˜=J˜"Jšœ
�
œ$�œ˜PJ˜ J˜!J˜#J˜!J˜"J˜"J˜"J˜#Jšœ�œ#˜7Jšœ�œ+˜@J˜.š�œ�œ(�œ˜EJšœ�œ�œ
˜*—š�œ˜Jšœ�œ�œ�œ
�œ
�œ&˜RJ˜,J˜EJšœ�
œA˜ZJ˜———Jš
œ™˜šŸœ�œ
�œ˜Jš�œ�œ
˜#Jšœ	�œ˜J˜#J˜š�œ�˜Jšœ�œ˜$J˜J˜Jš�œ
˜—J˜J˜J˜—J˜J˜J˜J˜J˜——…— ,-r