-- MDSRegion.Mesa Edited by Sandman on September 4, 1980 4:09 PM
-- Copyright Xerox Corporation 1979, 1980
DIRECTORY
AllocDefs USING [SwappingProcedure, SwapStrategy],
AltoDefs USING [PageCount, PageNumber, PageSize],
ControlDefs USING [
GFT, GlobalFrameHandle, NullGlobalFrame, PrefixHandle, PrefixHeader],
Inline USING [BITAND, BITOR],
Map USING [Clean, Entry, SETF],
NucleusOps USING [],
ProcessDefs USING [DisableInterrupts, EnableInterrupts],
Region USING [
Count, MaxRegionPage, Node, NodeObject, NodeSeal, Object, Page,
PagesPerRegion, PageStatus],
SDDefs USING [SD, sGFTLength],
SegmentDefs USING [
AddressFromPage, AllocInfo, FileSegmentHandle, MemoryConfig, SegmentHandle],
SwapperOps USING [BusyPage, FreePage, PageMap, PageTable];
MDSRegion: PROGRAM
IMPORTS Inline, Map, ProcessDefs, SegmentDefs
EXPORTS AllocDefs, NucleusOps, SwapperOps, SegmentDefs
SHARES SegmentDefs =PUBLIC
BEGIN OPEN Inline, SegmentDefs, AltoDefs, SwapperOps, AllocDefs, Region;
GlobalFrameHandle: TYPE = ControlDefs.GlobalFrameHandle;
memConfig: PUBLIC MemoryConfig;
-- MDS Region
mdsNodes: NodeObject;
pageTable: PageTable;
map: PageMap ← @pageTable;
ff, lf, rover, roverCopy: Region.Page;
mdsRegion: Region.Object;
strategyList: POINTER TO SwapStrategy;
InvalidNode: ERROR [node: UNSPECIFIED] = CODE;
Available: PROCEDURE [page: Region.Page, info: AllocInfo]
RETURNS [available: BOOLEAN] =
BEGIN
seg: SegmentHandle;
available ← FALSE;
ProcessDefs.DisableInterrupts[];
SELECT (seg ← map[page]) FROM
FreePage => available ← TRUE;
BusyPage => NULL;
ENDCASE => {
IF BITAND[seg, 1] # 0 THEN
seg ← LOOPHOLE[BITAND[seg, 177776B], GlobalFrameHandle].code.handle;
WITH s: seg SELECT FROM
file =>
IF info.effort = hard AND s.lock = 0 AND ~s.write AND ~s.busy THEN
available ← TRUE;
ENDCASE};
ProcessDefs.EnableInterrupts[];
RETURN
END;
Status: PROCEDURE [page: Region.Page]
RETURNS [seg: SegmentHandle, status: PageStatus] =
BEGIN
ProcessDefs.DisableInterrupts[];
SELECT (seg ← map[page]) FROM
BusyPage => BEGIN status ← busy; seg ← NIL END;
FreePage => BEGIN status ← free; seg ← NIL END;
ENDCASE => {
IF BITAND[seg, 1] # 0 THEN
seg ← LOOPHOLE[BITAND[seg, 177776B], GlobalFrameHandle].code.handle;
IF seg.busy THEN BEGIN status ← busy; seg ← NIL; END ELSE status ← inuse};
ProcessDefs.EnableInterrupts[];
RETURN
END;
Alloc: PROCEDURE [
base: PageNumber, pages: Count, info: AllocInfo, anyWhere: BOOLEAN]
RETURNS [BOOLEAN, Page] =
BEGIN
vm: Page;
IF ~anyWhere THEN
BEGIN
ProcessDefs.DisableInterrupts[];
FOR vm IN [base..base + pages) DO
IF ~Available[vm, info] THEN GOTO noRoom; ENDLOOP;
END
ELSE
BEGIN
n: CARDINAL ← 0; -- count of contiguous free pages
direction: INTEGER;
ProcessDefs.DisableInterrupts[];
IF info.effort = hard THEN
BEGIN
IF info.direction = bottomup THEN BEGIN direction ← 1; base ← ff; END
ELSE BEGIN direction ← -1; base ← lf; END;
WHILE base IN [ff..lf] DO
IF ~Available[base, info] THEN n ← 0
ELSE
IF (n ← n + 1) = pages THEN
BEGIN IF direction > 0 THEN base ← base - n + 1; EXIT END;
base ← base + direction
REPEAT FINISHED => GOTO noRoom;
ENDLOOP
END
ELSE
BEGIN
n: Node ← @mdsNodes;
up: BOOLEAN = info.direction = bottomup;
DO
n ← IF up THEN n.fwd ELSE n.back;
IF n = @mdsNodes THEN GOTO noRoom;
IF n # AddressFromPage[n.base] OR n.seal # Region.NodeSeal THEN
ERROR InvalidNode[n];
SELECT n.pages FROM
> pages =>
BEGIN
IF ~up THEN base ← n.base + (n.pages ← n.pages - pages)
ELSE
BEGIN
new: Node ← AddressFromPage[(base ← n.base) + pages];
new↑ ←
[base: base + pages, pages: n.pages - pages, fwd: n.fwd,
back: n.back];
new.back.fwd ← new;
new.fwd.back ← new;
END;
EXIT;
END;
= pages => {base ← n.base; n.back.fwd ← n.fwd; n.fwd.back ← n.back; EXIT};
ENDCASE;
ENDLOOP;
Update[base, pages, BusyPage, TRUE];
ProcessDefs.EnableInterrupts[];
RETURN[TRUE, base]
END;
END;
FOR vm IN [base..base + pages) DO
BEGIN
tempseg: SegmentHandle ← Status[vm].seg;
IF tempseg # NIL THEN
WITH s: tempseg SELECT FROM
file => {
Update[s.VMpage MOD PagesPerRegion, s.pages, FreePage, FALSE];
IF s.class = code THEN UpdateCodebases[@s];
s.swappedin ← FALSE;
s.file.swapcount ← s.file.swapcount - 1};
ENDCASE;
END;
ENDLOOP;
Update[base, pages, BusyPage, FALSE];
ProcessDefs.EnableInterrupts[];
RETURN[TRUE, base]
EXITS noRoom => BEGIN ProcessDefs.EnableInterrupts[]; RETURN[FALSE, 0] END;
END;
Update: PROCEDURE [
base: Page, pages: Count, seg: SegmentHandle, simple: BOOLEAN] =
BEGIN
IF seg = FreePage THEN
BEGIN
ProcessDefs.DisableInterrupts[];
ff ← MIN[ff, base];
lf ← MAX[lf, base + pages - 1];
ProcessDefs.EnableInterrupts[];
END;
IF simple THEN
BEGIN
n: Node;
ProcessDefs.DisableInterrupts[];
mdsRegion.hole ← 0;
FOR base IN [base..base + pages) DO map[base] ← seg; ENDLOOP;
FOR n ← mdsNodes.fwd, n.fwd UNTIL n = @mdsNodes DO
IF n # AddressFromPage[n.base] OR n.seal # Region.NodeSeal THEN
ERROR InvalidNode[n];
mdsRegion.hole ← MAX[mdsRegion.hole, n.pages];
ENDLOOP;
ProcessDefs.EnableInterrupts[];
END
ELSE
IF seg = FreePage THEN
BEGIN
n, n1: Node;
page: Page;
ProcessDefs.DisableInterrupts[];
FOR page IN [base..base + pages) DO
IF map[page] = FreePage THEN ERROR; map[page] ← FreePage; ENDLOOP;
-- Validate nodes
FOR n ← mdsNodes.fwd, n.fwd UNTIL n = @mdsNodes DO
IF n # AddressFromPage[n.base] OR n.seal # Region.NodeSeal THEN
ERROR InvalidNode[n];
ENDLOOP; -- enter new node in order
-- R: n.back.base < base < n.base OR n.back = @mdsNodes;
-- P: base < n.base; mdsNodes.base = 177777B
n ← @mdsNodes;
DO
n1 ← n.back;
IF n1 = @mdsNodes OR n1.base < base THEN EXIT;
n ← n1;
ENDLOOP;
n1 ← AddressFromPage[base];
n1↑ ← [base: base, pages: pages, fwd: n, back: n.back];
n.back.fwd ← n1;
n.back ← n1;
mdsRegion.hole ← MAX[mdsRegion.hole, pages];
n ← mdsNodes.fwd;
DO
n1 ← n.fwd;
IF n.base + n.pages = n1.base THEN
BEGIN
mdsRegion.hole ← MAX[n.pages ← n.pages + n1.pages, mdsRegion.hole];
n.fwd ← n1.fwd;
n1.fwd.back ← n;
END
ELSE n ← n1;
IF n = @mdsNodes THEN EXIT;
ENDLOOP;
ProcessDefs.EnableInterrupts[];
END
ELSE
BEGIN
newFree: BOOLEAN ← FALSE;
ProcessDefs.DisableInterrupts[];
FOR base IN [base..base + pages) DO
IF map[base] = FreePage THEN newFree ← TRUE; map[base] ← seg; ENDLOOP;
IF newFree THEN
BEGIN
state: {free, busy} ← busy;
mdsNodes.fwd ← mdsNodes.back ← @mdsNodes;
mdsRegion.hole ← 0;
FOR base DECREASING IN [0..MaxRegionPage] DO
IF map[base] = FreePage THEN
IF state = free THEN pages ← pages + 1
ELSE BEGIN state ← free; pages ← 1; END
ELSE
IF state = free THEN
BEGIN
new: Node ← AddressFromPage[base + 1];
new↑ ←
[base: base + 1, pages: pages, fwd: mdsNodes.fwd,
back: @mdsNodes];
new.fwd.back ← new;
mdsNodes.fwd ← new;
mdsRegion.hole ← MAX[mdsRegion.hole, pages];
state ← busy;
END;
ENDLOOP;
END;
ProcessDefs.EnableInterrupts[];
END;
RETURN
END;
trySwapInProgress: BOOLEAN ← FALSE;
TrySwapping: SwappingProcedure =
BEGIN
did: BOOLEAN;
sp, next: POINTER TO SwapStrategy;
ProcessDefs.DisableInterrupts[];
IF trySwapInProgress THEN
BEGIN
ProcessDefs.EnableInterrupts[];
RETURN[TryCodeSwapping[needed, info, seg]];
END;
trySwapInProgress ← TRUE;
ProcessDefs.EnableInterrupts[];
did ← TRUE;
FOR sp ← strategyList, next UNTIL sp = NIL DO
next ← sp.link;
IF sp.proc[needed, info, seg] THEN EXIT;
REPEAT FINISHED => did ← FALSE;
ENDLOOP;
trySwapInProgress ← FALSE;
RETURN[did]
END;
CantSwap: SwappingProcedure = BEGIN RETURN[FALSE] END;
TryCodeSwapping: SwappingProcedure =
BEGIN OPEN ControlDefs;
foundHole: BOOLEAN;
readMap: BOOLEAN = memConfig.AltoType = D0 OR memConfig.AltoType = Dorado;
pass: {first, second, quit} ← first;
okay: BOOLEAN;
base, page: Page;
segment: SegmentHandle;
n, inc: PageCount;
page ← n ← 0;
ProcessDefs.DisableInterrupts[];
segment ← Status[roverCopy ← rover].seg;
IF segment # NIL THEN rover ← segment.VMpage MOD PagesPerRegion;
base ← rover;
DO
-- until we've looked at them all twice
okay ← FALSE;
SELECT (segment ← map[rover]) FROM
BusyPage => inc ← 1;
FreePage => {okay ← TRUE; inc ← 1};
ENDCASE => {
IF BITAND[segment, 1] # 0 THEN
segment ← LOOPHOLE[BITAND[segment, 177776B], GlobalFrameHandle].code.handle;
WITH s: segment SELECT FROM
data => inc ← s.pages;
file =>
BEGIN
IF s.lock = 0 AND ~s.write AND ~s.busy THEN
BEGIN
IF readMap THEN {
t: Map.Entry ← Map.Clean;
FOR p: CARDINAL IN [s.VMpage..s.VMpage + s.pages) DO
t ← BITOR[t, Map.SETF[p, Map.Clean]]; ENDLOOP;
IF ~t.flags.R THEN okay ← TRUE}
ELSE
IF s.class = code THEN
BEGIN
p: PrefixHandle ← AddressFromPage[s.VMpage];
info: CARDINAL ← p.header.swapinfo;
IF info > 1 THEN
BEGIN p ← p + info; info ← p.header.swapinfo; END;
IF info = 0 THEN okay ← TRUE ELSE p.header.swapinfo ← 0;
END
ELSE IF s.inuse THEN s.inuse ← FALSE ELSE okay ← TRUE;
END;
inc ← s.pages;
END;
ENDCASE};
IF ~okay THEN {page ← n ← 0; IF pass = quit THEN {foundHole ← FALSE; EXIT}}
ELSE {
IF page = 0 THEN page ← rover;
IF (n ← n + inc) >= needed THEN {foundHole ← TRUE; EXIT}};
IF (rover ← rover + inc) > MaxRegionPage THEN
IF pass = quit THEN BEGIN foundHole ← FALSE; EXIT END
ELSE BEGIN rover ← page ← 0; n ← 0; END;
IF rover = base THEN IF pass = first THEN pass ← second ELSE pass ← quit;
ENDLOOP;
base ← rover ← page + n;
WHILE page < base DO
SELECT (segment ← map[page]) FROM
BusyPage, FreePage => page ← page + 1;
ENDCASE => {
relPage: Page;
IF BITAND[segment, 1] # 0 THEN
segment ← LOOPHOLE[BITAND[segment, 177776B], GlobalFrameHandle].code.handle;
relPage ← segment.VMpage MOD PagesPerRegion;
WITH s: segment SELECT FROM
data => page ← relPage + s.pages;
file => {
IF s.lock = 0 THEN {
IF s.class = code THEN UpdateCodebases[@s];
s.swappedin ← FALSE;
s.file.swapcount ← s.file.swapcount - 1;
Update[relPage, s.pages, FreePage, FALSE]};
page ← relPage + s.pages};
ENDCASE};
ENDLOOP;
ProcessDefs.EnableInterrupts[];
RETURN[foundHole]
END;
UpdateCodebases: PUBLIC PROCEDURE [seg: FileSegmentHandle] =
BEGIN OPEN ControlDefs;
lastUser, f: ControlDefs.GlobalFrameHandle;
nUsers, i: CARDINAL;
epbase: CARDINAL;
segBase: PageNumber;
vmpage: PageNumber;
ProcessDefs.DisableInterrupts[];
IF BITAND[seg, 1] # 0 THEN {
f ← BITAND[seg, 177776B];
seg ← f.code.handle;
IF ~f.shared THEN f.code.offset ← f.code.offset - AltoDefs.PageSize*seg.VMpage + 1};
nUsers ← 0;
FOR i IN [1..SDDefs.SD[SDDefs.sGFTLength]) DO
[frame: f, epbase: epbase] ← GFT[i];
IF f # NullGlobalFrame AND epbase = 0 THEN
BEGIN
IF ~f.code.out THEN
BEGIN
vmpage ← f.code.offset/AltoDefs.PageSize;
IF f.code.highByte = 0 THEN
vmpage ← vmpage + PagesPerRegion*CARDINAL[f.code.highHalf];
segBase ← seg.VMpage;
IF vmpage ~IN [segBase..segBase + seg.pages) THEN LOOP;
f.code.offset ← f.code.offset - AltoDefs.PageSize*segBase + 1;
f.code.handle ← LOOPHOLE[seg];
END
ELSE IF f.code.handle # LOOPHOLE[seg] THEN LOOP;
IF ~f.shared THEN EXIT;
nUsers ← nUsers + 1;
lastUser ← f;
END;
REPEAT FINISHED => IF nUsers = 1 THEN lastUser.shared ← FALSE;
ENDLOOP;
ProcessDefs.EnableInterrupts[];
RETURN
END;
END.....