-- Swapper>CachedRegionImplB.mesa (September 15, 1982 8:36 pm by Levin) -- Things to consider: -- 1) Analyze dynamic usage of MStore.Relocate for possible inline cases -- This program implements operations on regions and swap units and provides higher-level access to region descriptors. -- Implementation notes: -- Exclusive access to the region cache is provided by the monitor lock of CachedRegionImplA. Exclusive access to individual region descriptors is provided by the checkedOut field in the descriptors in the cache. Exclusive access to a region is provided by temporarily removing the region from its normal place in the client's address space. -- Whenever a change is made to the region descriptor which would imply a change in the corresponding Projection entry, the descriptor must be marked dDirty. This means any change to hasSwapUnits, writeProtected, needsLogging, or any transition in "state" between unmapped, outDead, and IN Alive. -- If a region is being remapped, there are two possible windows in which a swap unit may reside. -- Note that a swap unit which is In may nevertheless have zero real pages assigned, if it is past the end of the mapping file. -- When a swap unit needs to be swapped out, it is important that the program determine whether the pages actually be written to the disk (i.e. they are dirty) BEFORE getting the mapping space descriptor. This allows us to deallocate clean things even if their mapping space descriptor is not in the cache. -- Caveats: -- The proper operation of flush, remap, unmap is dependent on there being only one client operating on the swap units of a region at a time, and that the client applies the particular operation (successfully) once for each swap unit in the region. (This restriction does not apply to activate[why=pageFault] and age[] operations, which may happen asynchronously.) To put it another way, a region (space) should not be simultaneously operated on both by SpaceImpl and by SimpleSpaceImpl. Furthermore, the current implementation demands that there be only one space being remapped at any given instant! -- If a swap unit is in, and its region is inPinned, we promise that it will be continuously present at its assigned address. The way ForkWrite is currently implemented, we may not forceOut the swap unit for this reason. DIRECTORY CachedRegion USING [AliveSwappable, Desc, DescAvailable, In, InSwappable, Operation, Outcome, PageLocationInSpace, State, Swappable], CachedRegionInternal USING [AwaitNotCheckedOut, CheckIn, CheckOut], CachedSpace USING [DataOrFile, Desc, Get, Handle, SizeSwapUnit], Environment USING [bitsPerWord, Word, wordsPerPage], File USING [lastPageNumber, PageNumber], FilePageTransfer USING [Initiate, Wait], Inline USING [BITAND, LongCOPY], MStore USING [Allocate, Deallocate, Relocate], PageFault USING [RestartPageFault], PageMap USING [ Flags, flagsClean, flagsDirty, --flagsDirtyReferenced,--flagsNone, flagsNotReferenced, flagsReferenced, flagsVacant, flagsWriteProtected, GetF, SetF, Value], Process USING [GetPriority, Priority, SetPriority], ProcessInternal USING [DisableInterrupts, EnableInterrupts], ProcessPriorities USING [priorityPageFaultHigh], SwapBuffer USING [Allocate, Deallocate], SwapperPrograms, SwapTask USING [Advance, Fork, State], Utilities USING [Bit, BitGet, BitPut, LongPointerFromPage, PageFromLongPointer], VM USING [Interval, PageCount, PageNumber, PageOffset], VMMapLog USING [ Descriptor, PatchTable, PatchTableEntry, PatchTableEntryBasePointer, PatchTableEntryPointer]; CachedRegionImplB: PROGRAM [pMapLogDesc: LONG POINTER] IMPORTS CachedRegionInternal, CachedSpace, FilePageTransfer, Inline, MStore, PageFault, PageMap, Process, ProcessInternal, SwapBuffer, SwapTask, Utilities EXPORTS CachedRegion, SwapperPrograms SHARES File, PageMap = BEGIN OPEN CachedRegion; flagsDirtyReferenced: PageMap.Flags = [writeProtected: FALSE, dirty: TRUE, referenced: TRUE]; -- should be in PageMap! (AR 5157) maskNotReferenced: PageMap.Value = [ logSingleError: LOOPHOLE[1], flags: PageMap.flagsNotReferenced, realPage: LOOPHOLE[7777B]]; Bug: PRIVATE ERROR [BugType] = CODE; BugType: TYPE = { badSwapUnitSize, copyInButNotSwappable, copyInButReadOnly, copyOutButNotSwappable, copyOutToProtected, deadButSwapUnits, deadReadOnlyRegion, flushButPinned, funnyAction, funnyOutcome, funnyState, makeWritableButNotSwappable, mapButNotUnmapped, mapProtectedDataSpace, pinUnmapped, readButAlreadyIn, regionSpaceInconsistent, remapButNotSwappable, remapButReadOnly, remapButUnmapped, remapSpaceTooBig, remapToReadOnly, swapUnitsOnRealSpace, writeProtectAndNeedsLogging, writeProtectedAndNeedsLogging, writeProtectButPinned}; PatchTableIndex: TYPE = [0..50); patchTable: MACHINE DEPENDENT RECORD [ header: VMMapLog.PatchTable, body: ARRAY PatchTableIndex OF VMMapLog.PatchTableEntry]; inSwappableCold: InSwappable _ inSwappableWarmest; -- for age Operation. If region temperature is inSwappableCold and it has not been referenced, it will be swapped out. (A variable so we can experiment with it using the debugger.) pageLocationInSpace: PUBLIC PageLocationInSpace _ DESCRIPTOR[NIL, 0]; -- array supplied by caller of remap. If a swap unit is Out during a remap operation, this specifies which window it is in (the old or the new). Current implementation is: an array of bits, one for each page in the space being remapped. We use the bit corresponding to the first page of each swap unit to specify the swap unit's location. Initialize: PROCEDURE = BEGIN priorityPrev: Process.Priority; throwAway: PROCESS; patchTable.header _ [limit: FIRST[VMMapLog.PatchTableEntryPointer], maxLimit: LOOPHOLE[SIZE[VMMapLog.PatchTableEntry] * LENGTH[patchTable.body]], entries:]; LOOPHOLE[pMapLogDesc, LONG POINTER TO VMMapLog.Descriptor].patchTable _ @patchTable.header; priorityPrev _ Process.GetPriority[]; Process.SetPriority[ProcessPriorities.priorityPageFaultHigh]; throwAway _ FORK PageTransferProcess[]; -- region cache must -- have been initialized previously. Process.SetPriority[priorityPrev]; END; Apply: PUBLIC PROCEDURE [pageMember: VM.PageNumber, operation: Operation] RETURNS [outcome: Outcome, pageNext: VM.PageNumber] = -- The "operation" acts on the swap unit containing pageMember, except that get, map, and unpin always act on the entire region. Sets pageNext to the start of the next swap unit or region if a descriptor for the region containing pageMember is in the region descriptor cache; else sets pageNext to start of the next region in the cache (possibly having state=missing); if no next region, sets pageNext to pageTop. BEGIN region: Desc; -- When the "region" desc is gotten from the region cache, if the region ~hasSwapUnits, region.state is the truth. If the region hasSwapUnits and region.state IN AliveSwappable, the specific value of state is meaningless. In this case, region.state is supplied by Apply from [inSwappableColdest..outAlive] using the page flags. If the region hasSwapUnits and region.state = inPinned, outDead, or unMapped, region.state shows the target state for all of the swap units. endRegion: VM.PageNumber; -- the page following the region. swapInterval: VM.Interval; -- the interval of the swap unit. (If the region does not have swap units, the swap interval is the whole region.) inOutState: {in, out}; -- in means that there are pages in this swap unit that are mapped and they are now in memory. out means either that there are no mapped pages in this swap unit, or that they are not currently in memory. Note that region.state could be IN In, and yet have inOutState=out, in the case that there are no mapped pages in the swap unit. Therefore, if an operation demands that a swap unit be in, it must check to see if there are any mapped pages in the swap unit. gotMappingSpaceDesc, gotParentSpaceDesc: BOOLEAN; mappingSpace, parentSpace: CachedSpace.Desc; -- Parent and mapping space may or may not be same. ioStarted: BOOLEAN; -- Note: as soon as ioStarted is set to TRUE (by ForkRead or ForkWrite), the region descriptor must be considered read-only by this procedure (i.e. no further state transitions). -- Variables declared before here are referenced globally by Apply's local procedures. GetMappingSpaceDesc: PROCEDURE RETURNS [gotIt: BOOLEAN] = BEGIN IF ~gotMappingSpaceDesc THEN BEGIN OPEN region --USING[level,levelMapped,interval]--; IF gotParentSpaceDesc AND levelMapped = level THEN mappingSpace _ parentSpace ELSE CachedSpace.Get[ @mappingSpace, CachedSpace.Handle[levelMapped, interval.page]]; gotMappingSpaceDesc _ TRUE; END; IF mappingSpace.state = missing THEN { outcome _ [spaceDMissing[region.levelMapped]]; RETURN[gotIt: FALSE]} ELSE RETURN[gotIt: TRUE]; END; OldNew: TYPE = {oldWindow, newWindow}; InWindow: PROCEDURE [pageInSpace: VM.PageNumber] RETURNS [which: OldNew] = INLINE BEGIN -- Which window is this page in? RETURN[LOOPHOLE[Utilities.BitGet[ BASE[pageLocationInSpace], pageInSpace - mappingSpace.interval.page]]] END; MarkInWindow: PROCEDURE [which: OldNew, pageInSpace: VM.PageNumber] = INLINE -- Mark that this page is in which window. BEGIN Utilities.BitPut[ LOOPHOLE[which, Utilities.Bit], BASE[pageLocationInSpace], pageInSpace - mappingSpace.interval.page] END; ReadDead: PROCEDURE [ bufferPage: VM.PageNumber, offsetInSwapUnit: VM.PageOffset, count: VM.PageCount] = -- Zeroes out given area in buffer and relocates back into the swap unit, marking the pages dirty in the process. -- (The swap unit must be out and dead, and not writeProtected.) BEGIN pFirst: LONG POINTER TO Environment.Word; offset: VM.PageOffset; IF region.writeProtected OR region.needsLogging THEN Bug[deadReadOnlyRegion]; -- can't write into readOnly region. region.dDirty _ TRUE; -- changing from dead to alive FOR offset IN [0..count) DO pFirst _ Utilities.LongPointerFromPage[ bufferPage + offsetInSwapUnit + offset]; pFirst^ _ 0; Inline.LongCOPY[ from: pFirst, nwords: Environment.wordsPerPage - 1, to: pFirst + 1]; ENDLOOP; [] _ MStore.Relocate[ [bufferPage + offsetInSwapUnit, count], swapInterval.page + offsetInSwapUnit, PageMap.flagsNone, PageMap.flagsDirty]; END; SetSwapUnitInfo: PROCEDURE [] = INLINE -- Sets up parameters for a Uniform Swap Unit of a region. BEGIN swapInterval.page _ pageMember - ((pageMember - region.interval.page) MOD parentSpace.sizeSwapUnit); pageNext _ MIN[endRegion, swapInterval.page + parentSpace.sizeSwapUnit]; -- the start of the next swap unit or region (the last swap unit may be short). swapInterval.count _ pageNext - swapInterval.page; inOutState _ IF PageMap.GetF[swapInterval.page].valueOld.flags = PageMap.flagsVacant THEN out ELSE in; -- look at page flags to find if this swap unit is in or out: IF region.state IN Swappable THEN -- (leave unmapped and inPinned alone) { IF region.state = outDead THEN Bug[deadButSwapUnits]; region.state _ (IF inOutState = out THEN outAlive -- no way to tell whether dead or alive! ELSE inSwappableCold) }; -- must be inSwappableCold if swap units are ever going to be aged out. END; ForkRead: PROCEDURE [stateNext: State] = -- Implicit input parameters: operation.action, region, swapInterval, inOutState, pageMember, parentSpace, gotParentSpaceDesc. Implicit output parameters: region.state, region.dDirty, ioStarted, outcome. -- Normal operation: The swap unit must be out. Starts input of the swap unit from the mapping space's window. If the swap unit is dead, no reading is done, but instead real memory is allocated, initialized to zero, and marked dirty (and region.dDirty is set, reflecting the transition from dead to alive). At completion of input, flags are set on all pages using region.writeProtected and region.needsLogging. On return, region.state is set to stateNext. -- Operation for copyIn[from]: The swap unit may be in or out. If it is in, it is data from the current window. Reads leading pages from the other window "from" and makes them dirty, then reads (as required) further pages from the current window. If no pages are required from the other window, ForkRead is a no-op. -- Operation for remapB[from]: mappingSpace will have changed to the new window, "from" describes the old window. The swap unit may be in or out. If it is In, it is data from the old window. Reads in (as required) leading pages from the old window, then reads (as required) further pages from the current window, then deallocates (as required) any further pages not mapped in the current window. Any pages that came from the old window are marked dirty. -- Operation notes: -- If the mapping space desc is not available, outcome will bet set to [spaceDMissing[]], and no other action taken. -- If any reading is necessary, it is initiated and ioStarted set to TRUE. At this point, the region descriptor must be read-only to Apply, since a copy of it is bundled with the read request ("SwapTask"). The PageTransferProcess (see below) completes the input, and when complete, checks in the (copy of the) region descriptor. -- Real memory is allocated and freed as necessary. BEGIN buffer: VM.Interval; -- buffer for swapping. Size of mapped part of swap unit. offsetInSpace: VM.PageOffset; -- offset of swap unit in mapping space. countmapped: VM.PageCount; -- number of mapped pages in this swap unit. currentState: State _ region.state; -- the state of the region at entry to ForkRead. IF ~GetMappingSpaceDesc[].gotIt THEN RETURN; -- (outcome=[spaceDMissing] has been set.) region.state _ stateNext; -- sets the state of the region when IO is completed (so we're committed at this point). IF region.writeProtected AND ~mappingSpace.writeProtected THEN ERROR Bug[regionSpaceInconsistent]; -- region/space unallowably inconsistent. offsetInSpace _ swapInterval.page - mappingSpace.interval.page; countmapped _ IF mappingSpace.countMapped <= offsetInSpace THEN 0 ELSE MIN[ swapInterval.count, CARDINAL[mappingSpace.countMapped - offsetInSpace]]; buffer _ SwapBuffer.Allocate[countmapped]; WITH operation SELECT FROM copyIn --[from]-- => BEGIN offsetInOtherSpace: VM.PageOffset = swapInterval.page - from.interval.page; -- offset of swap unit in other space. countmappedOther: VM.PageCount -- number of mapped pages in this swap unit mapped in "from" (never more than countmapped). = IF from.countMapped <= offsetInOtherSpace THEN 0 ELSE MIN[ countmapped, CARDINAL[from.countMapped - offsetInOtherSpace]]; notMappedInOther: VM.PageCount -- number of mapped pages in this swap unit not mapped in "from". = IF countmapped <= countmappedOther THEN 0 ELSE CARDINAL[countmapped - countmappedOther]; IF countmappedOther > 0 THEN -- there's something to do.. BEGIN countToTransfer: VM.PageCount = countmappedOther + (IF inOutState = out AND currentState ~= outDead THEN notMappedInOther ELSE 0); IF region.writeProtected OR (~region.hasSwapUnits AND region.needsLogging) THEN Bug[copyInButReadOnly]; -- can't dirty it and writeProtect it. [] _ SwapTask.Fork[ [swapInterval.page, buffer.count], PageMap.flagsDirty, buffer.page, --countRemaining:--countToTransfer, region]; ioStarted _ TRUE; -- since we know countToTransfer>0. IF inOutState = out THEN BEGIN MStore.Allocate[buffer]; IF currentState = outDead THEN -- zero out trailing pages only mapped in current window: ReadDead[ bufferPage: buffer.page, offsetInSwapUnit: countmappedOther, count: notMappedInOther] ELSE --currentState=outAlive-- [] _ FilePageTransfer.Initiate[ [ -- read in trailing pages only mapped in current window: -- file: mappingSpace.window.file, filePage: mappingSpace.window.base + offsetInSpace + countmappedOther, memoryPage: buffer.page + countmappedOther, count: notMappedInOther, opSpecific: read[priorityPage: File.lastPageNumber]]]; END ELSE --inOutState=in-- -- Move the real mem under pages mapped in other window up to swap buffer: [] _ MStore.Relocate[ [swapInterval.page, countmappedOther], buffer.page, PageMap.flagsNone, PageMap.flagsClean]; -- Always read in pages mapped in other window: [] _ FilePageTransfer.Initiate[ [ file: from.window.file, filePage: from.window.base + offsetInOtherSpace, memoryPage: buffer.page, count: countmappedOther, opSpecific: read[priorityPage: File.lastPageNumber]]] END; END; remapB --[from]-- => -- Note: there's a lot of code in common here with copyIn. It is kept separate so that we can conveniently throw it away when Remap is retired. BEGIN countmappedOther: VM.PageCount -- number of mapped pages in this swap unit coming from "from" -- (never more than countmapped). = IF from.countMapped <= offsetInSpace THEN 0 ELSE MIN[countmapped, CARDINAL[from.countMapped - offsetInSpace]]; -- Number of mapped pages in this swap unit not mapped in "from": notMappedInOther: VM.PageCount = IF countmapped <= countmappedOther THEN 0 ELSE CARDINAL[countmapped - countmappedOther]; countToTransfer: VM.PageCount = notMappedInOther + (IF inOutState = out AND currentState ~= outDead THEN countmappedOther ELSE 0); IF region.writeProtected OR region.needsLogging THEN Bug[remapButReadOnly]; -- can't dirty it and writeProtect it. [] _ SwapTask.Fork[ [swapInterval.page, buffer.count], PageMap.flagsDirty, buffer.page, --countRemaining:--countToTransfer, region]; ioStarted _ (countToTransfer > 0); IF inOutState = out THEN BEGIN MStore.Allocate[buffer]; IF currentState = outDead THEN -- zero out leading pages mapped in other (old) window. ReadDead[ bufferPage: buffer.page, offsetInSwapUnit: 0, count: countmappedOther] ELSE --currentState=outAlive-- [] _ FilePageTransfer.Initiate[ [ -- read in leading pages mapped in other (old) window. file: from.window.file, filePage: from.window.base + offsetInSpace, memoryPage: buffer.page, count: countmappedOther, opSpecific: read[priorityPage: File.lastPageNumber]]]; END ELSE --inOutState=in-- -- (note that the stuff that is in is from the old window.) { [] _ MStore.Relocate[ [swapInterval.page, countmappedOther], swapInterval.page, PageMap.flagsReferenced, PageMap.flagsDirty]; -- make the pages from the old window that are in be dirty. MStore.Deallocate[ [page: swapInterval.page + countmapped, count: swapInterval.count - countmapped], --promised:--FALSE]; -- free any pages no longer mapped by current (new) window. MStore.Allocate[ [page: buffer.page + countmappedOther, count: notMappedInOther]]}; -- allocate any pages that weren't mapped by old window. [] _ FilePageTransfer.Initiate[ [ -- always read in any pages only mapped in current (new) window. file: mappingSpace.window.file, filePage: mappingSpace.window.base + offsetInSpace + countmappedOther, memoryPage: buffer.page + countmappedOther, count: notMappedInOther, opSpecific: read[priorityPage: File.lastPageNumber]]]; END; ENDCASE --all normal operations-- => IF countmapped > 0 THEN -- there's something to do.. BEGIN IF inOutState = in THEN ERROR Bug[readButAlreadyIn]; MStore.Allocate[buffer]; IF currentState = outDead THEN -- zero out buffer area and relocate back into region ReadDead[ bufferPage: buffer.page, offsetInSwapUnit: 0, count: countmapped] ELSE --currentState=outAlive--{ [] _ SwapTask.Fork[ [swapInterval.page, buffer.count], IF region.writeProtected OR region.needsLogging THEN PageMap.flagsWriteProtected ELSE PageMap.flagsClean, buffer.page, --countRemaining:--countmapped, region]; ioStarted _ TRUE; -- since we know countmapped>0. [] _ FilePageTransfer.Initiate[ [file: mappingSpace.window.file, filePage: mappingSpace.window.base + offsetInSpace, memoryPage: buffer.page, count: countmapped, opSpecific: read[ priorityPage: mappingSpace.window.base + offsetInSpace + (pageMember - swapInterval.page)]]]}; END; IF ~ioStarted THEN SwapBuffer.Deallocate[buffer]; -- (If ioStarted, PageTransferProcess will deallocate the buffer.) END; ForkWrite: PROCEDURE [stateNext: State] = -- Implicit input parameters: operation.action, region, swapInterval, inOutState, pageMember, parentSpace, gotParentSpaceDesc. Implicit output parameters: region.state, region.dDirty, ioStarted, outcome. -- Normal operation: The swap unit must be in. Starts output of the swap unit to the mapping space's window. If the swap unit is clean, no writing is done, but instead the real memory is just freed. At competion of input, flags are set on all pages using region.writeProtected and region.needsLogging. On return, region.state is set to stateNext. -- Operation for copyOut[to]: The swap unit must be in. Writes leading pages to the other window "to" - even if they are clean. stateNext must be equal to the current region.state. -- Operation notes: -- If the mapping space desc is not available, outcome will bet set to [spaceDMissing[]], and no other action taken. -- If any writing is necessary, it is initiated and ioStarted set to TRUE. At this point, the region descriptor must be read-only to Apply, since a copy of it is bundled with the write request ("SwapTask"). The PageTransferProcess (see below) completes the input, and when complete, checks in the (copy of the) region descriptor. -- Real memory is freed as appropriate. -- NOTE: Do not change region.state until all possibility of backing out has passed! BEGIN WITH operation SELECT FROM copyOut --[to]-- => -- move this code to main Apply copyOut arm? IF GetMappingSpaceDesc[].gotIt THEN BEGIN -- All needed resources have been acquired; can now change the state. offsetInSpace: VM.PageOffset = -- offset of swap unit in mapping space. swapInterval.page - mappingSpace.interval.page; countmapped: VM.PageCount = -- number of mapped pages in this swap unit. IF mappingSpace.countMapped <= offsetInSpace THEN 0 ELSE MIN[ swapInterval.count, CARDINAL[ mappingSpace.countMapped - offsetInSpace]]; offsetInOtherSpace: VM.PageOffset = -- offset of swap unit in other space. swapInterval.page - to.interval.page; countmappedOther: VM.PageCount = -- number of mapped pages in this swap unit going to "to" (never more than countmapped). IF to.countMapped <= offsetInOtherSpace THEN 0 ELSE MIN[countmapped, to.countMapped - offsetInOtherSpace]; IF region.writeProtected AND ~mappingSpace.writeProtected THEN ERROR Bug[regionSpaceInconsistent]; -- region/space unallowably inconsistent. region.state _ stateNext; -- now that we're committed. IF countmappedOther > 0 THEN -- there's something to do.. BEGIN buffer: VM.Interval = SwapBuffer.Allocate[countmappedOther]; -- The swap unit is relocated and protected during write to delay client references in order to allow us to maintain the referenced and dirty status bits, and to assure that an I/O device can compute a consistent checksum. Protecting it is also a flag to PageTransferProcess that these pages are being written, not read, so don't apply patches. flags: PageMap.Flags = MStore.Relocate[ [swapInterval.page, countmappedOther], buffer.page, PageMap.flagsNone, PageMap.flagsWriteProtected].flags; [] _ SwapTask.Fork[ [swapInterval.page, countmappedOther], flags, buffer.page, --countRemaining:--countmappedOther, region]; ioStarted _ TRUE; [] _ FilePageTransfer.Initiate[ [ -- always write pages mapped in other window. file: to.window.file, filePage: to.window.base + offsetInOtherSpace, memoryPage: buffer.page, count: countmappedOther, promise: FALSE, -- since we are leaving the stuff in memory, we don't need to promise it. opSpecific: write[]]]; END; END; --copyOut-- ENDCASE --all normal operations-- => BEGIN flagsFirst: PageMap.Flags = PageMap.GetF[ swapInterval.page].valueOld.flags; IF flagsFirst ~= PageMap.flagsVacant AND ~flagsFirst.writeProtected THEN BEGIN --mapped and writable-- buffer: VM.Interval = SwapBuffer.Allocate[swapInterval.count]; -- could actually scan nonvacant prefix of swapInterval. flags: PageMap.Flags _ MStore.Relocate[ swapInterval, buffer.page, PageMap.flagsNone, PageMap.flagsWriteProtected].flags; flags.writeProtected _ region.writeProtected OR region.needsLogging; IF ~flags.dirty THEN -- matches backing file.. BEGIN --no writing required-- region.state _ stateNext; -- now that we're committed. IF region.state IN In THEN -- put it back where it was [] _ MStore.Relocate[ buffer, swapInterval.page, PageMap.flagsNone, flags] ELSE MStore.Deallocate[interval: buffer, promised: FALSE]; -- throw it away SwapBuffer.Deallocate[buffer]; END --no writing required-- ELSE BEGIN --writing required-- IF GetMappingSpaceDesc[].gotIt THEN BEGIN --got space desc-- -- All needed resources have been acquired; can now change the state. offsetInSpace: VM.PageOffset = swapInterval.page - mappingSpace.interval.page; countmapped: VM.PageCount = IF mappingSpace.countMapped <= offsetInSpace THEN 0 ELSE MIN[ swapInterval.count, CARDINAL[ mappingSpace.countMapped - offsetInSpace]]; IF region.writeProtected AND ~mappingSpace.writeProtected THEN ERROR Bug[regionSpaceInconsistent]; -- region/space unallowably inconsistent. region.state _ stateNext; -- now that we're committed. flags.dirty _ FALSE; [] _ SwapTask.Fork[ [swapInterval.page, buffer.count], flags, buffer.page, countmapped, region]; ioStarted _ TRUE; -- since we know countmapped>0. FilePageTransfer.Initiate[ [file: mappingSpace.window.file, filePage: mappingSpace.window.base + offsetInSpace, memoryPage: buffer.page, count: countmapped, promise: ~(region.state IN In), -- promise the real mem if it will be freed. opSpecific: write[]]]; END --got space desc-- ELSE { -- couldn't get mapping space. Back out. [] _ MStore.Relocate[ buffer, swapInterval.page, PageMap.flagsNone, flags]; SwapBuffer.Deallocate[buffer] }; END; --writing required-- END --mapped and writable-- ELSE { --vacant or writeProtected-- region.state _ stateNext; -- now that we're committed. IF ~(region.state IN In) THEN MStore.Deallocate[interval: swapInterval, promised: FALSE] }; END; --all normal operations-- END; -- Main body of Apply: gotMappingSpaceDesc _ FALSE; gotParentSpaceDesc _ FALSE; ioStarted _ FALSE; region _ CachedRegionInternal.CheckOut[pageMember, operation.ifCheckedOut]; pageNext _ endRegion _ region.interval.page + region.interval.count; -- assume ~hasSwapUnits outcome _ [ok[]]; SELECT region.state FROM = checkedOut => --Operation.ifCheckedOut=skip--NULL; = missing => -- in this case, the value returned for pageNext is the start of the next region known in the region cache (see CheckOut). IF operation.ifMissing = report THEN outcome _ [regionDMissing[]] ELSE --operation.ifMissing=skip--NULL; IN DescAvailable => BEGIN OPEN region; --scope of Exit, etc.-- BEGIN IF beingFlushed AND operation.action ~= flush THEN -- we pretend the desc has already been flushed. { IF operation.ifMissing = report THEN outcome _ [regionDMissing[]]; --ELSE ++operation.ifMissing=skip++ NULL; GO TO Exit}; IF operation.action ~= get THEN -- (swapInterval, etc., not needed for get) BEGIN --non-get action-- IF ~hasSwapUnits THEN BEGIN swapInterval _ interval; inOutState _ IF PageMap.GetF[swapInterval.page].valueOld.flags = PageMap.flagsVacant THEN out ELSE in; END ELSE --hasSwapUnits-- BEGIN -- set interval and state of the swap unit: CachedSpace.Get[ @parentSpace, CachedSpace.Handle[ level: level, page: interval.page]]; -- get desc of immediate parent to get sizeSwapUnit. IF parentSpace.state = missing THEN { outcome _ [spaceDMissing[level]]; GO TO Exit} ELSE --parent space desc available-- BEGIN gotParentSpaceDesc _ TRUE; IF ~(parentSpace.sizeSwapUnit IN CachedSpace.SizeSwapUnit) OR ~parentSpace.hasSwapUnits THEN ERROR Bug[badSwapUnitSize]; -- improper use or region/space inconsistent. SetSwapUnitInfo[]; END; END; END; --non-get action-- WITH operation SELECT FROM activate --[why]-- => -- (activate[why:activate] is a hint and is legal on unmapped regions.) IF state = unmapped THEN { IF why = pagefault THEN GO TO AddressFault ELSE --why=activate--NULL} -- ignore the hint ELSE --state IN Mapped-- BEGIN IF ~GetMappingSpaceDesc[].gotIt THEN GO TO Exit; -- (outcome=[spaceDMissing] has been set.) IF why = pagefault AND pageMember >= mappingSpace.interval.page + mappingSpace.countMapped THEN GO TO AddressFault; IF inOutState = out THEN BEGIN IF mappingSpace.state = beingRemapped THEN -- the space desc has changed to the new window IF InWindow[swapInterval.page] = oldWindow THEN GO TO Exit; -- the swap unit needs to be read from the old window (but the space desc has changed to the new window and we don't know the old window right now). We ignore the request for now, and this (pagefault) request will be satisfied when the region is read in by remapB. ForkRead[ stateNext: IF state = inPinned THEN inPinned ELSE inSwappableWarmest] -- inSwappableWarmest is ok here for swap units. ForkRead will take care of any dead-to-alive transition. END -- ELSE ++inOutState=in++ -- IF why=pagefault THEN NULL ++the page is now in (it has been brought in since the pagefault) -- ELSE ++why=activate++ NULL; ++ it was already in! That's fine. END; age => BEGIN IF ~hasSwapUnits THEN GO TO SwapOut -- FindUnreferenced has selected this region to kick out. ELSE --hasSwapUnits-- IF ~(state IN Swappable) THEN { pageNext _ endRegion; GO TO Exit } --go to next region-- ELSE --hasSwapUnits AND Swappable-- -- The following block of code should be in FindUnreferenced but is not since it does not have access to the size of the UniformSwapUnits in the region. BEGIN -- loop through swap units, clearing ref'd bits and looking for an unreferenced one to swap out.. valueRegion: PageMap.Value = [ -- legal target flags for region. These flags are not definitive since needsLogging is just a hint. logSingleError: FALSE, flags: [writeProtected: writeProtected OR needsLogging, dirty: --assume--FALSE, referenced: --desired end state--FALSE], realPage: NULL]; --WHILE still in a swap unit of the same region-- DO IF inOutState=in THEN BEGIN -- swap out if not ref'd; else clear ref'd bits: value: PageMap.Value; referenced: BOOLEAN _ FALSE; FOR page: VM.PageNumber _ swapInterval.page, SUCC[page] WHILE page BEGIN IF ~(state IN InSwappable) THEN GO TO Exit; -- THIS STUFF MUST BE DONE INSIDE ForkWrite! -WDK -- IF ~GetMappingSpaceDesc[].gotIt THEN GO TO Exit; -- IF mappingSpace.state = beingRemapped THEN ++ The space desc has changed to the new window. We don't write the region into the new window because we don't have the countMapped of the old mapping space handy. -- GO TO Exit; ForkWrite[stateNext: outAlive]; END; END; clean --[andWriteProtect, andNeedsLogging]-- => BEGIN IF state IN Swappable THEN BEGIN IF state = outDead THEN { ForkRead[stateNext: inSwappableWarmest]; -- get the stuff in and dirty to assure initialized to zeroes. GO TO Retry} -- better luck next time. ELSE --state IN AliveSwappable-- BEGIN writeProtected _ writeProtected OR andWriteProtect; needsLogging _ needsLogging OR andNeedsLogging; IF needsLogging THEN { writeProtected _ FALSE; --IF andWriteProtect THEN Bug[writeProtectAndNeedsLogging]-- }; dDirty _ TRUE; -- change in writeProtect/needsLogging status. IF inOutState = in THEN ForkWrite[stateNext: state] -- makes it clean, and sets the flags. END; END ELSE NULL; -- a no-op on pinned and unmapped regions. END; copyIn --[from]-- => --input from the specified window-- { IF ~(state IN Swappable) THEN Bug[copyInButNotSwappable]; IF ~hasSwapUnits THEN {needsLogging _ FALSE; dDirty _ TRUE}; -- (no place to remember whether a swap unit needs logging.) ForkRead[stateNext: inSwappableWarmest]}; -- (additional copyIn logic is in ForkRead.) copyOut --[to]-- => -- output to the specified window. BEGIN IF ~(state IN Swappable) THEN Bug[copyOutButNotSwappable]; IF inOutState = out THEN -- get the swapUnit in.. BEGIN IF ~GetMappingSpaceDesc[].gotIt THEN GO TO Exit; -- better luck next time. IF swapInterval.page >= mappingSpace.interval.page + mappingSpace.countMapped THEN {outcome _ [ok[]]; GO TO Exit}; -- Done: no mapped pages in swap unit. ForkRead[stateNext: inSwappableWarmest]; GO TO Retry; -- better luck later when it's in. END ELSE --inOutState=in-- { IF to.writeProtected THEN Bug[copyOutToProtected]; ForkWrite[stateNext: state]}; -- (additional copyOut logic is in ForkWrite.) END; createSwapUnits => { IF state = outDead THEN state _ outAlive; -- we don't allow swap units to be outDead. hasSwapUnits _ TRUE; dDirty _ TRUE; pageNext _ endRegion}; -- acts on whole region. deactivate => IF state IN InSwappable THEN ForkWrite[stateNext: outAlive]; flush => -- flush all swap units of the region from memory and the region descriptor from the cache. -- the caller must, in ascending order, call flush once successfully for each swap unit of the region! BEGIN IF state = inPinned THEN Bug[flushButPinned]; IF dDirty THEN outcome _ [regionDDirty[]] ELSE --desc is clean, region not pinned-- BEGIN beingFlushed _ TRUE; -- desc will pretend it's missing until it really is. (desc does not become dirty from this statement) IF pageNext < endRegion THEN --the caller will flush more swap units later--{ IF inOutState = in THEN ForkWrite[stateNext: outAlive] ELSE --inOutState=out--NULL} ELSE --this is last swap unit of the region--{ IF inOutState = in THEN ForkWrite[stateNext: missing] ELSE -- inOutState=out --state _ missing}; -- the beingFlushed state will terminate when the desc vanishes (becomes missing). END; END; get --[andResetDDirty, pDescResult]-- => --"get (whole) region descriptor"-- { pageNext _ endRegion; -- acts on whole region. pDescResult^ _ region; IF andResetDDirty THEN dDirty _ FALSE}; kill --[andDeallocate]-- => -- this is a hint. Ignored for unmapped or pinned regions. andDeallocate is not a hint, it is always done. andDeallocate is not used in the current implementation, but may be useful in the future. IF state IN AliveSwappable THEN --there may be something to do-- { IF inOutState = in THEN -- (if it's writeProtected or needsLogging, it must be clean, so we can throw it away.) MStore.Deallocate[interval: swapInterval, promised: FALSE]; state _ IF writeProtected OR needsLogging OR hasSwapUnits THEN outAlive ELSE outDead; dDirty _ TRUE}; makeWritable => { IF ~(state IN Swappable) THEN Bug[makeWritableButNotSwappable]; writeProtected _ FALSE; IF ~hasSwapUnits THEN needsLogging _ FALSE; dDirty _ TRUE; -- change in writeProtected/needsLogging state. [] _ MStore.Relocate[ swapInterval, swapInterval.page, --PageMap.--flagsDirtyReferenced, PageMap.flagsNone]}; map --[level, backFileType, andWriteProtect, andNeedsLogging]-- => BEGIN IF state ~= unmapped THEN Bug[mapButNotUnmapped]; pageNext _ endRegion; -- acts on whole region. writeProtected _ andWriteProtect; needsLogging _ andNeedsLogging; IF writeProtected AND needsLogging THEN Bug[writeProtectedAndNeedsLogging]; levelMapped _ level; dDirty _ TRUE; SELECT backFileType FROM file => state _ outAlive; data => { IF writeProtected OR needsLogging THEN Bug[mapProtectedDataSpace]; state _ IF hasSwapUnits THEN outAlive ELSE outDead}; -- it's not convenient (or very useful) to have "all swap units are outDead". none => { IF hasSwapUnits THEN Bug[swapUnitsOnRealSpace]; -- can't repeat for each swap unit. state _ outDead; ForkRead[stateNext: inPinned]}; -- allocates real memory and pins it; no actual reading since dead. ENDCASE; END; noOp => NULL; pin => IF state = unmapped THEN Bug[pinUnmapped] ELSE IF inOutState = out THEN ForkRead[stateNext: inPinned] ELSE --inOutState=in--state _ inPinned; -- ok to pin a (swap unit of a) pinned region remapA --[firstClean]-- => -- (implicit parameter: pageLocationInSpace.) There will soon be two windows associated with this swap unit. We must keep track of which window the most recent copy of each swap unit is in. BEGIN IF ~(state IN Swappable) THEN Bug[remapButNotSwappable]; IF ~GetMappingSpaceDesc[].gotIt THEN GO TO Exit; -- better luck next time. IF (mappingSpace.interval.count + Environment.bitsPerWord - 1)/Environment.bitsPerWord > LENGTH[pageLocationInSpace] THEN Bug[remapSpaceTooBig]; MarkInWindow[oldWindow, swapInterval.page]; IF inOutState = in AND firstClean THEN ForkWrite[stateNext: state]; END; remapB --[from]-- => -- the new window has arrived. Make sure that the swap unit is in the new window, or is In and dirty. BEGIN IF state = unmapped THEN Bug[remapButUnmapped]; IF ~GetMappingSpaceDesc[].gotIt THEN GO TO Exit; -- better luck next time. IF mappingSpace.writeProtected THEN Bug[remapToReadOnly]; region.writeProtected _ FALSE; region.needsLogging _ FALSE; dDirty _ TRUE; IF InWindow[swapInterval.page] = oldWindow THEN ForkRead[stateNext: inSwappableWarmest]; -- even if it's currently In, to get growth from new window (additional remapB logic in ForkRead). -- MarkInWindow[newWindow, swapInterval.page]; ++ when the region is next written, it will be written to the new window, and marked as such by ForkWrite. END; unmap => BEGIN wasPinned: BOOLEAN = (state = inPinned); dDirty _ TRUE; -- (mapped to unmapped transition) IF inOutState = out THEN state _ unmapped ELSE --inOutState=in--{ IF ~GetMappingSpaceDesc[].gotIt THEN GO TO Exit; -- try again later. IF mappingSpace.dataOrFile = CachedSpace.DataOrFile[data] THEN { MStore.Deallocate[interval: swapInterval, promised: FALSE]; -- no need to swap out a vanishing data space. state _ unmapped} ELSE ForkWrite[stateNext: unmapped]}; IF wasPinned AND outcome = [ok[]] THEN outcome _ [notePinned[levelMax: level]]; END; unpin => { pageNext _ endRegion; -- acts on whole region. IF state = inPinned THEN state _ inSwappableWarmest}; -- ok for swap units. ENDCASE --operation-- => ERROR Bug[funnyAction]; EXITS Exit => NULL; -- outcome has been set already. AddressFault => outcome _ [error[region.state]]; Retry => IF outcome = [ok[]] THEN outcome _ [retry[]]; -- (leave [spaceDmissing[]] alone). END --scope of Exit, etc.--; IF outcome.kind = spaceDMissing THEN pageNext _ region.interval.page + region.interval.count; -- (suggest that caller go on to next region.) IF ~ioStarted THEN { CachedRegionInternal.CheckIn[desc: region]; WITH outcome SELECT FROM ok, notePinned => PageFault.RestartPageFault[region.interval]; error, regionDDirty, regionDMissing, retry, spaceDMissing => NULL; ENDCASE => Bug[funnyOutcome] } ELSE --ioStarted-- { IF operation.afterForking = wait THEN CachedRegionInternal.AwaitNotCheckedOut[pageMember] }; END --DescAvailable, USING region--; ENDCASE --region.state-- => ERROR Bug[funnyState]; END --Apply--; PageTransferProcess: PROCEDURE = -- Completes the I/O started by ForkRead and ForkWrite (q.v.). BEGIN resartOnLeadingPages: BOOLEAN _ TRUE; -- (a variable so we can experiment using CoPilot.) pageRunInterval, bufferInterval: VM.Interval; task: SwapTask.State; DO --FOREVER-- bufferInterval _ FilePageTransfer.Wait[]; task _ SwapTask.Advance[bufferInterval]; pageRunInterval _ VM.Interval[ task.swapInterval.page + (bufferInterval.page - task.bufferPage), bufferInterval.count]; SELECT task.region.state FROM IN In => BEGIN -- If this interval is write protected, it is because it is being written (not being read). If it is being written, we should not apply patches. If it is being read, we should apply patches. IF ~PageMap.GetF[bufferInterval.page].flags.writeProtected THEN ApplyPatches[pageRunInterval, bufferInterval.page]; -- relocate pageRunInterval back to region: [] _ MStore.Relocate[ bufferInterval, pageRunInterval.page, PageMap.flagsNone, task.flags]; IF task.countRemaining ~= 0 AND resartOnLeadingPages THEN PageFault.RestartPageFault[pageRunInterval]; -- restart client for leading pages of swap unit. END; ENDCASE -- unmapped, missing, IN Out -- => MStore.Deallocate[interval: bufferInterval, promised: TRUE]; -- (all pages being written were promised.) IF task.countRemaining = 0 THEN BEGIN SwapBuffer.Deallocate[ VM.Interval[task.bufferPage, task.swapInterval.count]]; -- free any real memory left in the buffer. CachedRegionInternal.CheckIn[desc: task.region]; PageFault.RestartPageFault[task.region.interval]; -- restart this client for last page, and all clients faulting anywhere in the entire region. END; ENDLOOP; END; ApplyPatches: PROCEDURE [interval: VM.Interval, pageBuffer: VM.PageNumber] = INLINE BEGIN OPEN pT: LOOPHOLE[pMapLogDesc, LONG POINTER TO VMMapLog.Descriptor].patchTable; entryPtr: VMMapLog.PatchTableEntryPointer; entrySize: CARDINAL = SIZE[VMMapLog.PatchTableEntry]; firstEntry: VMMapLog.PatchTableEntryPointer = FIRST[ VMMapLog.PatchTableEntryPointer]; FOR entryPtr _ firstEntry, entryPtr + entrySize WHILE entryPtr # pT.limit DO OPEN e: LOOPHOLE[@pT.entries[0], VMMapLog.PatchTableEntryBasePointer][ entryPtr]; IF Utilities.PageFromLongPointer[e.address] IN [interval.page..interval.page + interval.count) THEN BEGIN offset: LONG INTEGER = e.address - Utilities.LongPointerFromPage[interval.page]; (Utilities.LongPointerFromPage[pageBuffer] + offset)^ _ e.value; END; ENDLOOP; END; Initialize[]; END. LOG (For earlier log entries see Pilot 4.0 archive version.) April 24, 1980 11:54 AM Knutsen PageTransferProcess must RestartFaulted on entire region. April 30, 1980 5:24 PM Gobbel Make outputSpecial start a read and return with outcome=retry if region not in. August 5, 1980 3:16 PM Knutsen Implement makeWritable, redo copyIn, copyOut. Implement needsLogging versus writeProtect. inOutState now has only two states. September 4, 1980 10:54 PM Gobbel Fix copyIn bug, add some error checking. September 16, 1980 1:47 PM Knutsen Make CopyIn/Out handle short-mapped windows. Rework ForkRead/Write. ApplyPatches using GetF instruction. Fix another Remap bug. September 19, 1980 6:53 PM McJones AR 5889; ForkWrite[copyOut] must put back real memory if no I/O started. September 24, 1980 1:00 PM McJones Change ForkWrite once again to get mappingSpace descriptor only if region is dirty. September 26, 1980 4:26 PM McJones ForkWrite forgot to relocate memory if spaceDmissing. October 9, 1980 2:58 PM Gobbel Don't turn off needsLogging for region with uniform swap units. December 5, 1980 8:53 AM Knutsen Don't return [retry[]] if [spaceDMissing[]]. If [spaceDMissing[]], proceed to next (whole) region. New age operation. MakeWritable forgot to mark desc dirty. January 21, 1981 2:25 PM Knutsen Set process priority. Transiently change client process's priority as necessary. January 28, 1981 8:56 AM Knutsen Not necessary to transiently change client process's priority: now done by VMMgr. CopyIn must be more careful about checking for needsLogging before complaining. February 4, 1981 9:21 AM Knutsen age[] was fetching space desc earlier than necessary. February 11, 1981 4:15 PM Knutsen FilePageTransfer will now promise pageGroups itself. ForkWrite must not change region.state until all chance of failure is past. August 3, 1982 3:54 pm Levin Correct all occurrences of ~IN. September 15, 1982 8:36 pm Levin PageFault.Restart => PageFault.RestartPageFault.