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 April 5, 1983 3:56 pm
DIRECTORY
Environment USING [bitsPerWord, wordsPerPage],
BcdOps USING [SPHandle],
Heap USING [Create, Delete],
Inline USING [LongCOPY, LongDiv, LongMult, LowHalf],
MB USING [BitArray, Error, Handle, Zero],
MBStorage USING [FreeWords, Words],
MBVM USING [
Base, Code, CodeSeg, DataSeg, DefaultBase, Direction, FileSeg, First64K, HyperSpace, MaxBase, MDS, nullIndex, Object, ObjectSeal, Pages, Seg],
Segments USING [DeleteSegment, FHandle, LockFromSegment, Unlock],
StartList USING [NullSwapUnitIndex];
MBVMemory: PROGRAM
IMPORTS Heap, Inline, MB, MBStorage, Segments
EXPORTS MB, MBVM =
BEGIN
OPEN MBVM;
PageSize: CARDINAL = Environment.wordsPerPage;
data: MB.Handle ← NIL;
z: UNCOUNTED ZONE ← NIL;
minimumLength: Base = PageSize*Environment.bitsPerWord;
incrementalLength: CARDINAL = PageSize*Environment.bitsPerWord;
InitVM: PUBLIC PROC [h: MB.Handle] = {
IF data ~= NIL THEN FinishVM[];
data ← h;
data.lastVMPage ← 0;
segList ← NIL;
z ← Heap.Create[4];
};
FinishVM: PUBLIC PROC = {
IF data.vmMap ~= NIL THEN {MBStorage.FreeWords[BASE[data.vmMap]]; data.vmMap ← NIL};
IF z ~= NIL THEN {Heap.Delete[z]; z ← NIL};
data ← NIL;
};
WordsForBits: PROC [nBits: CARDINAL] RETURNS [nWords: CARDINAL] = INLINE
{RETURN[(nBits+Environment.bitsPerWord-1)/Environment.bitsPerWord]};
Segment Routines
segList: 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 [s: 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];
s ← z.NEW[data Object ← Object[
index: StartList.NullSwapUnitIndex, base: base, pages: pages, link: segList,
body: data[]]
];
segList ← s;
};
AllocCode: PUBLIC PROC [
file: Segments.FHandle, base: Base, pages: Pages, fileBase: CARDINAL, sph: BcdOps.SPHandle]
RETURNS [s: 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];
s ← z.NEW[code Object ← Object[
index: StartList.NullSwapUnitIndex, base: base, pages: pages, link: segList,
body: code[sph: sph, file: file, fileBase: fileBase, segment: NIL]]];
segList ← s};
AllocFile: PUBLIC PROC [
file: Segments.FHandle, base: Base, pages: Pages, fileBase: CARDINAL]
RETURNS [s: 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];
s ← z.NEW[file Object ← Object[
index: StartList.NullSwapUnitIndex, base: base, pages: pages, link: segList,
body: file[file: file, fileBase: fileBase, segment: NIL, bIndex: nullIndex]]
];
segList ← s;
};
SortSegs: PUBLIC PROC RETURNS [segs: LONG DESCRIPTOR FOR ARRAY OF MBVM.Seg] = {
i, nSegs: CARDINAL;
seg: MBVM.Seg;
SiftUp: PROC [low, high: CARDINAL] = {
k, son: CARDINAL;
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: CARDINAL] = {
temp: MBVM.Seg ← segs[a];
segs[a] ← segs[b];
segs[b] ← temp;
};
nSegs ← 0;
FOR seg ← segList, seg.link UNTIL seg = NIL DO nSegs ← nSegs + 1 ENDLOOP;
segs ← DESCRIPTOR[MBStorage.Words[nSegs*SIZE[MBVM.Seg]], nSegs];
i ← 0;
FOR seg ← segList, seg.link UNTIL seg = NIL DO
segs[i] ← seg; 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[Inline.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[s.base = base]};
RETURN[EnumerateSegs[FindSeg]]
};
SegFromLongPointer: PUBLIC PROC [p: LONG POINTER] RETURNS [s: Seg] = {
base: Base ← Inline.LongDiv[LOOPHOLE[p], PageSize];
FindSeg: PROC [seg: Seg] RETURNS [BOOL] = {RETURN[s.base = base]};
RETURN[EnumerateSegs[FindSeg]]
};
VM Routines
EnumerateSegs: PROC [proc: PROC [Seg] RETURNS [BOOL]] RETURNS [Seg] = {
FOR seg: Seg ← segList, seg.link UNTIL seg = NIL DO
IF proc[seg] THEN RETURN[seg];
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];
wordsForMap: CARDINAL = WordsForBits[initialLength];
data.vmMap ← DESCRIPTOR[MBStorage.Words[wordsForMap], initialLength];
MB.Zero[BASE[data.vmMap], wordsForMap];
};
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, LENGTH[data.vmMap]-1]};
ENDCASE => {incr ← -1; vm ← MIN[high, LENGTH[data.vmMap]-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"L];
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"L];
};
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 > LENGTH[data.vmMap] DO
IF ~ExtendVM[] THEN ERROR;
ENDLOOP;
};
ExtendVM: PROC RETURNS [worked: BOOL] = {
use LONG arithmetic to avoid overflows
newLength: CARDINAL =
Inline.LowHalf[MIN[LONG[LENGTH[data.vmMap]] + incrementalLength, LONG[MaxBase] + 1]];
newWords: CARDINAL = WordsForBits[newLength];
newMap: MB.BitArray;
IF LENGTH[data.vmMap] = newLength THEN RETURN[FALSE];
newMap ← DESCRIPTOR[MBStorage.Words[newWords], newLength];
MB.Zero[BASE[newMap], newWords];
Inline.LongCOPY[
from: BASE[data.vmMap], to: BASE[newMap], nwords: WordsForBits[LENGTH[data.vmMap]]];
MBStorage.FreeWords[BASE[data.vmMap]];
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.