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. NMBVMemory.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Sandman on 6-Aug-81 15:43:17 Lewis on 17-Sep-81 15:52:42 Levin on January 13, 1984 1:40 pm Russ Atkinson (RRA) May 13, 1985 11:21:50 pm PDT 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! Κ ˜codešœ™Kšœ Οmœ1™K˜"Kšžœ˜—Kš žœž œžœžœžœ˜=Kš žœž œžœ žœž˜HKšœ˜K˜—š Ÿœžœžœ žœžœžœ˜EKšžœ žœ#žœžœ˜Kšžœžœžœ ˜,Kšžœ˜—Kšžœžœ˜ Kšœ˜K˜—šŸœžœCžœ˜UKšžœ ˜K˜ šžœžœžœ˜Kšœžœžœ˜;Kšœ žœžœ ˜3Kš žœžœžœžœžœžœ˜HK˜—šžœž˜KšœF™Fšž˜Kšœžœ˜KšœžœΟc!˜3šžœž˜Kšœžœ˜6Kšžœžœ˜=—š žœžœžœ žœ žœ ž˜HKšžœžœžœžœ˜;šžœžœžœ˜"Kšœžœ žœ žœ˜+šžœžœžœ !˜QKšžœ žœ$˜4Kšžœ&˜*—Kšžœžœ˜,K˜K˜—Kšžœ˜—KšœK™KKšœ™Kšžœ žœžœ˜,Kšž˜——šžœ˜K˜šžœžœž˜Kš žœžœžœžœžœ˜;šž˜Kšžœžœ˜4—Kšžœ˜—Kšžœ˜Kšœ˜—Kšž˜Kšœ˜K˜—šŸœžœžœžœ˜DKšžœ!˜'Kšœ˜K˜—šŸ œžœ˜.Kšœžœ ˜5K˜Kš žœžœžœžœž˜BKšœ˜K˜—šŸœžœžœ˜+šžœž˜!Kšžœ žœžœ˜Kšž˜—šœ˜K˜——šŸœžœžœ žœ˜)Kšœ&™&šœ žœ˜Kšžœžœ)žœ˜D—šžœ˜Kšžœžœžœ˜šžœ˜Kšœžœ žœžœ˜8Kšžœžœžœžœ˜4Kš žœžœžœžœžœ˜PKš žœžœžœ žœ žœžœ˜PK˜Kšžœžœ˜ K˜——Kšœ˜K˜—KšœN™NKšœ,™,K˜šŸ œžœ˜.šžœ ž˜&š žœ žœž œžœž˜=Kšžœžœžœ˜@Kšžœ˜——Kš žœžœžœžœž˜Bšœ˜K˜K˜——šžœ˜˜K˜———…—(+‹