MBVMemory.mesa
Last edited by Sandman on 6-Aug-81 15:43:17
Last edited by Lewis on 17-Sep-81 15:52:42
Last edited by Levin on June 20, 1983 2:19 pm
DIRECTORY
BcdDefs USING [SPHandle],
BootStartList USING [nullSwapUnitIndex],
MB USING [BitArray, BitArrayObject, Error, Handle],
MBVM USING [
Base, Code, CodeSeg, DataSeg, DefaultBase, Direction, FileSeg, First64K, HyperSpace, MaxBase, MDS, nullIndex, Object, Pages, Seg, Segs, SegsSequence],
PrincOps USING [bitsPerWord, wordsPerPage],
PrincOpsUtils USING [LongDiv, LongMult, LowHalf],
Segments USING [DeleteSegment, FHandle, LockFromSegment, Unlock];
MBVMemory: PROGRAM
IMPORTS MB, PrincOpsUtils, Segments
EXPORTS MB, MBVM =
BEGIN
OPEN MBVM;
pageSize: CARDINAL = PrincOps.wordsPerPage;
data: MB.Handle ← NIL;
minimumLength: Base = pageSize*PrincOps.bitsPerWord;
incrementalLength: CARDINAL = pageSize*PrincOps.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+PrincOps.bitsPerWord-1)/PrincOps.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: Segments.FHandle, base: Base, pages: Pages, fileBase: CARDINAL, 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,
body: code[sph: sph, file: file, fileBase: fileBase, segment: NIL]]],
segList
];
};
AllocFile: PUBLIC PROC [
file: Segments.FHandle, base: Base, pages: Pages, fileBase: CARDINAL] 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,
body: file[file: file, fileBase: fileBase, segment: NIL, bIndex: nullIndex]]],
segList
];
};
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;
};
ReleaseCodeSegs: PUBLIC PROC = {
FreeOneCodeSegment: PROC [s: Seg] RETURNS [stop: BOOL] = {
WITH s SELECT FROM
code =>
IF segment ~= NIL THEN {
IF Segments.LockFromSegment[segment] ~= 0 THEN Segments.Unlock[segment];
Segments.DeleteSegment[segment];
segment ← NIL;
};
ENDCASE;
RETURN[FALSE]
};
[] ← EnumerateSegs[FreeOneCodeSegment]
};
PointerFromSeg: PUBLIC PROC [s: Seg] RETURNS [p: POINTER] = {
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] = {
RETURN[LOOPHOLE[PrincOpsUtils.LongMult[s.base, pageSize]]]};
SegFromPointer: PUBLIC PROC [p: POINTER] RETURNS [s: Seg] = {
base: Base ← LOOPHOLE[p, CARDINAL]/pageSize;
FindSeg: PROC [seg: Seg] RETURNS [BOOL] = {RETURN[seg.base = base]};
RETURN[EnumerateSegs[FindSeg]]
};
SegFromLongPointer: PUBLIC PROC [p: LONG POINTER] RETURNS [s: Seg] = {
base: Base ← PrincOpsUtils.LongDiv[LOOPHOLE[p], pageSize];
FindSeg: PROC [seg: Seg] RETURNS [BOOL] = {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 =
PrincOpsUtils.LowHalf[MIN[LONG[data.vmMap.length] + incrementalLength, LONG[MaxBase] + 1]];
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 data.vmMap[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.