<> <> <> <> <> <> 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]}; <> 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]] }; <> 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 <> 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; <> <> 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] = { <> 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]; }; }; <> <> 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.