InternalSymbolCache.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Satterthwaite, April 17, 1986 10:39:40 am PST
Rovner, November 17, 1983 2:23 pm
Russ Atkinson (RRA) February 11, 1985 12:32:12 pm PST
DIRECTORY
BcdDefs: TYPE USING [PageSize],
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 [wordsPerPage, 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𡤀,
nUses: INT𡤀];
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,
VMPages:
PROC[bcdPages:
NAT]
RETURNS[vmPages:
INT] = {
RETURN[
IF (BcdDefs.PageSize
MOD
VM.wordsPerPage) = 0
THEN bcdPages*(BcdDefs.PageSize/VM.wordsPerPage)
ELSE (bcdPages*BcdDefs.PageSize + (VM.wordsPerPage-1))/VM.wordsPerPage]
};
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 = VMPages[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/Symbols.HTRecord.SIZE];
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 ← Symbols.MDIndex.FIRST + p.mdBlock.size;
base.extLimit ← SymbolSegment.ExtIndex.FIRST + 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 {
FGPointer: TYPE = POINTER TO SymbolSegment.FGHeader;
offset: CARDINAL = LOOPHOLE[@(FGPointer.NIL).sourceFile];
q ← b + p.fgRelPgBase*BcdDefs.PageSize;
base.sourceFile ← (b + p.fgRelPgBase*BcdDefs.PageSize) + offset;
base.fgTable ← DESCRIPTOR[b + p.fgRelPgBase*BcdDefs.PageSize + 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[];
}.