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]}; 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]] }; 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]; 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] }; 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. 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 Segment Routines VM Routines allocate 'pages' consecutive pages in virtual pages range [low..high]. Can't find sufficient VM in present vmMap. If it hasn't reached its limit, extend it and try again. use LONG arithmetic to avoid overflows 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! Ê ÿ˜Jšœ™Jšœ+™+Jšœ*™*Jšœ2™2J˜šÏk ˜ Jšœœ"˜.Jšœœ ˜Jšœœ˜(Jšœœ+˜3šœœ˜ Jšœ^œ5˜–—Jšœ œ˜Jšœ œ3˜AJ˜—šœ ˜Jšœ œ ˜Jšœœœ˜—J˜Jš˜J˜Jšœœ˜ J˜Jšœ œ˜+J˜Jšœœ œ˜J˜J˜2Jšœœ˜:J˜šÏnœœœœ ˜&J˜ J˜Jšœ œ˜J˜J˜—šžœœœ˜Jšœ œ˜Jšœ˜ Jšœ˜J˜—š ž œœ œœ œ˜HJšœœ3˜:J˜—Jšœ™J˜Jšœ œœœ˜J˜šž œœœ˜Jšœ1œ˜Išœ˜Jšœœ˜Jšœœ˜$Jšœ!˜(—Jšœ/˜5Jšœ˜J˜—šž œœœ3œ˜bJ˜šœ˜JšœH˜KJ˜8J˜MJšœ˜&—JšœOœ˜Všœ œ˜šœœ˜JšœQ˜Q—J˜J˜—J˜J˜—šž œœœ˜Jšœ<œ˜\Jšœ˜J˜šœ˜J˜DJšœ˜&—JšœNœ˜Tšœ œ˜šœœ˜JšœA˜AJšœ>œ˜E—J˜J˜—J˜J˜—šž œœœ˜Jšœ<œœ˜_J˜šœ˜JšœH˜KJ˜8J˜MJšœ˜&—JšœNœ˜Ušœ œ˜šœœ˜JšœA˜AJšœ4œ˜N—J˜J˜—J˜J˜—š žœœœœœ˜4Jšœ œ˜šžœœ œ˜!Jšœœ˜ J˜š˜Jšœ œœ˜Jšœœ'œ ˜GJšœ ˜Jšœ#œœ˜/J˜J˜Jš˜—Jšœ˜—šžœœœ˜Jšœœ˜J˜J˜J˜—J˜ Jšœœœœœœœ˜YJšœœ˜ J˜š œœœœœ˜>J˜"Jšœ˜—Jš œ œœœœ˜=Jš œ œœ œ˜HJšœ˜J˜—šžœœœ˜ šžœœ œœ˜:šœœ˜˜šœ œœ˜Jšœ(œ˜HJ˜ Jšœ ˜Jšœ˜——Jšœ˜—Jšœœ˜ Jšœ˜—J˜&J˜J˜—š žœœœ œœ˜=Jšœ œ#œœ˜Jšœœœ ˜,Jšœ˜—Jšœœ˜ Jšœ˜J˜—šžœœCœ˜UJšœ ˜J˜ šœœœ˜Jšœœœ˜;Jšœ œœ ˜3Jš œœœœœœ˜HJ˜—šœ˜JšœF™Fš˜Jšœœ˜JšœœÏc!˜3šœ˜Jšœœ˜6Jšœœ˜=—š œœœ œ œ ˜HJšœœœœ˜;šœœœ˜"Jšœœ œ œ˜+šœœœŸ!˜QJšœ œ$˜4Jšœ&˜*—Jšœœ˜,J˜J˜—Jšœ˜—JšœK™KJšœ™Jšœ œœ˜,Jš˜——šœ˜J˜šœœ˜Jš œœœœœ˜;š˜Jšœœ˜4—Jšœ˜—Jšœ˜Jšœ˜—Jš˜Jšœ˜J˜—šžœœœœ˜DJšœ"˜(J˜—šž œœ˜.Jšœœ ˜5J˜Jš œœœœ˜BJšœ˜J˜—šžœœœ˜+šœ˜!Jšœ œœ˜Jš˜—šœ˜J˜——šžœœœ œ˜)Jšœ&™&šœ œ˜Jšœœ)œ˜D—Jšœœ œœ˜8Jšœœœœ˜4Jš œœœœœ˜PJš œœœ œœœ˜TJ˜Jšœœ˜ Jšœ˜J˜—JšœN™NJšœ,™,J˜šž œœ˜.šœ ˜&š œ œ œœ˜=Jšœœœ˜@Jšœ˜——Jš œœœœ˜Bšœ˜J˜J˜——šœ˜˜J˜———…—R+_