-- file SymbolCache.mesa
-- last edited by Satterthwaite, May 24, 1982 10:31 am
-- last edited by Paul Rovner, 14-May-81 16:19:57
DIRECTORY
Environment: TYPE USING [wordsPerPage],
File: TYPE USING [ID, ShowCapability, Unknown],
FileSegment: TYPE USING [Span],
Heap: TYPE USING [systemZone],
Space: TYPE USING [
Activate, Handle, nullHandle, virtualMemory,
Create, CreateUniformSwapUnits, Delete, Error, LongPointer, Map],
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];
SymbolCache: MONITOR -- protects the cache of global frames for symbol tables
IMPORTS initial: SymbolPack, File, Heap, Space
EXPORTS SymbolTable = {
-- public interface
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;
IF freeTables = NIL THEN {base ← NEW initial; Bump[@stats.nNew]; START base}
ELSE {base ← freeTables; freeTables ← freeTables.link};
node ← MakeCacheEntry[handle];
base.link ← busyTables; busyTables ← base;
InstallTable[base, node]};
Release: PUBLIC ENTRY PROC [base: SymbolTable.Base] = {
ENABLE UNWIND => {NULL};
cacheNode: CachePointer = base.cacheInfo;
prev: SymbolTable.Base;
Bump[@stats.nRelease];
FOR node: CachePointer ← 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};
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 [File.ID] = INLINE {
RETURN [h.file.ShowCapability[].fID]};
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]};
fileId: File.ID = FID[handle];
nLocks: NAT ← 0;
prev: CachePointer;
FOR node: CachePointer ← unused.prev, prev UNTIL node = header DO
prev ← node.prev;
IF fileId = 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 ERROR Locked[handle, nLocks]};
busyTables: SymbolTable.Base ← NIL;
freeTables: SymbolTable.Base ← initial;
cachePageLimit: CARDINAL ← 0;
CacheSize: PUBLIC PROC RETURNS [pages: CARDINAL] = {RETURN [cachePageLimit]};
SetCacheSize: PUBLIC ENTRY PROC [pages: CARDINAL] = {
ENABLE UNWIND => {NULL};
cachePageLimit ← pages; TrimCache[cachePageLimit]};
-- statistics
takingStatistics: BOOLEAN = TRUE;
Count: TYPE = LONG CARDINAL ← 0;
stats: RECORD [nAcquire, nNew, nRelease: Count] ← [];
Bump: PROC [p: POINTER TO Count, delta: Count ← 1] = INLINE {
IF takingStatistics THEN p↑ ← p↑ + delta};
-- internal cache management
initialNodes: NAT = 15;
maxNodes: NAT = 255;
CacheNode: TYPE = RECORD [
prev, next: CachePointer,
table: Handle,
space: Space.Handle ← Space.nullHandle,
refCount: [0..maxNodes] ← 0,
nUses: NAT ← 0];
CachePointer: TYPE = LONG POINTER TO CacheNode;
header, free, unused: CachePointer;
nNodes: [0..maxNodes];
mappedPages: 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: INTERNAL 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 => {
IF node = free THEN free ← node.next; Detach[node]};
FINISHED => {node ← GetEmptyNode[]; node.table ← handle};
ENDLOOP;
IF node.space = Space.nullHandle THEN {
pages: CARDINAL = handle.span.pages;
TrimCache[MAX[cachePageLimit, pages] - pages];
node.space ← Space.Create[size: pages, parent: Space.virtualMemory];
IF pages > 15 THEN
Space.CreateUniformSwapUnits[parent: node.space, size: 8];
node.space.Map[
window: [file: node.table.file, base: node.table.span.base]
! Space.Error, File.Unknown => {ERROR Missing[handle]}];
mappedPages ← mappedPages + pages};
Insert[node, free]};
ENDLOOP;
node.refCount ← node.refCount+1; node.nUses ← node.nUses + 1;
node.space.Activate[];
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 ← (Heap.systemZone).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 [size: CARDINAL] = {
WHILE (mappedPages > size OR size = 0) AND unused # free DO
ClearNode[unused ← unused.prev] ENDLOOP};
ClearNode: INTERNAL PROC [node: CachePointer] = {
IF node.space # Space.nullHandle THEN {
Space.Delete[node.space]; node.space ← Space.nullHandle;
mappedPages ← mappedPages - node.table.span.pages};
node.refCount ← node.nUses ← 0};
-- symbol table setup
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 = node.space.LongPointer[];
tB: SymbolSegment.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.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*Environment.wordsPerPage;
base.sourceFile ← (b + p.fgRelPgBase*Environment.wordsPerPage) + offset;
base.fgTable ← DESCRIPTOR[b + p.fgRelPgBase*Environment.wordsPerPage + q.offset, q.length]}};
-- initialization
Init: ENTRY PROC = {
START initial; initial.link ← NIL;
header ← (Heap.systemZone).NEW[CacheNode];
header.next ← header.prev ← header;
nNodes ← 1;
FOR j: NAT IN [0..initialNodes) DO
node: CachePointer ← (Heap.systemZone).NEW[CacheNode];
Insert[node, header];
nNodes ← nNodes + 1;
ENDLOOP;
free ← unused ← header.next;
mappedPages ← 0};
Init[];
}.