MBVMemory.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Sandman on 6-Aug-81 15:43:17
Lewis on 17-Sep-81 15:52:42
Levin on January 13, 1984 1:40 pm
Russ Atkinson (RRA) May 13, 1985 11:21:50 pm PDT
DIRECTORY
Basics USING [bitsPerWord, LongDiv, LongMult],
BcdDefs USING [SPHandle],
BootStartList USING [nullSwapUnitIndex],
FS USING [Open, OpenFile],
MB USING [BitArray, BitArrayObject, Error, Handle],
MBVM USING [Base, Code, CodePiece, CodeSeg, DataSeg, DefaultBase, Direction, File, FileBase, FileSeg, First64K, HyperSpace, MaxBase, MDS, nullIndex, Object, Pages, Seg, Segs, SegsSequence],
PrincOps USING [wordsPerPage];
MBVMemory: CEDAR PROGRAM
IMPORTS Basics, FS, MB
EXPORTS MB, MBVM = BEGIN OPEN MBVM;
pageSize: CARDINAL = PrincOps.wordsPerPage;
data: MB.Handle ← NIL;
minimumLength: Base = pageSize*Basics.bitsPerWord;
incrementalLength: CARDINAL = pageSize*Basics.bitsPerWord;
InitVM: PUBLIC PROC [h: MB.Handle] = {
data ← h;
data.lastVMPage ← 0;
segList ← NIL;
};
FinishVM: PUBLIC PROC = {
segList ← NIL;
data ← NIL;
};
WordsForBits: PROC [nBits: CARDINAL] RETURNS [nWords: CARDINAL] = INLINE
{RETURN[(nBits+Basics.bitsPerWord-1)/Basics.bitsPerWord]};
Segment Routines
segList: LIST OF Seg ← NIL;
AllocMDSData: PUBLIC PROC [
base: Base, pages: Pages, dir: Direction ← down] RETURNS [s: DataSeg] = {
SELECT base FROM
MDS, DefaultBase => NULL;
First64K, HyperSpace, Code => ERROR;
ENDCASE => base ← (data.mdsBase + base);
RETURN[AllocData[base: base, pages: pages, dir: dir]]
};
AllocData: PUBLIC PROC [base: Base, pages: Pages, dir: Direction ← down] RETURNS [ds: DataSeg] = {
low, high: Base;
SELECT base FROM
MDS => {low ← data.mdsBase; high ← data.mdsBase+255; base ← DefaultBase};
First64K => {low ← 0; high ← 255; base ← DefaultBase};
HyperSpace => {low ← data.mdsBase+256; high ← MaxBase; base ← DefaultBase};
ENDCASE => {low ← 0; high ← MaxBase};
base ← AllocVM[base: base, pages: pages, dir: dir, high: high, low: low, code: FALSE];
segList ← CONS[
ds ← NEW[data Object ← Object[
base: base, pages: pages, index: BootStartList.nullSwapUnitIndex, body: data[]]],
segList
];
};
AllocCode: PUBLIC PROC [
file: File, base: Base, pages: Pages, fileBase: FileBase, sph: BcdDefs.SPHandle]
RETURNS [cs: CodeSeg] = {
low, high: Base;
SELECT base FROM
Code => {low ← data.codeBase; high ← MaxBase; base ← DefaultBase};
ENDCASE => {low ← 0; high ← MaxBase};
base ← AllocVM[base: base, pages: pages, dir: up, high: high, low: low, code: TRUE];
segList ← CONS[
cs ← NEW[code Object ← Object[
base: base, pages: pages, index: BootStartList.nullSwapUnitIndex, file: file, fileBase: fileBase,
body: code[
sph: sph,
pieces: CONS[
CodePiece[offset: 0, body: code[length: pages*PrincOps.wordsPerPage]],
NIL]
]
]],
segList
];
};
AllocFile: PUBLIC PROC [file: File, base: Base, pages: Pages, fileBase: FileBase]
RETURNS [fs: FileSeg] = {
low, high: Base;
SELECT base FROM
MDS => {low ← data.mdsBase; high ← data.mdsBase+255; base ← DefaultBase};
First64K => {low ← 0; high ← 255; base ← DefaultBase};
HyperSpace => {low ← data.mdsBase+256; high ← MaxBase; base ← DefaultBase};
ENDCASE => {low ← 0; high ← MaxBase};
base ← AllocVM[base: base, pages: pages, dir: up, high: high, low: low, code: FALSE];
segList ← CONS[
fs ← NEW[file Object ← Object[
base: base, pages: pages, index: BootStartList.nullSwapUnitIndex, file: file, fileBase: fileBase,
body: file[bIndex: nullIndex]]],
segList
];
};
BackingForSeg: PUBLIC PROC [seg: Seg] RETURNS [file: FS.OpenFile, fileBase: FileBase] = {
IF seg.objType = $data THEN ERROR;
RETURN[FS.Open[seg.file], seg.fileBase]
};
SortSegs: PUBLIC PROC RETURNS [segs: Segs ← NIL] = {
i, nSegs: NAT;
SiftUp: PROC [low, high: NAT] = {
k, son: NAT;
k ← low;
DO
IF k*2 > high THEN EXIT;
IF k*2+1 > high OR segs[k*2+1-1].base < segs[k*2-1].base THEN son ← k*2
ELSE son ← k*2+1;
IF segs[son-1].base < segs[k-1].base THEN EXIT;
Exchange[son-1, k-1];
k ← son;
ENDLOOP;
};
Exchange: PROC [a, b: NAT] = {
temp: MBVM.Seg ← segs[a];
segs[a] ← segs[b];
segs[b] ← temp;
};
nSegs ← 0;
FOR segL: LIST OF Seg ← segList, segL.rest UNTIL segL = NIL DO nSegs ← nSegs + 1 ENDLOOP;
segs ← NEW[SegsSequence[nSegs]];
i ← 0;
FOR segL: LIST OF Seg ← segList, segL.rest UNTIL segL = NIL DO
segs[i] ← segL.first; i ← i + 1;
ENDLOOP;
FOR i DECREASING IN [1..nSegs/2] DO SiftUp[i, nSegs] ENDLOOP;
FOR i DECREASING IN [1..nSegs) DO Exchange[0, i]; SiftUp[1, i] ENDLOOP;
};
PointerFromSeg: PUBLIC PROC [s: Seg] RETURNS [p: POINTER] = TRUSTED {
IF ~(s.base IN [data.mdsBase..data.mdsBase+255]) THEN ERROR;
RETURN[LOOPHOLE[(s.base-data.mdsBase)*pageSize]]
};
LongPointerFromSeg: PUBLIC PROC [s: Seg] RETURNS [p: LONG POINTER] = TRUSTED {
RETURN[LOOPHOLE[Basics.LongMult[s.base, pageSize]]]};
SegFromPointer: PUBLIC PROC [p: POINTER] RETURNS [s: Seg] = TRUSTED {
base: Base ← LOOPHOLE[p, CARDINAL]/pageSize;
FindSeg: PROC [seg: Seg] RETURNS [BOOL] = TRUSTED {RETURN[seg.base = base]};
RETURN[EnumerateSegs[FindSeg]]
};
SegFromLongPointer: PUBLIC PROC [p: LONG POINTER] RETURNS [s: Seg] = TRUSTED {
base: Base ← Basics.LongDiv[LOOPHOLE[p], pageSize];
FindSeg: PROC [seg: Seg] RETURNS [BOOL] = TRUSTED {RETURN[seg.base = base]};
RETURN[EnumerateSegs[FindSeg]]
};
VM Routines
EnumerateSegs: PROC [proc: PROC [Seg] RETURNS [BOOL]] RETURNS [Seg] = {
FOR segL: LIST OF Seg ← segList, segL.rest UNTIL segL = NIL DO
IF proc[segL.first] THEN RETURN[segL.first];
ENDLOOP;
RETURN[NIL]
};
AllocVM: PROC [base: Base, pages: Pages, dir: Direction, low, high: Base, code: BOOL]
RETURNS [Base] = {
vm: Base;
IF data.vmMap = NIL THEN {
initialLength: CARDINAL = MAX[data.mdsBase, minimumLength];
data.vmMap ← NEW[MB.BitArrayObject[initialLength]];
FOR i: CARDINAL IN [0..initialLength) DO data.vmMap[i] ← FALSE; ENDLOOP;
};
IF base = DefaultBase THEN
allocate 'pages' consecutive pages in virtual pages range [low..high].
DO
incr: INTEGER;
n: CARDINAL ← 0; -- count of contiguous free pages
SELECT dir FROM
up => {incr ← 1; vm ← MIN[low, data.vmMap.length-1]};
ENDCASE => {incr ← -1; vm ← MIN[high, data.vmMap.length-1]};
FOR vm ← vm, vm+incr UNTIL (IF dir = up THEN vm > high ELSE vm < low) DO
IF data.vmMap[vm] OR vm = 0 OR vm = data.mdsBase THEN n ← 0
ELSE IF (n ← n + 1) = pages THEN {
base ← IF dir = up THEN vm - n + 1 ELSE vm;
IF code AND Spans64KBoundary[base, pages] THEN -- try again on next 64K boundary
IF dir = up THEN {n ← 1; vm ← 256*((base+255)/256)}
ELSE {n ← 1; vm ← 256*((base+255)/256)-1}
ELSE {ReserveVM[base, pages]; RETURN[base]};
n ← 0;
};
ENDLOOP;
Can't find sufficient VM in present vmMap. If it hasn't reached its limit,
extend it and try again.
IF ~ExtendVM[] THEN MB.Error["Memory Full"];
ENDLOOP
ELSE {
EnsureAdequateVM[base+pages];
FOR vm IN [base..base+pages) DO
IF data.vmMap[vm] OR vm = 0 OR vm = data.mdsBase THEN EXIT;
REPEAT
FINISHED => {ReserveVM[base, pages]; RETURN[base]};
ENDLOOP;
MB.Error["Memory Busy"];
};
ERROR
};
Spans64KBoundary: PROC [base: Base, pages: Pages] RETURNS [BOOL] = {
RETURN[(base+pages-1)/256 ~= base/256];
};
ReserveVM: PROC [base: Base, pages: Pages] = {
data.lastVMPage ← MAX[base+pages-1, data.lastVMPage];
EnsureAdequateVM[base+pages];
FOR base IN [base..base+pages) DO data.vmMap[base] ← TRUE ENDLOOP;
};
EnsureAdequateVM: PROC [size: CARDINAL] = {
WHILE size > data.vmMap.length DO
IF ~ExtendVM[] THEN ERROR;
ENDLOOP;
};
ExtendVM: PROC RETURNS [worked: BOOL] = {
use LONG arithmetic to avoid overflows
newLength: CARDINAL =
MIN[LONG[data.vmMap.length] + incrementalLength, LONG[MaxBase] + 1];
IF newLength > MaxBase
THEN RETURN [FALSE]
ELSE {
newMap: MB.BitArray = NEW[MB.BitArrayObject[newLength]];
IF data.vmMap.length = newLength THEN RETURN[FALSE];
FOR i: CARDINAL IN [0..data.vmMap.length) DO newMap[i] ← data.vmMap[i]; ENDLOOP;
FOR i: CARDINAL IN [data.vmMap.length..newLength) DO newMap[i] ← FALSE; ENDLOOP;
data.vmMap ← newMap;
RETURN[TRUE];
};
};
The following isn't used any more, but we might need it someday and it will be
easy to get wrong if we recode from scratch!
ReleaseVM: PROC [base: Base, pages: Pages] = {
IF data.lastVMPage = base+pages-1 THEN
FOR lastPage: MBVM.Base DECREASING IN [0..data.lastVMPage) DO
IF data.vmMap[lastPage] THEN {data.lastVMPage ← lastPage; EXIT};
ENDLOOP;
FOR base IN [base..base+pages) DO data.vmMap[base] ← FALSE ENDLOOP
};
END.