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 September 30, 1983 4:00 pm
DIRECTORY
Basics USING [bitsPerWord, LongDiv, LongMult],
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 [wordsPerPage],
Segments USING [DeleteSegment, FHandle, LockFromSegment, Unlock];
MBVMemory:
PROGRAM
IMPORTS Basics, MB, Segments
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: 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[Basics.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 ← Basics.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 =
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