SymbolCache.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Satterthwaite, May 24, 1982 10:31 am
Rovner, November 17, 1983 2:23 pm
Russ Atkinson (RRA) February 11, 1985 12:32:12 pm PST
DIRECTORY
PrincOps USING [wordsPerPage],
FS USING [Read, OpenFile, SameFile],
FileSegment USING [Span],
Symbols USING [HTIndex, HTRecord, MDIndex],
SymbolPack USING [bb, cacheInfo, ctxb, extb, extLimit, fgTable, hashVec, ht, link, ltb, mainCtx, mdb, mdLimit, notifier, NullNotifier, seb, sourceFile, ssb, stHandle, tb],
SymbolSegment USING [Base, ExtIndex, FGHeader, STHeader],
SymbolTable USING [Base, Handle, anySpan],
VM USING [Free, Allocate, AddressForPageNumber, Interval, CantAllocate];
SymbolCache:
MONITOR
-- protects the cache of global frames for symbol tables
IMPORTS initial: SymbolPack, FS, VM
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;
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;
};
statistics
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;
};
internal cache management
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;
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 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;
};
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 = 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]}};
initialization
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[];
}.