-- 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.