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