DIRECTORY
BootFileChanges USING [IsVacant, PageStateFromFlags],
BootStartList
USING [
EntryPointer, Enumerate, h, IndexToEntryPointer, IndexToSpaceEntryPointer, Proc, SpaceEntryPointer],
GermSwap USING [mdsiGerm],
PrincOps USING [flagsVacant, PDA, shortPointerSpan],
PrincOpsUtils USING [VERSION],
ProcessorFace USING [GetNextAvailableVM],
ProcessorFaceExtras USING [firstSpecialRealPage, specialRealPages],
VM
USING [
AddressForPageNumber, MakeReadOnly, PageNumberForAddress, Pin, PagesForWords],
VMInternal
USING [
AddToFreeList, AllocCount, allocCounts, Crash, DataState, freePages, GetVMMap, InOut, Interval, lastRealPage, PageCount, PageNumber, partitions, RealPageNumber, rmMap, RMMapEntry, SetVMMap, VMMapEntry, VMPartition],
VMSideDoor USING [];
InitializeTables:
PUBLIC
PROC = {
rmTable: Interval;
AllocateRMMap:
PROC
RETURNS [rmTable: Interval] = {
AssignVMForRMTable:
PROC
RETURNS [Interval] = {
pagesForRMMap: PageCount =
VM.PagesForWords[(lastRealPage.LONG+1)*SIZE[RMMapEntry]];
page: PageNumber ← BootStartList.h.lastVMPage + 1;
DO
count: PageCount;
[firstPage: page, count: count] ← ProcessorFace.GetNextAvailableVM[page];
SELECT count
FROM
0 => Crash[];
< pagesForRMMap => page ← page + count;
ENDCASE => EXIT;
ENDLOOP;
RETURN[[page, pagesForRMMap]]
};
AssignRealMemoryToInterval:
PROC [interval: Interval] = {
endInterval: PageNumber = interval.page + interval.count - 1;
nextUnmapped: PageNumber ← AdvanceToNextUnmapped[interval.page];
AdvanceToNextUnmapped:
PROC [vmPage: PageNumber]
RETURNS [PageNumber] = {
UNTIL BootFileChanges.IsVacant[vmPage] DO vmPage ← vmPage.SUCC; ENDLOOP;
RETURN[vmPage]
};
RealMemoryStealable:
PROC [vmPage: PageNumber]
RETURNS [
BOOL] = {
IF BootFileChanges.IsVacant[vmPage] THEN RETURN [FALSE];
RETURN[ProcessorFace.GetNextAvailableVM[vmPage].firstPage = vmPage]
};
SwapVMEntries:
PROC [vm1, vm2: PageNumber] = {
vmE1: VMMapEntry = GetVMMap[vm1];
vmE2: VMMapEntry = GetVMMap[vm2];
SetVMMap[vm1, vmE2];
SetVMMap[vm2, vmE1];
};
FindRealMemoryForInterval: BootStartList.Proc = {
WITH e: BootStartList.IndexToEntryPointer[index]
SELECT
FROM
space => {
IF ~e.bootLoaded
THEN
FOR vmPage: PageNumber
IN [e.vmPage..e.vmPage+e.pages)
DO
It is assumed that "interval" does not overlap the virtual memory spanned by the start list. If it does, add the following statement:
IF vmPage IN [interval.page..interval.page+interval.count) THEN LOOP;
IF RealMemoryStealable[vmPage]
THEN
SwapVMEntries[vmPage, nextUnmapped];
IF (nextUnmapped ← AdvanceToNextUnmapped[nextUnmapped]) > endInterval
THEN
RETURN[TRUE];
ENDLOOP;
};
swapUnit => NULL;
ENDCASE => Crash[];
};
IF nextUnmapped <= endInterval
THEN
BootStartList.Enumerate[FindRealMemoryForInterval];
FOR vmPage: PageNumber
IN [BootStartList.h.lastBootLoadedPage+1..vmPages)
DO
IF vmPage IN [interval.page..interval.page+interval.count) THEN LOOP;
IF RealMemoryStealable[vmPage]
THEN {
SwapVMEntries[vmPage, nextUnmapped];
IF (nextUnmapped ← AdvanceToNextUnmapped[nextUnmapped]) > endInterval
THEN
EXIT;
};
ENDLOOP;
};
We now know how much virtual (and real) memory will be needed to hold the rmMap. We allocate virtual memory following the end of the memory claimed by the boot file, then put real memory behind it.
AssignRealMemoryToInterval[rmTable ← AssignVMForRMTable[]];
};
PartitionForPage:
PROC [page: PageNumber]
RETURNS [partition: VMPartition] = {
FOR partition
IN VMPartition
DO
interval: Interval = partitions[partition];
IF page IN [interval.page..interval.page+interval.count) THEN EXIT;
ENDLOOP;
};
ProcessSpaces: BootStartList.Proc = {
OPEN BootStartList;
entry: EntryPointer = IndexToEntryPointer[index];
WITH e: entry
SELECT
FROM
space => {
The following is adequate because MakeBoot won't build a space that crosses a partition boundary.
--*stats*-- partition: VMPartition = PartitionForPage[e.vmPage];
IF e.bootLoaded
THEN {
This "space" requires real memory.
FOR vmPage: PageNumber
IN [e.vmPage
..e.vmPage+e.pages)
DO
vmEntry: VMMapEntry ← GetVMMap[vmPage];
WITH vmE: vmEntry
SELECT InOut[vmEntry]
FROM
in => {
Note that the following marks bootloaded pages as dirty, so that when (if) backing storage becomes available, they will eventually be written out.
rmMap[vmE.real] ← [
dataState: unchanged, needsBackingStoreWrite: TRUE,
body: reclaimable[virtual: vmPage]
];
Make sure that the pages are "old" to help the laundry process.
vmE.state.flags.referenced ← FALSE;
Clear the write-protect bit in the VMMapEntry. This enables us to use VM.MakeReadOnly in the ProcessSwapUnits pass instead of writing special-case code.
vmE.state.flags.readonly ← FALSE;
SetVMMap[vmPage, vmE];
};
out => Crash[];
ENDCASE;
ENDLOOP;
--*stats*--
allocCounts[partition].pagesAllocated ←
allocCounts[partition].pagesAllocated + e.pages;
}
ELSE {
This "space" doesn't need any real memory. We put any real memory it might have onto the free list, and, in any event, initialize its VMMap entry.
EnsureUnmapped[
[e.vmPage, e.pages], IF e.type.class = empty THEN none ELSE undefined];
--*stats*--
IF e.type.class ~= empty
THEN
allocCounts[partition].pagesAllocated ←
allocCounts[partition].pagesAllocated + e.pages;
};
};
swapUnit => NULL; -- Pinning, where necessary, will be done later.
ENDCASE => Crash[];
};
ProcessSwapUnits: BootStartList.Proc = {
OPEN BootStartList;
entry: EntryPointer = IndexToEntryPointer[index];
WITH e: entry
SELECT
FROM
space => NULL;
swapUnit => {
parent: SpaceEntryPointer = IndexToSpaceEntryPointer[e.parent];
IF parent.bootLoaded
THEN {
We don't need the full generality of the VM operations, and the ProcessSpaces pass has set up the VMMap and RMMap well enough to allow us to call the public interface.
interval: Interval = [parent.vmPage+e.base, e.pages];
IF e.info.state = resident
THEN {
VM.Pin[interval]};
IF e.info.readOnly
THEN {
VM.MakeReadOnly[interval]};
};
};
ENDCASE => {Crash[]};
};
ReserveSpecialVM:
PROC [interval: Interval] = {
Arranges that the pages in "interval", as well as any real memory they may have, will never be allocated.
FOR vmPage: PageNumber
IN [interval.page..interval.page+interval.count)
DO
--*stats*-- partition: VMPartition = PartitionForPage[vmPage];
vmEntry: VMMapEntry ← GetVMMap[vmPage];
WITH vmE: vmEntry
SELECT InOut[vmEntry]
FROM
in =>
The following test on vmE.real is necessary because lastRealPage is computed ignoring any real memory belonging to unavailable VM. However, this procedure is invoked to place such VM (and its associated real memory) off-limits to the allocators, and such real memory might be above lastRealPage.
IF vmE.real <= lastRealPage
THEN
rmMap[vmE.real] ← [
dataState: changed, needsBackingStoreWrite: TRUE,
body: pinned[pinReason: permanentlyPinned, pinCount: 1]
];
out => {
vmE.dataState ← none;
vmE.checkedOut ← TRUE;
SetVMMap[vmPage, vmEntry];
};
ENDCASE;
--*stats*--
allocCounts[partition].pagesAllocated ← allocCounts[partition].pagesAllocated.SUCC;
ENDLOOP;
};
EnsureUnmapped:
PROC [interval: Interval, dataState: DataState] = {
AlreadyAllocated:
PROC [real: RealPageNumber]
RETURNS [inUse:
BOOL] =
INLINE {
WITH rmE: rmMap[real]
SELECT
FROM
free => Crash[];
reclaimable => RETURN[TRUE];
pinned => RETURN[rmE.pinReason ~= noSuchRealPage];
ENDCASE;
};
FOR vmPage: PageNumber
IN [interval.page..interval.page+interval.count)
DO
vmEntry: VMMapEntry ← GetVMMap[vmPage];
WITH vmE: vmEntry
SELECT InOut[vmEntry]
FROM
in => IF AlreadyAllocated[vmE.real] THEN LOOP ELSE AddToFreeList[vmE.real];
out => NULL;
ENDCASE;
SetVMMap[vmPage,
[state: BootFileChanges.PageStateFromFlags[PrincOps.flagsVacant],
body: out[checkedOut: FALSE, readOnly: FALSE, dataState: dataState]]];
ENDLOOP;
};
ReserveUnavailableVM:
PROC [] =
-- INLINE -- {
vmPage: PageNumber ← ProcessorFace.GetNextAvailableVM[0].firstPage;
ReserveSpecialVM[[0, vmPage]];
DO
Assert: vmPage is available, in the sense of ProcessorFace.GetNextAvailableVM.
nextAvailable: PageNumber;
count: PageCount ← ProcessorFace.GetNextAvailableVM[vmPage].count;
[nextAvailable, count] ← ProcessorFace.GetNextAvailableVM[vmPage + count];
IF count = 0 THEN EXIT;
ReserveSpecialVM[[vmPage + count, nextAvailable - (vmPage + count)]];
vmPage ← nextAvailable;
ENDLOOP;
};
The memory state at this point is as follows: The microcode has placed all of the real memory in the virtual memory map and has loaded the Germ into its predefined area of virtual memory (moving real memory under virtual memory in this interval, as necessary). The Germ has subsequently allocated some additional virtual and real memory for i/o buffers and the like, and has loaded the boot file in which we are executing. In the course of loading, real memory has been moved under the bootloaded virtual memory pages.
firstSpecialReal: RealPageNumber = ProcessorFaceExtras.firstSpecialRealPage;
countSpecialReal: PageCount = ProcessorFaceExtras.specialRealPages;
lastRealPage ← RealPageNumber.FIRST;
rmPages ← 0;
vmPages ← 0;
DO
page: PageNumber;
count: PageCount;
[firstPage: page, count: count] ← ProcessorFace.GetNextAvailableVM[vmPages];
IF count = 0 THEN EXIT;
vmPages ← page + count;
lastVMPage ← vmPages.PRED;
THROUGH [0..count)
DO
vmEntry: VMMapEntry = GetVMMap[page];
WITH vmE: vmEntry
SELECT InOut[vmE]
FROM
in => {lastRealPage ← MAX[lastRealPage, vmE.real]; rmPages ← rmPages.SUCC};
out => NULL;
ENDCASE;
page ← page.SUCC;
ENDLOOP;
ENDLOOP;
IF countSpecialReal > 0
THEN
lastRealPage ← MAX[lastRealPage, RealPageNumber[firstSpecialReal+countSpecialReal-1]];
InitializePartitions[];
rmTable ← AllocateRMMap[];
rmMap ← VM.AddressForPageNumber[rmTable.page];
FOR realPage: RealPageNumber
IN [RealPageNumber.
FIRST..lastRealPage]
DO
rmMap[realPage].body ← pinned[pinReason: noSuchRealPage, pinCount: 1];
ENDLOOP;
IF countSpecialReal > 0
THEN
FOR realPage: RealPageNumber
IN [firstSpecialReal..RealPageNumber[firstSpecialReal+countSpecialReal-1]]
DO
rmMap[realPage].body ← pinned[pinReason: specialRealPageAvailable, pinCount: 0];
ENDLOOP;
BootStartList.Enumerate[ProcessSpaces];
BootStartList.Enumerate[ProcessSwapUnits];
The VMMap and RMMap entries for all bootloaded pages are now consistent with each other and with the start list. In addition, the real memory for all non-bootloaded pages within the virtual memory interval spanned by the boot file has been placed on the free list and all VMMap entries for non-bootloaded boot file pages now have dataState = undefined.
We now deal with a few special cases. (Shouldn't we do something about the dedicated real memory (i.e., the Dandelion's display memory)?)
ReserveSpecialVM[rmTable];
ReserveSpecialVM[
[GermSwap.mdsiGerm*PrincOps.shortPointerSpan, PrincOps.shortPointerSpan]];
ReserveSpecialVM[[VM.PageNumberForAddress[LONG[NIL]], 1]];
ReserveSpecialVM[[VM.PageNumberForAddress[LONG[LOOPHOLE[1, POINTER]]], 1]];
ReserveUnavailableVM[];
Finally, we initialize all VMMap entries describing the virtual memory not spanned by the boot file or handled explicitly above, placing any real memory they may have on the free list.
EnsureUnmapped[
[BootStartList.h.lastVMPage+1, vmPages - (BootStartList.h.lastVMPage+1)], none];
We now limit the virtual address space to the size of usable real memory (more or less). The argument for the following calculation is somewhat subtle. (rmTable.page + rmTable.count - 1) is the last page of VM allocated on behalf of this boot file. However, some of the allocated VM doesn't have associated real memory, most notably the "spaces" in the BootStartList that are not bootloaded. Their VM will not be populated with real memory until a VM backing file is available, since their contents can only be obtained from secondary storage. So, we can safely raise the VM limit to 'freePages' beyond the last allocated page, on the grounds that, until a VM backing file is located, real memory will be consumed only to populate newly-allocated virtual memory. However, there are two other factors to consider. First, the unmapped portions of lowCore, pda, and mds have been included in the VM limit, and, in principle, additional pages of these regions could be allocated and populated with real memory. Thus, the limit may be too generous. Second, the simple calculation of the limit assumes that no unavailable VM (in the sense of ProcessorFace.GetNextAvailableVM) is spanned. Thus, the limit might be too conservative. We could correct precisely for the second factor, but not the first. However, the only consequence of the limit being too generous is that we may run out of real memory before we run out of virtual memory. If this actually happens, the system will die, but some fundamental fix to the higher-level logic will be required anyway, since there is simply not enough real memory for the system to execute.
vmPages ←
MIN[(rmTable.page + rmTable.count - 1) + freePages, 16000];
RRA sez that this estimate is only OK for small memories. When the physical memory gets really huge, then this number may well become larger than the backing file is prepared to handle. This estimate need only be large enough to take us through to when we attach the backing file.
partitions[normalVM].count ← vmPages - partitions[normalVM].page;
};