-- Swapper.Mesa Edited by Levin on December 29, 1978 4:22 PM DIRECTORY AllocDefs: FROM "allocdefs" USING [AllocHandle, AllocInfo, AllocObject, DefaultDataSegmentInfo, DefaultFileSegmentInfo, DefaultFrameSegmentInfo, DefaultTableSegmentInfo, PageNumber, PageState, SwappingProcedure, SwapStrategy], AltoDefs: FROM "altodefs" USING [BYTE, MaxVMPage, PageCount, PageNumber, PageSize], AltoFileDefs: FROM "altofiledefs" USING [eofDA, vDC], BootDefs: FROM "bootdefs" USING [BusyPage, FreePage, PageMap, PositionSeg, SystemTable, SystemTableHandle, Table, TableHandle], CodeDefs: FROM "codedefs" USING [CodeHandle], ControlDefs: FROM "controldefs" USING [CSegPrefix, GFT, GlobalFrameHandle, NullGlobalFrame], DiskDefs: FROM "diskdefs" USING [DiskRequest, SwapPages], FrameDefs: FROM "framedefs" USING [FlushLargeFrames, ValidateGlobalFrame], GlobalFrameDefs: FROM "globalframedefs" USING [GlobalFrameHandle], InlineDefs: FROM "inlinedefs" USING [BITAND, DIVMOD], MiscDefs: FROM "miscdefs", NucleusDefs: FROM "nucleusdefs", ProcessDefs: FROM "processdefs" USING [DisableInterrupts, EnableInterrupts], SDDefs: FROM "sddefs" USING [SD, sGFTLength], SegmentDefs: FROM "segmentdefs" USING [ChangeDataToFileSegment, DataSegmentHandle, DefaultBase, DeleteFileSegment, FileHint, FileSegmentHandle, FrobHandle, FrobLink, FrobNull, InvalidSegmentSize, MaxLocks, MaxRefs, NewFileSegment, Object, ObjectHandle, ObjectType, OpenFile, PageNumber, Read, RemoteSegCommand, SegmentHandle, Write], SystemDefs: FROM "systemdefs" USING [FreePages], XMESA: FROM "xmesaprivatedefs" USING [Bank1X, BankMasks, BankOption, FreeSeal, InUseSeal, PageMapAllocInfo, XDataSegmentHandle, XFileSegmentHandle, XFileSegmentObject, XMremote, XSegInfo, XSegInfoIndex, XSegInfoTable, XSegmentHandle], XMesaDefs: FROM "xmesadefs" USING [BankIndex, DefaultBase0, DefaultBase3, DefaultXMBase, GetMemoryConfig, MaxXPage, MemoryConfig, LongAddressFromPage, PagesPerBank, XCOPY, XDataSegmentAddress, XFileSegmentAddress]; DEFINITIONS FROM SegmentDefs; Swapper: PROGRAM [ffvmp, lfvmp: AltoDefs.PageNumber] IMPORTS BootDefs, CodeDefs, DiskDefs, FrameDefs, SegmentDefs, SystemDefs, XMesaDefs EXPORTS AllocDefs, BootDefs, FrameDefs, NucleusDefs, SegmentDefs, XMESA SHARES SegmentDefs, XMESA = BEGIN AllocInfo: TYPE = AllocDefs.AllocInfo; AllocHandle: TYPE = AllocDefs.AllocHandle; PageState: TYPE = AllocDefs.PageState; SwappingProcedure: TYPE = AllocDefs.SwappingProcedure; SwapStrategy: TYPE = AllocDefs.SwapStrategy; PageCount: TYPE = AltoDefs.PageCount; PageNumber: TYPE = AltoDefs.PageNumber; TableHandle: TYPE = BootDefs.TableHandle; SegmentHandle: TYPE = SegmentDefs.SegmentHandle; DataSegmentHandle: TYPE = SegmentDefs.DataSegmentHandle; FileSegmentHandle: TYPE = SegmentDefs.FileSegmentHandle; MaxVMPage: PageNumber = AltoDefs.MaxVMPage; PageSize: CARDINAL = AltoDefs.PageSize; PAGEDISP: TYPE = MACHINE DEPENDENT RECORD [ page: [0..MaxVMPage], disp: [0..PageSize)]; PageFromAddress: PUBLIC PROCEDURE [a:POINTER] RETURNS [PageNumber] = BEGIN RETURN[LOOPHOLE[a,PAGEDISP].page] END; AddressFromPage: PUBLIC PROCEDURE [p:PageNumber] RETURNS [POINTER] = BEGIN RETURN[LOOPHOLE[PAGEDISP[p,0]]] END; PagePointer: PUBLIC PROCEDURE [a:POINTER] RETURNS [POINTER] = BEGIN LOOPHOLE[a,PAGEDISP].disp ← 0; RETURN[a] END; -- Data Segments DefaultBase: PageNumber = SegmentDefs.DefaultBase; NewDataSegment: PUBLIC PROCEDURE [base:PageNumber, pages:PageCount] RETURNS [seg:DataSegmentHandle] = BEGIN RETURN[MakeDataSegment[base, pages, AllocDefs.DefaultDataSegmentInfo]] END; NewFrameSegment: PUBLIC PROCEDURE [pages:PageCount] RETURNS [seg:DataSegmentHandle] = BEGIN RETURN[MakeDataSegment[DefaultBase, pages, AllocDefs.DefaultFrameSegmentInfo]] END; MakeDataSegment: PUBLIC PROCEDURE [ base: PageNumber, pages: PageCount, info: AllocInfo] RETURNS [seg: DataSegmentHandle] = BEGIN IF pages ~IN (0..MaxVMPage+1] THEN ERROR InvalidSegmentSize[pages]; seg ← AllocateDataSegment[]; seg↑ ← [busy:, body: segment[data[VMpage:, pages:, unused:]]]; base ← alloc.alloc[base, pages, seg, info ! UNWIND => LiberateDataSegment[seg]]; seg↑ ← [busy: FALSE, body: segment[data[VMpage: , pages: pages, unused: 0]]]; --XM IF base > MaxVMPage THEN --XM BEGIN --XM OPEN s: LOOPHOLE[seg, XMESA.XDataSegmentHandle]; --XM s.VMpage ← 0; s.XMpage ← base --XM END --XM ELSE seg.VMpage ← base; --XM alloc.update[base, pages, inuse, seg]; RETURN END; BootDataSegment: PUBLIC PROCEDURE [base:PageNumber, pages:PageCount] RETURNS [seg:DataSegmentHandle] = BEGIN OPEN AllocDefs; -- called only by Wart we hope -- --XM i: PageNumber; IF base > MaxVMPage THEN ERROR; --XM FOR i IN [base..base+pages) DO IF alloc.status[i].status # busy THEN ERROR; ENDLOOP; seg ← AllocateDataSegment[]; seg↑ ← [busy: FALSE, body: segment[data[VMpage: base, pages: pages, unused: 0]]]; alloc.update[base, pages, inuse, seg]; RETURN END; DeleteDataSegment: PUBLIC PROCEDURE [seg:DataSegmentHandle] = BEGIN base: PageNumber; pages: PageCount; ValidateDataSegment[seg]; BEGIN OPEN s: LOOPHOLE[seg, XMESA.XDataSegmentHandle]; --XM base ← IF s.VMpage = 0 THEN s.XMpage ELSE s.VMpage; --XM END; --XM pages ← seg.pages; alloc.update[base, pages, busy, NIL]; --XM LiberateDataSegment[seg]; alloc.update[base, pages, free, NIL]; --XM RETURN END; DataSegmentAddress: PUBLIC PROCEDURE [seg:DataSegmentHandle] RETURNS [POINTER] = BEGIN IF seg.VMpage = 0 THEN ERROR; --XM RETURN[LOOPHOLE[PAGEDISP[seg.VMpage,0]]] END; -- Swapping Segments SwapError: PUBLIC SIGNAL [seg:FileSegmentHandle] = CODE; MakeSwappedIn: PUBLIC PROCEDURE [ seg: FileSegmentHandle, base: PageNumber, info: AllocInfo] = BEGIN vmpage: PageNumber; IF seg.lock = MaxLocks THEN ERROR SwapError[seg]; ValidateObject[seg]; ProcessDefs.DisableInterrupts[]; IF seg.swappedin THEN BEGIN seg.lock ← seg.lock+1; ProcessDefs.EnableInterrupts[]; RETURN END; -- XM -- seg.busy ← TRUE; ProcessDefs.EnableInterrupts[]; IF seg.file.swapcount = MaxRefs THEN SIGNAL SwapError[seg]; IF ~seg.file.open THEN OpenFile[seg.file]; vmpage ← alloc.alloc[base, seg.pages, seg, info]; --XM -- There is a funny side-effect of AllocVM that we have to worry about. In the course -- of allocating space for the segment, it is possible that segments have been swapped in -- (in order to call swapping procedures or execute instructions implemented in software). -- In particular, it is possible that 'seg' itself has been swapped in this way. The exits -- in the following block of code deal with this possibility. BEGIN -- block for funny cases -- --XM ENABLE UNWIND => alloc.update[vmpage, seg.pages, free, NIL]; ProcessDefs.DisableInterrupts[]; --XM IF seg.swappedin THEN BEGIN seg.lock ← seg.lock+1; ProcessDefs.EnableInterrupts[]; GO TO Surprise END; --XM ProcessDefs.EnableInterrupts[]; --XM WITH s: seg SELECT FROM disk => IF vmpage > MaxVMPage THEN --XM BEGIN --XM MakeSwappedIn[@s, XMesaDefs.DefaultBase0, AllocDefs.DefaultFileSegmentInfo]; --XM IF s.loc ~= disk THEN GO TO Surprise; -- already in a high bank -- --XM XMesaDefs.XCOPY[from: XMesaDefs.LongAddressFromPage[s.VMpage], --XM to: XMesaDefs.LongAddressFromPage[vmpage], --XM nwords: s.pages*PageSize]; --XM alloc.update[VanillaToChocolate[seg,vmpage], s.pages, free, NIL]; --XM ProcessDefs.DisableInterrupts[]; --XM END --XM ELSE BEGIN s.VMpage ← vmpage; IF (s.hint.page # s.base OR s.hint.da = AltoFileDefs.eofDA) AND BootDefs.PositionSeg[@s,TRUE] AND s.pages = 1 THEN NULL ELSE MapVM[@s, ReadD]; GO TO BumpCounts --XM END; remote => IF s.proc = XMESA.XMremote THEN ERROR --XM ELSE BEGIN s.proc[@s, remoteRead]; GO TO BumpCounts END; --XM ENDCASE; EXITS --XM BumpCounts => -- normal termination of non-chocolate segment read-in -- --XM BEGIN --XM ProcessDefs.DisableInterrupts[]; --XM seg.file.swapcount ← seg.file.swapcount+1; --XM seg.lock ← seg.lock+1; --XM seg.swappedin ← TRUE; --XM END; --XM Surprise => BEGIN alloc.update[vmpage, seg.pages, free, NIL]; RETURN END; --XM END; -- block for funny cases -- --XM alloc.update[vmpage, seg.pages, inuse, seg]; ProcessDefs.EnableInterrupts[]; RETURN END; SwapIn: PUBLIC PROCEDURE [seg:FileSegmentHandle] = BEGIN info: AllocDefs.AllocInfo ← AllocDefs.DefaultFileSegmentInfo; IF seg.class = code THEN info.class ← code; MakeSwappedIn[seg, DefaultBase, info]; RETURN END; Unlock: PUBLIC PROCEDURE [seg:FileSegmentHandle] = BEGIN OPEN seg; IF lock = 0 THEN ERROR SwapError[seg]; ValidateObject[seg]; ProcessDefs.DisableInterrupts[]; lock ← lock-1; ProcessDefs.EnableInterrupts[]; RETURN END; SwapUp: PUBLIC PROCEDURE [seg:FileSegmentHandle] = BEGIN OPEN seg; ValidateObject[seg]; IF swappedin AND write THEN BEGIN WITH s: seg SELECT FROM disk => BEGIN IF s.hint.page # base OR s.hint.da = AltoFileDefs.eofDA THEN [] ← BootDefs.PositionSeg[@s,FALSE]; MapVM[@s, WriteD]; END; remote => IF s.proc = XMESA.XMremote THEN BEGIN OPEN xs: LOOPHOLE[seg,POINTER TO remote XMESA.XFileSegmentObject]; --XM lowFileSeg: FileSegmentHandle ← NewFileSegment[xs.file, xs.base, xs.pages, Read+Write]; lowDataSeg: DataSegmentHandle ← NewDataSegment[DefaultBase, xs.pages]; --XM XMesaDefs.XCOPY[from: XMesaDefs.XFileSegmentAddress[seg], --XM to: XMesaDefs.XDataSegmentAddress[lowDataSeg], --XM nwords: xs.pages*PageSize]; --XM ChangeDataToFileSegment[lowDataSeg, lowFileSeg]; --XM Unlock[lowFileSeg]; --XM DeleteFileSegment[lowFileSeg]; --XM END --XM ELSE s.proc[@s, remoteWrite]; --XM ENDCASE; END; RETURN END; SwapOut: PUBLIC PROCEDURE [seg:FileSegmentHandle] = BEGIN OPEN seg; base: PageNumber; SwapUp[seg]; ProcessDefs.DisableInterrupts[]; IF ~swappedin THEN BEGIN ProcessDefs.EnableInterrupts[]; RETURN END; IF lock # 0 THEN BEGIN ProcessDefs.EnableInterrupts[]; ERROR SwapError[seg] END; busy ← TRUE; WITH s: seg SELECT FROM --XM disk => BEGIN base ← s.VMpage; s.VMpage ← 0; END; --XM remote => IF s.proc = XMESA.XMremote THEN base ← ChocolateToVanilla[LOOPHOLE[seg],0] --XM ELSE BEGIN base ← s.VMpage; s.VMpage ← 0; END; --XM ENDCASE; alloc.update[base, pages, busy, NIL]; swappedin ← FALSE; busy ← FALSE; file.swapcount ← file.swapcount-1; ProcessDefs.EnableInterrupts[]; -- IF swapcount = 0 THEN CloseFile[]; ??? alloc.update[base, pages, free, NIL]; RETURN END; VanillaToChocolate: PUBLIC PROCEDURE [seg: FileSegmentHandle, newpage: PageNumber] RETURNS [oldpage: PageNumber] = --XM BEGIN xs: POINTER TO XMESA.XSegInfo ← AllocXSegInfo[]; oldpage ← seg.VMpage; xs.XMpage ← newpage; WITH s: seg SELECT FROM disk => xs.body ← hint[s.hint]; ENDCASE => ERROR; seg.location ← remote[XMESA.XMremote, xs]; -- note variant changes here!!!-- END; ChocolateToVanilla: PUBLIC PROCEDURE [seg: XMESA.XFileSegmentHandle, newpage: PageNumber] RETURNS [oldpage: PageNumber] = --XM BEGIN WITH s: seg SELECT FROM remote => IF s.proc = XMESA.XMremote THEN BEGIN fh: FileHint ← s.info.hint; oldpage ← s.info.XMpage; FreeXSegInfo[s.info]; seg.location ← disk[fh]; -- note that variant changes here!!!-- seg.VMpage ← newpage; END ELSE ERROR; ENDCASE => ERROR; END; XSIhead: POINTER TO XMESA.XSegInfoTable ← NIL; --XM AllocXSegInfo: PROCEDURE RETURNS [xs: POINTER TO XMESA.XSegInfo] = --XM BEGIN OPEN XMESA; i: XSegInfoIndex; p: POINTER TO XSegInfoTable; ProcessDefs.DisableInterrupts[]; FOR p ← XSIhead, AddressFromPage[p.nextPage] UNTIL p = NIL DO IF p.freeCount # 0 THEN BEGIN xs ← p.freeHead; IF xs.seal # FreeSeal THEN ERROR; EXIT END; REPEAT FINISHED => BEGIN p ← DataSegmentAddress[NewDataSegment[DefaultBase,1]]; p.nextPage ← PageFromAddress[XSIhead]; XSIhead ← p; p.freeCount ← LAST[XSegInfoIndex]+1; FOR i IN XSegInfoIndex DO p.table[i].link ← @p.table[i+1]; p.table[i].seal ← FreeSeal; ENDLOOP; xs ← @p.table[0]; END; ENDLOOP; p.freeHead ← xs.link; p.freeCount ← p.freeCount-1; ProcessDefs.EnableInterrupts[]; xs.seal ← InUseSeal; END; FreeXSegInfo: PROCEDURE [xs: POINTER TO XMESA.XSegInfo] = --XM BEGIN OPEN XMESA; p: POINTER TO XSegInfoTable ← PagePointer[xs]; IF xs.seal # InUseSeal THEN ERROR; xs.seal ← FreeSeal; ProcessDefs.DisableInterrupts[]; xs.link ← p.freeHead; p.freeHead ← xs; p.freeCount ← p.freeCount+1; IF p.freeCount = LAST[XSegInfoIndex]+1 THEN BEGIN prev: POINTER TO XSegInfoTable ← XSIhead; IF prev = p THEN XSIhead ← AddressFromPage[p.nextPage] ELSE BEGIN UNTIL prev = NIL DO IF prev.nextPage = PageFromAddress[p] THEN EXIT; prev ← AddressFromPage[prev.nextPage]; REPEAT FINISHED => ERROR; ENDLOOP; prev.nextPage ← p.nextPage; END; SystemDefs.FreePages[p]; END; ProcessDefs.EnableInterrupts[]; END; remoteRead: RemoteSegCommand = 0; remoteWrite: RemoteSegCommand = 1; SegmentFault: PUBLIC SIGNAL [seg:FileSegmentHandle, pages:PageCount] = CODE; MapVM: PUBLIC PROCEDURE [seg:FileSegmentHandle, dc: AltoFileDefs.vDC] = BEGIN OPEN seg; page: PageNumber; byte: CARDINAL; temp: PageCount; arg: swap DiskDefs.DiskRequest; WITH s: seg SELECT FROM disk => BEGIN arg ← DiskDefs.DiskRequest[AddressFromPage[s.VMpage], @s.hint.da, s.base, s.base+s.pages-1, @s.file.fp, FALSE, dc, dc, FALSE, swap[NIL]]; IF s.hint.page # s.base THEN ERROR SwapError[@s]; [page,byte] ← DiskDefs.SwapPages[@arg]; temp ← page-base+(IF byte=0 THEN 0 ELSE 1); IF temp=0 THEN ERROR SegmentFault[@s,0]; IF temp # pages THEN BEGIN SIGNAL SegmentFault[@s,temp]; alloc.update[s.VMpage+temp, s.pages-temp, free, NIL]; s.pages ← temp; END; END; remote => ERROR SwapError[@s]; ENDCASE; RETURN END; -- Code Swapping and Swap Strategies trySwapInProgress: BOOLEAN ← FALSE; TrySwapping: SwappingProcedure = BEGIN did: BOOLEAN; sp, next: POINTER TO SwapStrategy; ProcessDefs.DisableInterrupts[]; IF trySwapInProgress THEN BEGIN ProcessDefs.EnableInterrupts[]; RETURN[TryCodeSwapping[needed, info, seg]]; END; trySwapInProgress ← TRUE; ProcessDefs.EnableInterrupts[]; did ← TRUE; FOR sp ← StrategyList, next UNTIL sp = NIL DO next ← sp.link; IF sp.proc[needed, info, seg] THEN EXIT; REPEAT FINISHED => did ← FALSE; ENDLOOP; trySwapInProgress ← FALSE; RETURN[did] END; CantSwap: PUBLIC SwappingProcedure = BEGIN RETURN[FALSE] END; pageRover: AltoDefs.PageNumber ← 0;-- these three variables are set by XAllocVM-- --XM roverMax: AltoDefs.PageNumber ← AltoDefs.MaxVMPage; --XM roverMin: AltoDefs.PageNumber ← 0; --XM TryCodeSwapping: PUBLIC SwappingProcedure = BEGIN OPEN ControlDefs; foundHole: BOOLEAN ← FALSE; pass: {first, second, quit} ← first; okay: BOOLEAN; base, page: AltoDefs.PageNumber; segment: XMESA.XSegmentHandle; status: AllocDefs.PageState; p: POINTER TO CSegPrefix; --XM longP: LONG POINTER TO CSegPrefix; --XM csegpfx: CSegPrefix; --XM n, inc: PageCount; page ← n ← 0; ProcessDefs.DisableInterrupts[]; segment ← LOOPHOLE[alloc.status[pageRover].seg,XMESA.XSegmentHandle]; --XM IF segment # NIL THEN WITH s: segment SELECT FROM data => pageRover ← IF s.VMpage = 0 THEN s.XMpage ELSE s.VMpage; --XM file => --XM WITH fs: s SELECT FROM --XM disk => pageRover ← s.VMpage; --XM remote => pageRover ← IF fs.proc = XMESA.XMremote THEN fs.info.XMpage ELSE fs.VMpage; --XM ENDCASE; --XM ENDCASE; base ← pageRover; DO -- until we've looked at them all twice [segment, status] ← LOOPHOLE[alloc.status[pageRover], RECORD[XMESA.XSegmentHandle,AllocDefs.PageState]]; okay ← FALSE; SELECT status FROM inuse => WITH s: segment SELECT FROM data => inc ← s.pages; file => BEGIN IF s.lock = 0 AND ~s.write THEN IF s.class = code THEN BEGIN csegBase: PageNumber ← s.VMpage; --XM WITH fs:s SELECT FROM --XM remote => IF fs.proc = XMESA.XMremote THEN csegBase ← fs.info.XMpage; --XM ENDCASE; --XM longP ← XMesaDefs.LongAddressFromPage[csegBase]; --XM p←@csegpfx; --XM XMesaDefs.XCOPY[from: longP, to: LONG[p], nwords: SIZE[CSegPrefix]]; --XM IF p.swapinfo > 1 THEN --XM BEGIN --XM longP ← longP + p.swapinfo; --XM XMesaDefs.XCOPY[from: longP, to: LONG[p], nwords: SIZE[CSegPrefix]]; --XM END; --XM IF p.swapinfo = 0 THEN okay ← TRUE ELSE --XM BEGIN --XM p.swapinfo←0; --XM XMesaDefs.XCOPY[from: LONG[p], to: longP, nwords: SIZE[CSegPrefix]]; --XM END; --XM END ELSE okay ← TRUE; inc ← s.pages; END; ENDCASE; ENDCASE => BEGIN IF status = free THEN okay ← TRUE; inc ← 1; END; IF ~okay THEN BEGIN page ← n ← 0; IF pass = quit THEN EXIT; END ELSE BEGIN IF page = 0 THEN page ← pageRover; IF (n ← n+inc) >= needed THEN BEGIN foundHole ← TRUE; EXIT END; --XM END; IF (pageRover ← pageRover+inc) > roverMax THEN --XM IF pass = quit THEN EXIT ELSE BEGIN pageRover ← page ← roverMin; n ← 0 END; --XM IF pageRover = base THEN pass ← IF pass = first THEN second ELSE quit; ENDLOOP; base ← page + n; WHILE page < base DO segment ← LOOPHOLE[alloc.status[page].seg]; IF segment # NIL THEN WITH s: segment SELECT FROM data => page ← (IF s.VMpage = 0 THEN s.XMpage ELSE s.VMpage) + s.pages; --XM file => BEGIN WITH fs: s SELECT FROM --XM disk => page ← s.VMpage; --XM remote => page ← IF fs.proc = XMESA.XMremote THEN fs.info.XMpage ELSE fs.VMpage; --XM ENDCASE; --XM IF s.lock = 0 THEN BEGIN alloc.update[page, s.pages, free, NIL]; IF s.class = code THEN UpdateCodebases[@s]; SwapOutUnlocked[@s]; END; page ← page + s.pages; END; ENDCASE ELSE page ← page + 1; ENDLOOP; ProcessDefs.EnableInterrupts[]; RETURN[foundHole] END; SwapOutCode: PUBLIC PROCEDURE [f:ControlDefs.GlobalFrameHandle] = BEGIN OPEN SegmentDefs, ControlDefs; cseg: FileSegmentHandle; FrameDefs.ValidateGlobalFrame[f]; ProcessDefs.DisableInterrupts[]; cseg ← CodeDefs.CodeHandle[f]; IF cseg # NIL THEN BEGIN SwapIn[cseg]; -- lock it so it won't go away UpdateCodebases[LOOPHOLE[cseg]]; Unlock[cseg]; SwapOut[cseg]; END; ProcessDefs.EnableInterrupts[]; RETURN END; SwapOutFileSegment: PUBLIC PROCEDURE [seg: SegmentDefs.FileSegmentHandle] = --XM BEGIN IF seg.class = code THEN BEGIN ProcessDefs.DisableInterrupts[]; SwapIn[seg]; -- lock it so it won't go away UpdateCodebases[LOOPHOLE[seg]]; Unlock[seg]; SwapOut[seg]; ProcessDefs.EnableInterrupts[]; END ELSE SwapOut[seg]; RETURN END; LastResort: SwapStrategy ← SwapStrategy[NIL,TryCodeSwapping]; StrategyList: POINTER TO SwapStrategy ← @LastResort; AddSwapStrategy: PUBLIC PROCEDURE [strategy:POINTER TO SwapStrategy] = BEGIN sp: POINTER TO SwapStrategy; ProcessDefs.DisableInterrupts[]; FOR sp ← StrategyList, sp.link UNTIL sp = NIL DO IF sp = strategy THEN RETURN; ENDLOOP; strategy.link ← StrategyList; StrategyList ← strategy; ProcessDefs.EnableInterrupts[]; RETURN END; RemoveSwapStrategy: PUBLIC PROCEDURE [strategy:POINTER TO SwapStrategy] = BEGIN sp: POINTER TO SwapStrategy; prev: POINTER TO SwapStrategy ← NIL; ProcessDefs.DisableInterrupts[]; FOR sp ← StrategyList, sp.link UNTIL sp = NIL DO IF sp = strategy THEN BEGIN IF prev = NIL THEN StrategyList ← sp.link ELSE prev.link ← sp.link; EXIT END; prev ← sp; ENDLOOP; ProcessDefs.EnableInterrupts[]; strategy.link ← NIL; RETURN END; -- Memory Allocator -- extra entries to point at maps for banks 1, 2, and 3 (kludge because of interface between Mesa world and external debugger). PageMap: ARRAY [0..XMesaDefs.PagesPerBank+3) OF SegmentHandle; --XM FreePage: SegmentHandle = BootDefs.FreePage; --XM BusyPage: SegmentHandle = BootDefs.BusyPage; --XM PageMaps: ARRAY XMesaDefs.BankIndex OF POINTER TO BootDefs.PageMap; -- PageMaps[0]=@PageMap-- --XM BankState: TYPE = RECORD --XM [ ffvmp, lfvmp: PageNumber, -- absolute page numbers for first and last free pages (hint) pageRover: PageNumber, -- absolute page number for first place to try swapping (hint) nFree: PageCount, -- number of free pages in bank (hint) bankAvailable: BOOLEAN -- TRUE if can access this bank ]; allocState: ARRAY XMesaDefs.BankIndex OF BankState; --XM -- *** The framesize of PageAvailable is depended on below *** PageAvailable: PROCEDURE [page: PageNumber, info: AllocInfo] RETURNS [available: BOOLEAN] = BEGIN seg: SegmentHandle; dummy: ARRAY [0..4) OF UNSPECIFIED; -- ensure that this frame is suitably large! bank: PageCount; relPage: PageNumber; --XM dummy[0] ← 0; [bank, relPage] ← InlineDefs.DIVMOD[page, XMesaDefs.PagesPerBank]; --XM IF bank ~IN XMesaDefs.BankIndex THEN ERROR; --XM available ← FALSE; IF PageMaps[bank] = NIL THEN RETURN; --XM ProcessDefs.DisableInterrupts[]; seg ← PageMaps[bank][relPage]; --XM IF seg = FreePage THEN available ← TRUE ELSE IF seg # BusyPage THEN WITH s: seg SELECT FROM file => IF (info.effort = hard OR info.swapunlocked) AND s.lock = 0 AND ~s.write AND ~s.busy THEN available ← TRUE; ENDCASE; ProcessDefs.EnableInterrupts[]; RETURN END; -- *** PageStatus' framesize must be <= PageAvailable's *** PageStatus: PROCEDURE [page: PageNumber] RETURNS [seg: SegmentHandle, status: PageState] = BEGIN bank: PageCount; relPage: PageNumber; --XM [bank, relPage] ← InlineDefs.DIVMOD[page, XMesaDefs.PagesPerBank]; --XM IF bank ~IN XMesaDefs.BankIndex THEN ERROR; --XM ProcessDefs.DisableInterrupts[]; IF PageMaps[bank] = NIL THEN seg ← BusyPage ELSE seg ← PageMaps[bank][relPage]; --XM SELECT seg FROM BusyPage => BEGIN status ← busy; seg ← NIL END; FreePage => BEGIN status ← free; seg ← NIL END; ENDCASE => IF seg.busy THEN BEGIN status ← free; seg ← NIL; END ELSE status ← inuse; ProcessDefs.EnableInterrupts[]; RETURN END; XAllocVM: PROCEDURE [base: PageNumber, pages: PageCount, seg: SegmentHandle, info: AllocInfo] RETURNS [PageNumber] = --XM BEGIN OPEN XMESA; baseCopy: PageNumber ← DefaultBase; i, bank: XMesaDefs.BankIndex; page: PageNumber; worthwhile, allocSucceeded: BOOLEAN; bankSelect: ARRAY XMesaDefs.BankIndex OF BankOption; SetForSingleBank: PROCEDURE[b: XMesaDefs.BankIndex] = BEGIN bankSelect[0] ← b; bankSelect[1] ← LAST[BankOption]; END; Swap: PROCEDURE[i,j: BankOption] = BEGIN temp: BankOption ← bankSelect[i]; bankSelect[i] ← bankSelect[j]; bankSelect[j] ← temp; END; OrderBanks: PROCEDURE[includeZero: BOOLEAN] = BEGIN -- sort XM banks from most empty to fullest bankSelect ← [1, 2, 3, 4]; IF allocState[bankSelect[0]].nFree < allocState[bankSelect[1]].nFree THEN Swap[0,1]; IF allocState[bankSelect[0]].nFree > allocState[bankSelect[2]].nFree THEN BEGIN IF allocState[bankSelect[1]].nFree < allocState[bankSelect[2]].nFree THEN Swap[1,2] END ELSE BEGIN Swap[1,2]; Swap[0,1] END; IF includeZero THEN bankSelect[LAST[XMesaDefs.BankIndex]] ← 0; END; FrameDefs.FlushLargeFrames[]; DO -- loop so that we can retry if InsufficientVM is RESUMEd BEGIN SELECT base FROM < XMesaDefs.MaxXPage => -- explicit base given BEGIN baseCopy ← base; SetForSingleBank[base/XMesaDefs.PagesPerBank]; END; IN [XMesaDefs.DefaultBase0 .. XMesaDefs.DefaultBase3] => SetForSingleBank[base-XMesaDefs.DefaultBase0]; XMesaDefs.DefaultXMBase => OrderBanks[includeZero: FALSE]; ENDCASE => -- must be DefaultBase IF info.class=code THEN OrderBanks[includeZero: TRUE] ELSE SetForSingleBank[0]; -- now that the bankSelect array is set up, begin the allocation process FOR i IN XMesaDefs.BankIndex WHILE (bank ← bankSelect[i]) IN XMesaDefs.BankIndex DO -- first just try the appropriate banks IF allocState[bank].bankAvailable THEN BEGIN [allocSucceeded, page] ← AllocVM[baseCopy, pages, seg, info, bank]; IF allocSucceeded THEN RETURN[page] END; ENDLOOP; IF info.class=table OR info.class=frame THEN GOTO SendSignal; -- don't try harder in this case FOR i IN XMesaDefs.BankIndex WHILE (bank ← bankSelect[i]) IN XMesaDefs.BankIndex DO -- now try swapping for each bank and then retry IF allocState[bank].bankAvailable THEN DO pageRover ← allocState[bank].pageRover; -- global var used by TryCodeSwapping roverMin ← bank*XMesaDefs.PagesPerBank; roverMax ← roverMin+XMesaDefs.PagesPerBank-1; worthwhile ← TrySwapping[pages, info, seg]; allocState[bank].pageRover ← pageRover; -- save its new value IF worthwhile THEN BEGIN [allocSucceeded, page] ← AllocVM[baseCopy, pages, seg, info, bank]; --pass 2 IF allocSucceeded THEN RETURN[page]; END ELSE EXIT; ENDLOOP ENDLOOP; EXITS SendSignal => NULL; END; SIGNAL InsufficientVM[pages]; -- falling out of the second loop means really no room ENDLOOP; END; InsufficientVM: PUBLIC SIGNAL [needed: PageCount] = CODE; VMnotFree: PUBLIC SIGNAL [base: PageNumber, pages: PageCount] = CODE; AllocVM: PROCEDURE [base: PageNumber, pages: PageCount, seg: SegmentHandle, info: AllocInfo, bank: XMesaDefs.BankIndex] --XM RETURNS [success: BOOLEAN, p: PageNumber] = BEGIN tempseg: XMESA.XSegmentHandle; --XM n: CARDINAL; direction: INTEGER; vm: PageNumber; IF base # DefaultBase THEN DO -- repeat if requested VM not free ProcessDefs.DisableInterrupts[]; FOR vm IN [base.. base+pages) DO IF ~alloc.avail[base, info] THEN EXIT; REPEAT FINISHED => GOTO found; ENDLOOP; ProcessDefs.EnableInterrupts[]; SIGNAL VMnotFree[base, pages]; REPEAT found => NULL ENDLOOP ELSE BEGIN ProcessDefs.DisableInterrupts[]; n ← 0; -- count of contiguous free pages IF info.direction = bottomup THEN BEGIN direction ← 1; base ← allocState[bank].ffvmp; END ELSE BEGIN direction ← -1; base ← allocState[bank].lfvmp; END; WHILE base IN [allocState[bank].ffvmp..allocState[bank].lfvmp] DO IF ~alloc.avail[base, info] THEN n ← 0 ELSE IF (n ← n+1) = pages THEN BEGIN IF direction>0 THEN base ← base-n+1; GOTO foundHole END; base ← base+direction ENDLOOP; ProcessDefs.EnableInterrupts[]; RETURN[FALSE, 0]; -- leave strategies up to XAllocVM-- --XM EXITS foundHole => NULL; END; FOR vm IN [base..base+pages) DO tempseg ← LOOPHOLE[alloc.status[vm].seg]; IF tempseg # NIL THEN WITH s: tempseg SELECT FROM file => BEGIN csegBase: PageNumber ← s.VMpage; --XM WITH fs: s SELECT FROM --XM remote => IF fs.proc = XMESA.XMremote THEN csegBase ← fs.info.XMpage; --XM ENDCASE; --XM alloc.update[csegBase, s.pages, free, NIL]; IF s.class = code THEN UpdateCodebases[@s]; SwapOutUnlocked[@s]; END; ENDCASE; ENDLOOP; alloc.update[base, pages, busy, seg]; ProcessDefs.EnableInterrupts[]; RETURN[TRUE, base] END; -- *** UpdateVM's framesize must be <= PageAvailable's *** UpdateVM: PROCEDURE [base: PageNumber, pages: PageCount, status: PageState, seg: SegmentHandle] = BEGIN bank: PageCount; relPage: PageNumber; --XM wereFree: PageCount ← 0; --XM [bank, relPage] ← InlineDefs.DIVMOD[base, XMesaDefs.PagesPerBank]; --XM IF bank ~IN XMesaDefs.BankIndex OR PageMaps[bank] = NIL THEN ERROR; --XM IF status = free THEN BEGIN ProcessDefs.DisableInterrupts[]; allocState[bank].ffvmp ← MIN[allocState[bank].ffvmp,base]; --XM allocState[bank].lfvmp ← MAX[allocState[bank].lfvmp,base+pages-1]; --XM allocState[bank].nFree ← allocState[bank].nFree+pages; --XM ProcessDefs.EnableInterrupts[]; END; seg ← SELECT status FROM free => FreePage, busy => BusyPage, ENDCASE => IF seg = NIL THEN BusyPage ELSE seg; ProcessDefs.DisableInterrupts[]; FOR base IN [relPage..relPage+pages) DO IF PageMaps[bank][base] = FreePage THEN wereFree ← wereFree+1; PageMaps[bank][base] ← seg; ENDLOOP; --XM allocState[bank].nFree ← allocState[bank].nFree-wereFree; --XM ProcessDefs.EnableInterrupts[]; RETURN END; -- *** SwapOutUnlocked's framesize must be <= PageAvailable's *** SwapOutUnlocked: PROCEDURE [seg: XMESA.XFileSegmentHandle] = BEGIN ProcessDefs.DisableInterrupts[]; seg.swappedin ← FALSE; WITH s: seg SELECT FROM --XM remote => --XM IF s.proc = XMESA.XMremote THEN -- seg.VMpage ← ChocolateToVanilla[seg,0] -- --XM BEGIN OPEN XMESA; --XM -- can't call ChocolateToVanilla because of possible frame trap, so... -- --XM fh: FileHint ← s.info.hint; --XM xsi: POINTER TO XSegInfo ← s.info; --XM p: POINTER TO XSegInfoTable ← LOOPHOLE[xsi]; --XM LOOPHOLE[p,PAGEDISP].disp ← 0; --XM IF xsi.seal # InUseSeal THEN ERROR; --XM xsi.seal ← FreeSeal; --XM xsi.link ← p.freeHead; --XM p.freeHead ← xsi; --XM p.freeCount ← p.freeCount+1; --XM seg.location ← disk[fh]; -- note that variant changes here!!!-- --XM END; -- don't try to release possibly empty page -- --XM ENDCASE; --XM seg.VMpage ← 0; seg.file.swapcount ← seg.file.swapcount-1; ProcessDefs.EnableInterrupts[]; END; -- *** UpdateCodebases's framesize must be <= PageAvailable's *** UpdateCodebases: PROCEDURE [seg: XMESA.XFileSegmentHandle] = BEGIN OPEN ControlDefs; lastUser, f: GlobalFrameHandle; nUsers: CARDINAL ← 0; --XM i: CARDINAL; --XM segBase: PageNumber; --XM zeroPtr: POINTER = LOOPHOLE[0]; --XM vmpage: PageNumber; ProcessDefs.DisableInterrupts[]; FOR i IN [1..SDDefs.SD[SDDefs.sGFTLength]) DO f ← GFT[i].frame; IF f # NullGlobalFrame AND GFT[i].epbase = 0 THEN BEGIN IF ~f.code.swappedout THEN --XM BEGIN OPEN frame: LOOPHOLE[f, GlobalFrameDefs.GlobalFrameHandle]; vmpage ← LOOPHOLE[frame.code.shortCodebase,PAGEDISP].page; IF frame.code.highByte = 0 THEN vmpage ← vmpage + 256*frame.code.topByteOfLongPointer; --XM segBase ← seg.VMpage; --XM WITH s:seg SELECT FROM remote => IF s.proc = XMESA.XMremote THEN segBase ← s.info.XMpage; --XM ENDCASE; IF vmpage ~IN [segBase..segBase+seg.pages) THEN LOOP; --XM f.code.offset ← f.code.offset - AltoDefs.PageSize*segBase; f.code.swappedout ← TRUE; f.codesegment ← LOOPHOLE[seg]; END ELSE IF f.codesegment # LOOPHOLE[seg] THEN LOOP; --XM IF ~f.shared THEN EXIT; nUsers ← nUsers+1; lastUser ← f; END; REPEAT FINISHED => IF nUsers = 1 THEN lastUser.shared ← FALSE; ENDLOOP; ProcessDefs.EnableInterrupts[]; RETURN END; SetAllocationObject: PUBLIC PROCEDURE [new: AllocHandle] RETURNS [old: AllocHandle] = BEGIN ProcessDefs.DisableInterrupts[]; old ← alloc; alloc ← new; ProcessDefs.EnableInterrupts[]; RETURN END; GetAllocationObject: PUBLIC PROCEDURE RETURNS [old: AllocHandle] = BEGIN RETURN[alloc] END; -- Primative Object Allocation ObjectSeal: AltoDefs.BYTE = 21B; InvalidObject: PUBLIC SIGNAL [object: POINTER] = CODE; AllocateObject: PUBLIC PROCEDURE [size: CARDINAL] RETURNS [ObjectHandle] = BEGIN OPEN BootDefs; frob: FrobLink; frobject: FrobHandle; table: TableHandle; base, length: CARDINAL; ProcessDefs.DisableInterrupts[]; FOR table ← systemTable.table, table.link UNTIL table = NIL DO IF table.free.fwdp # FIRST[FrobLink] THEN BEGIN base ← LOOPHOLE[table, CARDINAL]; FOR frob ← table.free.fwdp, frobject.fwdp UNTIL frob = FIRST[FrobLink] DO frobject ← base+frob; length ← frobject.size; UNTIL frob+length > FrobNull DO WITH n: LOOPHOLE[frobject+length, ObjectHandle] SELECT FROM free => -- coalesce nodes BEGIN (base+n.fwdp).backp ← n.backp; (base+n.backp).fwdp ← n.fwdp; length ← length + n.size; END; ENDCASE => EXIT; ENDLOOP; SELECT length FROM = size => BEGIN (base+frobject.fwdp).backp ← frobject.backp; (base+frobject.backp).fwdp ← frobject.fwdp; table.free.size ← table.free.size + size; ProcessDefs.EnableInterrupts[]; RETURN[frobject]; END; > size => BEGIN frobject.size ← length - size; table.free.size ← table.free.size + size; ProcessDefs.EnableInterrupts[]; RETURN[frobject+length-size]; END; ENDCASE => frobject.size ← length; ENDLOOP; END; ENDLOOP; table ← AllocateTable[! UNWIND => ProcessDefs.EnableInterrupts[]]; frob ← table.free.fwdp; frobject ← LOOPHOLE[table, CARDINAL]+frob; frobject.size ← frobject.size - size; table.free.size ← table.free.size + size; ProcessDefs.EnableInterrupts[]; RETURN[frobject+frobject.size]; END; LiberateObject: PUBLIC PROCEDURE [object: ObjectHandle] = BEGIN table: TableHandle ← SegmentDefs.PagePointer[object]; size, base: CARDINAL; frob: FrobLink ← LOOPHOLE[InlineDefs.BITAND[LOOPHOLE[object], 377B]]; base ← LOOPHOLE[table]; ValidateObject[object]; size ← WITH o: object SELECT FROM segment => SELECT o.type FROM data => SIZE[data segment Object], ENDCASE => SIZE[file segment Object], file => SIZE[file Object], ENDCASE => SIZE[length Object]; ProcessDefs.DisableInterrupts[]; IF (table.free.size ← table.free.size - size) = 0 THEN LiberateTable[table ! UNWIND => ProcessDefs.EnableInterrupts[]] ELSE BEGIN object↑ ← Object[FALSE, free[seal: ObjectSeal, size: size, fwdp: table.free.fwdp, backp: FIRST[FrobLink]]]; (base+table.free.fwdp).backp ← frob; table.free.fwdp ← frob; END; ProcessDefs.EnableInterrupts[]; RETURN END; AllocateTable: PROCEDURE RETURNS [newTable: TableHandle] = BEGIN OPEN BootDefs, SegmentDefs; frob: FrobLink = LOOPHOLE[SIZE[Table]]; base: CARDINAL; page: PageNumber; page ← alloc.alloc[DefaultBase, 1, NIL, AllocDefs.DefaultTableSegmentInfo]; newTable ← AddressFromPage[page]; newTable↑ ← Table[[FALSE, free[ObjectSeal,0, frob, frob]],systemTable.table,NIL]; base ← LOOPHOLE[newTable]; (base+frob)↑ ← [FALSE, free[ObjectSeal, AltoDefs.PageSize-SIZE[Table], FIRST[FrobLink], FIRST[FrobLink]]]; systemTable.table ← newTable; systemTable.table.seg ← BootDataSegment[page, 1]; RETURN END; LiberateTable: PROCEDURE [table:TableHandle] = BEGIN current: TableHandle; prev: TableHandle ← NIL; FOR current ← systemTable.table, current.link UNTIL current = NIL DO IF current = table THEN BEGIN IF prev = NIL THEN systemTable.table ← current.link ELSE prev.link ← current.link; -- oops: this had better not recur! DeleteDataSegment[current.seg]; RETURN END; prev ← current; ENDLOOP; ERROR InvalidObject[table]; END; ValidateObject: PUBLIC PROCEDURE [object:ObjectHandle] = BEGIN t: TableHandle; table: TableHandle = PagePointer[object]; BEGIN IF object = NIL OR InlineDefs.BITAND[LOOPHOLE[object, CARDINAL], 1] = 1 OR object.tag = free THEN GOTO invalid; IF table.free.seal # ObjectSeal THEN GOTO invalid; FOR t ← systemTable.table, t.link UNTIL t = NIL DO IF t = table THEN EXIT; REPEAT FINISHED => GOTO invalid; ENDLOOP; EXITS invalid => ERROR InvalidObject[object]; END; RETURN END; EnumerateObjects: PUBLIC PROCEDURE [type: ObjectType, proc:PROCEDURE [ObjectHandle] RETURNS [BOOLEAN]] RETURNS [object: ObjectHandle] = BEGIN i, j: CARDINAL; table: TableHandle; FOR table ← systemTable.table, table.link UNTIL table = NIL DO j ← i ← SIZE[BootDefs.Table]; FOR object ← @table.free + i, object + i UNTIL j >= AltoDefs.PageSize DO i ← WITH obj:object SELECT FROM segment => SELECT obj.type FROM data => SIZE[data segment Object], ENDCASE => SIZE[file segment Object], file => SIZE[file Object], free => obj.size, ENDCASE => SIZE[length Object]; j ← j + i; IF object.tag = type AND proc[object] THEN RETURN[object]; ENDLOOP; ENDLOOP; RETURN[NIL] END; -- Managing Data Segment Objects AllocateDataSegment: PROCEDURE RETURNS [DataSegmentHandle] = BEGIN RETURN[LOOPHOLE[AllocateObject[SIZE[data segment Object]]]]; END; ValidateDataSegment: PROCEDURE [DataSegmentHandle] = LOOPHOLE[ValidateObject]; LiberateDataSegment: PROCEDURE [DataSegmentHandle] = LOOPHOLE[LiberateObject]; GetSystemTable: PUBLIC PROCEDURE RETURNS [BootDefs.SystemTableHandle] = BEGIN RETURN[@systemTable]; END; -- Main body systemTable: BootDefs.SystemTable ← BootDefs.SystemTable[@PageMap, NIL]; systemObject: AllocDefs.AllocObject ← [ PageAvailable, PageStatus, UpdateVM, XAllocVM]; alloc: AllocHandle ← @systemObject; EnableBank: PUBLIC PROCEDURE [b: XMesaDefs.BankIndex] = --XM BEGIN IF PageMaps[b] # NIL THEN allocState[b].bankAvailable ← TRUE ELSE InitBank[b]; END; DisableBank: PUBLIC PROCEDURE [b: XMesaDefs.BankIndex] = --XM BEGIN allocState[b].bankAvailable ← FALSE; END; InitBank: PROCEDURE [bx: XMesaDefs.BankIndex] = --XM BEGIN OPEN XMESA, XMesaDefs; i: PageNumber; bankPageMap: POINTER TO BootDefs.PageMap; IF bx#0 THEN BEGIN ffvmp ← bx*PagesPerBank; lfvmp ← ffvmp+PagesPerBank-3; END; allocState[bx] ← [ffvmp: ffvmp, lfvmp: lfvmp, pageRover: ffvmp, nFree: lfvmp-ffvmp+1, bankAvailable: TRUE]; bankPageMap ← PageMaps[bx] ← IF bx=0 THEN LOOPHOLE[@PageMap] ELSE (PageMap[bx+Bank1X-1] ← DataSegmentAddress[MakeDataSegment[DefaultBase0, 1, PageMapAllocInfo]]); FOR i IN [0..PagesPerBank) DO bankPageMap[i] ← IF i+bx*PagesPerBank IN [ffvmp .. lfvmp] THEN FreePage ELSE BusyPage; ENDLOOP; END; Init: PROCEDURE = -- almost completely rewritten for XMESA -- --XM BEGIN OPEN XMESA, XMesaDefs; bx: BankIndex; memoryConfig: MemoryConfig ← GetMemoryConfig[]; FOR bx IN BankIndex DO IF (~memoryConfig.useXM AND bx # 0) OR InlineDefs.BITAND[memoryConfig.banks, BankMasks[bx]] = 0 THEN BEGIN -- bank not available on this Alto; set so can't be used (will never be executed for bx=0) allocState[bx].nFree ← 0; allocState[bx].bankAvailable←FALSE; allocState[bx].ffvmp ← bx*PagesPerBank; allocState[bx].lfvmp ← allocState[bx].ffvmp-1; PageMaps[bx] ← PageMap[bx+Bank1X-1] ← NIL; END ELSE InitBank[bx]; ENDLOOP; END; Init[]; END.