MBMain.mesa
Copyright Ó 1985, 1986 by Xerox Corporation. All rights reserved.
Sandman on 6-Aug-81 15:41:24
Lewis on 17-Sep-81 13:31:13
Levin on January 12, 1984 4:26 pm
Russ Atkinson (RRA) March 8, 1985 5:24:23 pm PST
Doug Wyatt, December 12, 1986 6:39:56 pm PST
DIRECTORY
Basics USING [BYTE],
BcdDefs USING [MTHandle],
BootStartList USING [StateVectorCounts],
IO USING [card, PutF, rope, STREAM],
MB USING [Alloc, AllocFault, BHandle, EnumerateNoTrapModules, Handle, WartFrame],
MBVM USING [AllocData, AllocMDSData, Base, CopyRead, CopyWrite, DataSeg, LongPointerFromSeg, LongWrite, MDS, PointerFromSeg, Read, Write],
PrincOps USING [AllocationVectorSize, AV, ControlLink, Frame, FrameCodeBase, FrameSizeIndex, FrameVec, GFT, GFTIndex, GFTItem, GlobalFrame, GlobalFrameHandle, LargeReturnSlot, MainBodyIndex, PDABase, Priority, ProcessDataArea, ProcessStateBlock, SD, sGFTLength, SpecialReturnSlot, wordsPerPage],
PrincOpsUtils USING [MakeFsi, PagesForWords, WordsForPages];
MBMain:
CEDAR
PROGRAM
IMPORTS IO, MB, MBVM, PrincOpsUtils
EXPORTS MB = BEGIN OPEN PrincOps;
BYTE: TYPE = Basics.BYTE;
AVPage: CARDINAL = LOOPHOLE[AV, CARDINAL]/wordsPerPage;
GFTPage: CARDINAL = LOOPHOLE[GFT, CARDINAL]/wordsPerPage;
data: MB.Handle ← NIL;
values: REF Values ← NIL;
Values:
TYPE =
RECORD [
frameWeights: PACKED ARRAY FrameSizeIndex OF BYTE ← ALL[LAST[BYTE]],
fsiChain: PACKED ARRAY FrameSizeIndex OF BYTE ← ALL[LAST[BYTE]]];
DefaultValues: Values = [
frameWeights: [9,13,9,8,7,6,4,2,2,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0],
fsiChain: [1,2,3,4,5,6,7,8,9,10,11,0,13,14,15,16,17,18,0,0,0,0,0,0,0,0,0,0,0,0]];
heapFrames, extraFrames: FrameCounts ← NIL;
FrameCounts: TYPE = REF FrameCountTable;
FrameCountTable: TYPE = ARRAY FrameSizeIndex OF CARDINAL;
InitMain:
PUBLIC
PROC [h:
MB.Handle] = {
data ← h;
values ← NEW[Values ← []];
heapFrames ← NEW[FrameCountTable ← ALL[0]];
extraFrames ← NEW[FrameCountTable ← ALL[0]];
FOR i: Priority
IN Priority
DO
h.stateVectorCounts[i] ← LAST[CARDINAL];
ENDLOOP;
h.nProcesses ← LAST[CARDINAL];
h.framePages ← LAST[CARDINAL];
h.pdaPages ← LAST[CARDINAL];
h.svSize ← LAST[CARDINAL];
h.gftLength ← LAST[CARDINAL];
h.mdsBase ← LAST[CARDINAL];
h.codeBase ← LAST[CARDINAL];
};
FinishMain:
PUBLIC
PROC = {
values ← NIL;
heapFrames ← NIL;
extraFrames ← NIL;
data ← NIL;
};
Memory initialization
InitMemory:
PUBLIC
PROC = {
AssignDefaults[];
IF ~data.germ THEN {ReserveSelectedPages[]; InitPDA[]};
InitializeMDS[];
AllocateLocalFrames[];
};
AssignDefaults:
PROC = {
i: CARDINAL;
FOR i
IN Priority
DO
IF data.stateVectorCounts[i] =
LAST[
CARDINAL]
THEN
data.stateVectorCounts[i] ← simpleDefaults.stateVectorCounts[i];
ENDLOOP;
FOR i
IN FrameSizeIndex
DO
IF values.frameWeights[i] =
LAST[
BYTE]
THEN
values.frameWeights[i] ← DefaultValues.frameWeights[i];
IF values.fsiChain[i] =
LAST[
BYTE]
THEN
values.fsiChain[i] ← DefaultValues.fsiChain[i];
ENDLOOP;
IF data.gftLength =
LAST[
CARDINAL]
THEN
data.gftLength ← simpleDefaults.gftLength;
IF data.mdsBase =
LAST[
CARDINAL]
THEN
data.mdsBase ← simpleDefaults.mdsBase;
IF data.codeBase =
LAST[
CARDINAL]
THEN
data.codeBase ← simpleDefaults.codeBase;
IF data.pdaPages =
LAST[
CARDINAL]
THEN
data.pdaPages ← simpleDefaults.pdaPages;
IF data.nProcesses =
LAST[
CARDINAL]
THEN
data.nProcesses ← simpleDefaults.nProcesses;
IF data.framePages =
LAST[
CARDINAL]
THEN
data.framePages ← simpleDefaults.framePages;
ReserveSelectedPages:
PROC = {
seg: MBVM.DataSeg;
seg ← MBVM.AllocData[base: 1, pages: 1];
SetReservedSegBits[seg];
seg ← MBVM.AllocData[base: 376B, pages: 1];
SetReservedSegBits[seg];
seg ← MBVM.AllocData[base: 377B, pages: 1];
SetReservedSegBits[seg];
};
SetReservedSegBits:
PROC [s:
MBVM.DataSeg] = {
s.info ← [FALSE, resident];
s.bootLoaded ← TRUE;
};
InitPDA:
PROC = {
seg: MBVM.DataSeg;
pda: PDABase;
i: CARDINAL;
words: CARDINAL ← 0;
FOR i
IN Priority
DO
words ← words + data.stateVectorCounts[i]*data.svSize;
ENDLOOP;
data.pdaPages ←
MAX[
PrincOpsUtils.PagesForWords[
data.nProcesses*(SIZE[ProcessStateBlock]+1) + words + SIZE[ProcessDataArea]],
data.pdaPages
];
seg ← MBVM.AllocData[base: 256, pages: data.pdaPages, dir: up];
SetReservedSegBits[seg];
TRUSTED {
pda ← MBVM.LongPointerFromSeg[seg];
FOR i
IN [0..data.pdaPages*wordsPerPage)
DO
MBVM.LongWrite[pda+i, 0];
ENDLOOP;
};
InitializeMDS:
PROC =
TRUSTED {
gftPages: CARDINAL;
seg: MBVM.DataSeg;
p: POINTER;
av and sd
p ← AV;
SetReservedSegBits[seg ← MBVM.AllocMDSData[base: AVPage, pages: 1]];
FOR i: CARDINAL IN [0..wordsPerPage) DO MBVM.Write[p+i, 0] ENDLOOP;
InitAV[p];
gft
gftPages ← PrincOpsUtils.PagesForWords[data.gftLength*SIZE[GFTItem]];
SetReservedSegBits[seg ← MBVM.AllocMDSData[base: GFTPage, pages: gftPages]];
p ← GFT;
FOR i:
CARDINAL
IN [0..gftPages*
SIZE[GFTItem])
DO
MBVM.Write[p+i, 0];
ENDLOOP;
MBVM.Write[@SD[sGFTLength], data.gftLength];
};
InitAV:
PROC [av:
POINTER] =
TRUSTED {
FOR i: FrameSizeIndex
IN FrameSizeIndex
DO
IF values.fsiChain[i] <= i THEN MBVM.Write[av+i, 1]
ELSE MBVM.Write[av+i, 4*values.fsiChain[i]+2];
ENDLOOP;
MBVM.Write[av+LargeReturnSlot, 1];
MBVM.Write[av+SpecialReturnSlot, 1];
};
TurnOffStartTrap:
PUBLIC
PROC = {
DoIt:
PROC [bh:
MB.BHandle, mth: BcdDefs.MTHandle]
RETURNS [
BOOL] =
TRUSTED {
f: GlobalFrameHandle = bh.mt[mth.gfi].frame;
fcb: FrameCodeBase;
MBVM.CopyRead[from: @f.code, to: @fcb, nwords: SIZE[FrameCodeBase]];
fcb.out ← FALSE;
MBVM.CopyWrite[from: @fcb, to: @f.code, nwords: SIZE[FrameCodeBase]];
RETURN[FALSE]
};
MB.EnumerateNoTrapModules[DoIt];
};
StartControlLink:
PUBLIC
PROC
RETURNS [proc: ControlLink] =
TRUSTED {
g: GlobalFrameHandle = MB.WartFrame[];
gfWords: CARDINAL ~ SIZE[PrincOps.GlobalFrame[0]];
gfSpace: ARRAY [0..gfWords) OF WORD;
gf: GlobalFrameHandle ~ LOOPHOLE[@gfSpace];
Note that the following manipulates only the overhead words.
MBVM.CopyRead[from: g, to: gf, nwords: gfWords];
proc ← [procedure[gfi: gf.gfi, ep: MainBodyIndex, tag: TRUE]];
gf.started ← TRUE;
MBVM.CopyWrite[from: gf, to: g, nwords: gfWords];
};
Frame Allocation
SimpleValues:
TYPE =
RECORD [
mdsBase, codeBase: MBVM.Base,
nProcesses: CARDINAL,
framePages: CARDINAL,
pdaPages: CARDINAL,
gftLength: CARDINAL,
svSize: CARDINAL,
stateVectorCounts: BootStartList.StateVectorCounts
];
simpleDefaults: SimpleValues = [
mdsBase: 512,
codeBase: 768,
nProcesses: 50,
framePages: 10,
pdaPages: 1,
gftLength: 512,
svSize: 20B,
stateVectorCounts: [1,1,3,1,1,3,1,1]
];
GetFrameWeight:
PUBLIC
PROC [index: FrameSizeIndex]
RETURNS [weight:
CARDINAL] = {
RETURN[values.frameWeights[index]]};
SetFrameWeight:
PUBLIC
PROC [index: FrameSizeIndex, weight:
CARDINAL] = {
values.frameWeights[index] ← weight};
GetFsiChain:
PUBLIC
PROC [index: FrameSizeIndex]
RETURNS [fsiNext: FrameSizeIndex] = {
RETURN[values.fsiChain[index]]};
SetFsiChain:
PUBLIC
PROC [index: FrameSizeIndex, fsiNext: FrameSizeIndex] = {
values.fsiChain[index] ← fsiNext};
AllocateFrames:
PUBLIC
PROC [size:
CARDINAL, single, resident:
BOOL]
RETURNS [frames: POINTER, inFrameHeap: BOOL] = TRUSTED {
pages: CARDINAL;
seg: MBVM.DataSeg;
IF single
THEN
RETURN[MB.Alloc[PrincOpsUtils.MakeFsi[size] ! MB.AllocFault => CONTINUE], TRUE];
pages ← PrincOpsUtils.PagesForWords[size];
seg ← MBVM.AllocData[base: MBVM.MDS, pages: pages, dir: up];
frames ← MBVM.PointerFromSeg[seg];
seg.info.readOnly ← FALSE;
IF resident
THEN {
seg.bootLoaded ← TRUE;
seg.info.state ← resident;
Someday, we may wish to do the following:
[] ← DivideAllocationArea[frames+size, pages*wordsPerPage - size, extraFrames];
};
RETURN[frames, FALSE]
};
The following declarations are shared with VMInternal and VMSideDoor. When VM stabilizes, they should be referenced from there.
VMInternal:
AnyFrameSizeIndex:
TYPE =
CARDINAL [0..PrincOps.AllocationVectorSize);
note that an AnyFrameSizeIndex immediately precedes a Frame.
FsiFrame:
TYPE =
MACHINE
DEPENDENT
RECORD [
fsi (0): AnyFrameSizeIndex
];
FrameHeapPiece: TYPE = POINTER TO FrameHeapPieceHeader;
FrameHeapPieceHeader:
TYPE =
MACHINE
DEPENDENT
RECORD [
next(0): FrameHeapPiece, -- must be at 0 MOD 4 boundary.
wordsAllocated(1): CARDINAL, -- actually [0..VM.PagesToWords[PrincOps.shortPointerSpan]]
wordsInUse(2): CARDINAL, -- assert: wordsInUse MOD 4 = 3
frameFsi(3): AnyFrameSizeIndex
must be at 3 MOD 4 boundary
];
VMSideDoor:
MarkerType: TYPE = MACHINE DEPENDENT {frame(0), deadSpace(1)};
FrameMarker:
TYPE =
MACHINE
DEPENDENT
RECORD [
marker(0):
SELECT markerType(0:0..0): MarkerType
FROM
frame => [fsi(0:1..15): PrincOps.FrameSizeIndex],
deadSpace => [count(0:1..15): NAT], -- count does NOT include FrameMarker
ENDCASE
];
AllocateLocalFrames:
PROC = {
pieceHeader: --VMInternal.--FrameHeapPieceHeader ← NULL;
pieceInVM: --VMInternal.--FrameHeapPiece;
piecePages: CARDINAL;
localHeapSize: CARDINAL ← 0;
seg: MBVM.DataSeg;
FOR i:
CARDINAL
IN FrameSizeIndex
DO
localHeapSize ← localHeapSize + values.frameWeights[i]*(FrameVec[i]+1);
ENDLOOP;
piecePages ← MAX[PrincOpsUtils.PagesForWords[localHeapSize], data.framePages];
pieceHeader.next ← NIL;
pieceHeader.wordsAllocated ← PrincOpsUtils.WordsForPages[piecePages];
seg ← MBVM.AllocData[base: MBVM.MDS, pages: piecePages, dir: up];
seg.bootLoaded ← TRUE;
seg.info ← [FALSE, resident];
TRUSTED {
pieceInVM ← MBVM.PointerFromSeg[seg];
pieceHeader.wordsInUse ←
DivideAllocationArea[pieceInVM, pieceHeader.wordsAllocated, heapFrames];
MBVM.CopyWrite[from: @pieceHeader, to: pieceInVM, nwords: SIZE[FrameHeapPieceHeader]];
};
};
DivideAllocationArea:
PROC [base:
POINTER, size:
CARDINAL, counts: FrameCounts]
RETURNS [wordsUsed: CARDINAL ← 0] = {
p: POINTER ← base;
origin: POINTER;
sum: CARDINAL ← 0;
ct: CARDINAL;
fw: ARRAY FrameSizeIndex OF CARDINAL;
AdjustSize:
PROC [words:
CARDINAL, markDead:
BOOL ←
TRUE] = {
IF markDead THEN MBVM.Write[p, --VMSideDoor.--FrameMarker[deadSpace[words-1]]];
TRUSTED {p ← p + words};
size ← size - words;
};
EnsureQuadWordAlignment:
PROC [markDead:
BOOL] = {
pm4: CARDINAL = LOOPHOLE[p, CARDINAL] MOD 4;
IF pm4 ~= 0 THEN AdjustSize[4 - pm4, markDead];
};
Ensure3Mod4Alignment:
PROC [markDead:
BOOL] = {
pm4: CARDINAL = LOOPHOLE[p, CARDINAL] MOD 4;
IF pm4 ~= 3 THEN AdjustSize[3 - pm4, markDead];
};
IF size < 4 THEN RETURN;
EnsureQuadWordAlignment[markDead: FALSE];
IF size < 4 THEN RETURN;
origin ← p;
Ensure3Mod4Alignment[markDead: FALSE]; -- allow space for FramePieceHeader
FOR i: FrameSizeIndex
IN [0..fw.
LENGTH)
DO
sum ← sum + FrameVec[i]*(fw[i] ← values.frameWeights[i]);
ENDLOOP;
ct ← MAX[size/sum, 1];
WHILE size > FrameVec[0]
DO
FOR fsi: FrameSizeIndex
IN [0..FrameVec.
LENGTH)
DO
frSize: CARDINAL = FrameVec[fsi] + SIZE[FrameMarker];
THROUGH [1..fw[fsi]*ct]
UNTIL size < frSize
DO
AddFrameToAV:
PROC =
TRUSTED {
OPEN VMSideDoor;
MBVM.Write[p, FrameMarker[frame[fsi]]];
MBVM.Write[p + SIZE[FrameMarker], MBVM.Read[@AV[fsi]]];
MBVM.Write[@AV[fsi], p + SIZE[FrameMarker]];
};
EnsureLegalForDandelion:
PROC = {
Make sure that the fsi word, overhead, and local 0 are all in the same page.
OPEN PrincOps;
offsetInPage: CARDINAL = LOOPHOLE[p, CARDINAL] MOD wordsPerPage;
IF offsetInPage = wordsPerPage-SIZE[FrameMarker] THEN AdjustSize[4]
ELSE IF offsetInPage = wordsPerPage-SIZE[FrameMarker]-SIZE[local Frame] THEN AdjustSize[8];
};
Ensure3Mod4Alignment[markDead: TRUE];
IF size < frSize THEN EXIT;
EnsureLegalForDandelion[];
IF size < frSize THEN EXIT;
Assert: 'p' MOD 4 = 3 and 'frSize' words are available, beginning at 'p'.
AddFrameToAV[];
counts[fsi] ← counts[fsi] + 1;
TRUSTED {p ← p + frSize};
size ← size - frSize;
ENDLOOP;
ENDLOOP;
FOR i: FrameSizeIndex IN [0..fw.LENGTH-1) DO fw[i] ← MAX[fw[i]/3, 1]; ENDLOOP;
ct ← 1;
ENDLOOP;
TRUSTED {RETURN [p - origin]}
ReportFrameAllocation:
PUBLIC
PROC = {
loadmap: IO.STREAM = data.loadmap;
serendipity: BOOL ← FALSE;
FOR i: FrameSizeIndex
IN FrameSizeIndex
DO
IF extraFrames[i] ~= 0 THEN {serendipity ← TRUE; EXIT};
ENDLOOP;
loadmap.PutF[
"\NLOCAL FRAMES ALLOCATED%g:\N\N",
IO.rope[IF serendipity THEN " (total=(heap+serendipity))" ELSE NIL]];
FOR i: FrameSizeIndex
IN FrameSizeIndex
DO
IF extraFrames[i] = 0 THEN loadmap.PutF["%4d: %d\N", IO.card[i], IO.card[heapFrames[i]]]
ELSE
loadmap.PutF["%4d: %d (=%d+%d)\N",
IO.card[i], IO.card[heapFrames[i]+extraFrames[i]],
IO.card[heapFrames[i]], IO.card[extraFrames[i]]
];
ENDLOOP;
END.