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 = { 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[]; }. μSymbolCache.mesa Copyright c 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 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 Κ y˜codešœ™Kšœ Οmœ1™K˜Kš   œžœžœžœ žœžœ˜MK˜š   œžœžœžœ žœ˜5Kšžœžœžœ˜K˜K˜K˜——Kšœ ™ ˜Kšœžœžœ˜Kšœžœžœ˜Kšœžœ(˜5K˜š  œžœžœžœžœ˜=Kšžœžœ˜)Kšœ˜K˜K˜——Kšœ™˜Kšœžœ˜Kšœ žœ˜K˜šœ žœžœ˜K˜K˜Kšœžœ˜Kšœ žœ˜Kšœžœ˜K˜—Kšœžœžœ ˜#K˜K˜#K˜Kšœ žœ˜K˜K˜Kšœ#™#K˜Kšœτ™τKšœ9™9Kšœ@™@Kšœ.™.K˜š œžœžœžœ˜Ošžœžœ ž˜6Kšžœžœžœ ˜+šž˜Kšœžœ˜šžœ˜ šžœžœž˜1Kšžœžœžœ ˜+šž˜Kšœžœ žœ"˜CKšžœ2˜:—Kšžœ˜—šžœžœ˜Kšœžœ˜K˜šžœ˜K˜K˜K˜Kšœžœ(˜.—K˜—K˜K˜——Kšžœ˜—K˜>Kšžœ˜K˜—š œžœžœ˜6šžœ'žœ˜/K˜K˜ šžœ žœž˜=Kšžœžœžœ˜*Kšžœ˜—K˜Kšžœžœ˜&K˜——š œžœžœ˜9Kšžœ žœ˜%K˜K˜ K˜%K˜—š  œžœžœžœ˜<šžœžœžœžœ˜BKšœžœ"˜,—šžœ˜K˜šžœžœ˜Kšžœ žœ˜%K˜&—K˜Kšžœ žœ˜%K˜—Kšžœ˜K˜—š œžœžœ˜.K˜9K˜—š œžœžœ#˜8K˜2K˜-K˜—š   œžœžœ žœžœžœ˜Pšžœž˜&Kšžœžœžœ˜K˜ —Kšžœ˜Kšœžœžœžœ˜@šžœ˜šžœ˜Kšžœžœ!žœ˜?Kšœžœ˜"Kšœ˜——Kšœ"˜"K˜K˜—š  œžœžœ˜1šžœžœ˜K˜-Kšžœ˜K˜K˜—K˜K˜K˜K˜——Kšœ™˜š  œžœžœ1˜LK˜:K˜—š œžœžœ1˜HKšœžœžœžœ'˜;Kšœžœ˜%Kšœžœžœžœ˜.Kšœžœžœžœ˜*KšœžœžœžœŸ ˜=K˜"Kšœ ž œ$žœ˜PK˜ K˜!K˜#K˜!K˜"K˜"K˜"K˜#Kšœžœ#˜7Kšœžœ+˜@K˜.šžœžœ(žœ˜EKšœžœžœ˜*—šžœ˜Kš œžœžœžœžœžœ&˜RK˜,K˜EKšœž œA˜ZK˜———Kšœ™˜š œžœžœ˜Kšžœžœ˜#Kšœ žœ ˜K˜#K˜ šžœž˜Kšœžœ ˜$K˜K˜Kšžœ˜—K˜K˜K˜—K˜K˜K˜K˜K˜——…—ϊ-_