-- HyperRegion.Mesa Edited by Sandman on September 4, 1980 4:17 PM
-- Copyright Xerox Corporation 1979, 1980
DIRECTORY
AllocDefs USING [SwappingProcedure],
InlineDefs USING [BITOR],
Map USING [Clean, Entry, SETF, VacantFlags],
Mopcodes USING [zRBL, zWBL],
NucleusOps USING [],
ProcessDefs USING [DisableInterrupts, EnableInterrupts],
Region USING [
Count, Handle, Index, MaxRegionPage, Node, Object, Page, PagesPerRegion,
PageStatus],
SegmentDefs USING [
AddressFromPage, AllocInfo, DataSegmentHandle, FileSegmentHandle, memConfig,
Object, PageCount, PageNumber, SegmentHandle, SwapOut, TableDS],
SwapperOps USING [
AllocateObject, BusyPage, FreePage, LiberateObject, Page, PageStatus,
UpdateCodebases];
HyperRegion: PROGRAM [index: Region.Index] RETURNS [Region.Handle]
IMPORTS InlineDefs, Map, ProcessDefs, SegmentDefs, SwapperOps
EXPORTS NucleusOps, Region
SHARES SegmentDefs =
BEGIN OPEN Region, SegmentDefs, SwapperOps;
disabled: BOOLEAN;
freeList: Node;
ff, lf, rover: Page;
mapSegment: DataSegmentHandle;
myRegion: Region.Object;
ReadPrefixInfo: PROCEDURE [p: POINTER, region: Index ← index]
RETURNS [CARDINAL] = MACHINE CODE BEGIN Mopcodes.zRBL, 0 END;
WritePrefixInfo: PROCEDURE [info: CARDINAL, p: POINTER, region: Index ← index] =
MACHINE CODE BEGIN Mopcodes.zWBL, 0 END;
ReadMap: PROCEDURE [page: Page, region: Index ← index] RETURNS [SegmentHandle] =
MACHINE CODE BEGIN Mopcodes.zRBL, 0 END;
WriteMap: PROCEDURE [seg: SegmentHandle, page: Page, region: Index ← index] =
MACHINE CODE BEGIN Mopcodes.zWBL, 0 END;
ReadBase: PROCEDURE [node: Node, region: Index ← index] RETURNS [CARDINAL] =
MACHINE CODE BEGIN Mopcodes.zRBL, 0 END;
WriteBase: PROCEDURE [base: CARDINAL, node: Node, region: Index ← index] =
MACHINE CODE BEGIN Mopcodes.zWBL, 0 END;
ReadPages: PROCEDURE [node: Node, region: Index ← index] RETURNS [CARDINAL] =
MACHINE CODE BEGIN Mopcodes.zRBL, 1 END;
WritePages: PROCEDURE [pages: CARDINAL, node: Node, region: Index ← index] =
MACHINE CODE BEGIN Mopcodes.zWBL, 1 END;
ReadFwdLink: PROCEDURE [node: Node, region: Index ← index] RETURNS [Node] =
MACHINE CODE BEGIN Mopcodes.zRBL, 2 END;
WriteFwdLink: PROCEDURE [link: Node, node: Node, region: Index ← index] =
MACHINE CODE BEGIN Mopcodes.zWBL, 2 END;
ReadBackLink: PROCEDURE [node: Node, region: Index ← index] RETURNS [Node] =
MACHINE CODE BEGIN Mopcodes.zRBL, 3 END;
WriteBackLink: PROCEDURE [link: Node, node: Node, region: Index ← index] =
MACHINE CODE BEGIN Mopcodes.zWBL, 3 END;
Available: PROCEDURE [page: Page, info: AllocInfo]
RETURNS [available: BOOLEAN] =
BEGIN
seg: SegmentHandle;
available ← FALSE;
IF disabled THEN RETURN;
ProcessDefs.DisableInterrupts[];
seg ← ReadMap[page: page];
SELECT seg FROM
FreePage => available ← TRUE;
BusyPage => NULL;
ENDCASE =>
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: Page]
RETURNS [seg: SegmentHandle, status: PageStatus] =
BEGIN
IF disabled THEN RETURN[NIL, busy];
ProcessDefs.DisableInterrupts[];
seg ← ReadMap[page: page];
SELECT seg FROM
BusyPage => BEGIN status ← busy; seg ← NIL END;
FreePage => BEGIN status ← free; seg ← NIL END;
ENDCASE =>
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 disabled THEN RETURN[FALSE, 0];
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
nodePages: CARDINAL;
n: Node ← freeList;
IF n = NIL THEN GOTO noRoom;
DO
nodePages ← ReadPages[node: n];
base ← ReadBase[node: n];
SELECT nodePages FROM
> pages =>
BEGIN
base ← base + (nodePages ← nodePages - pages);
WritePages[pages: nodePages, node: n];
EXIT;
END;
= pages =>
BEGIN
back: Node ← ReadBackLink[node: n];
fwd: Node ← ReadFwdLink[node: n];
IF back = n THEN freeList ← NIL
ELSE
BEGIN
IF freeList = n THEN freeList ← back;
WriteBackLink[link: back, node: fwd];
WriteFwdLink[link: fwd, node: back];
END;
EXIT;
END;
ENDCASE;
n ← ReadFwdLink[node: n];
IF n = freeList THEN GOTO noRoom;
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 =>
BEGIN
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;
END;
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 disabled THEN RETURN;
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[];
myRegion.hole ← 0;
FOR base IN [base..base + pages) DO WriteMap[page: base, seg: seg]; ENDLOOP;
IF (n ← freeList) # NIL THEN
DO
myRegion.hole ← MAX[ReadPages[node: n], myRegion.hole];
n ← ReadFwdLink[node: n];
IF n = freeList THEN EXIT;
ENDLOOP;
ProcessDefs.EnableInterrupts[];
END
ELSE
IF seg = FreePage THEN
BEGIN
n: Node;
page: Page;
nodePages: CARDINAL;
ProcessDefs.DisableInterrupts[];
FOR page IN [base..base + pages) DO
IF ReadMap[page: page] = FreePage THEN ERROR;
WriteMap[page: page, seg: FreePage];
ENDLOOP;
AddNode[base: base, pages: pages];
n ← freeList;
DO
nodePages ← ReadPages[node: n];
IF (base ← ReadBase[node: n] + nodePages) <= MaxRegionPage AND ReadMap[
page: base] = FreePage THEN
BEGIN
oldNode: Node ← AddressFromPage[base];
back: Node ← ReadBackLink[node: oldNode];
fwd: Node ← ReadFwdLink[node: oldNode];
WriteBackLink[link: back, node: fwd];
WriteFwdLink[link: fwd, node: back];
IF freeList = oldNode THEN freeList ← n;
nodePages ← ReadPages[node: oldNode] + nodePages;
myRegion.hole ← MAX[nodePages, myRegion.hole];
WritePages[pages: nodePages, node: n];
END
ELSE {n ← ReadFwdLink[node: n]; IF n = freeList THEN EXIT};
ENDLOOP;
ProcessDefs.EnableInterrupts[];
END
ELSE
BEGIN
newFree: BOOLEAN ← FALSE;
ProcessDefs.DisableInterrupts[];
FOR base IN [base..base + pages) DO
IF ReadMap[page: base] = FreePage THEN newFree ← TRUE;
WriteMap[page: base, seg: seg];
ENDLOOP;
IF newFree THEN
BEGIN
state: {free, busy} ← busy;
freeList ← NIL;
myRegion.hole ← 0;
FOR base DECREASING IN [0..MaxRegionPage] DO
IF ReadMap[page: base] = FreePage THEN
IF state = free THEN pages ← pages + 1
ELSE BEGIN state ← free; pages ← 1; END
ELSE
IF state = free THEN
BEGIN AddNode[base: base + 1, pages: pages]; state ← busy END;
ENDLOOP;
END;
ProcessDefs.EnableInterrupts[];
END;
RETURN
END;
AddNode: PROCEDURE [base: Page, pages: Count] =
BEGIN
n: Node ← AddressFromPage[base];
WriteBase[base: base, node: n];
WritePages[pages: pages, node: n];
IF freeList = NIL THEN
BEGIN
freeList ← n;
WriteBackLink[link: n, node: n];
WriteFwdLink[link: n, node: n];
END
ELSE
BEGIN
fwd: Node ← ReadFwdLink[node: freeList];
WriteBackLink[link: n, node: fwd];
WriteFwdLink[link: fwd, node: n];
WriteBackLink[link: freeList, node: n];
WriteFwdLink[link: n, node: freeList];
END;
myRegion.hole ← MAX[myRegion.hole, pages];
END;
CodeSwap: AllocDefs.SwappingProcedure =
BEGIN
foundHole: BOOLEAN ← FALSE;
segment: SegmentHandle;
base, page: Page;
n, inc: PageCount;
readMap: BOOLEAN = memConfig.AltoType = D0 OR memConfig.AltoType = Dorado;
pass: {first, second, quit} ← first;
IF disabled THEN RETURN[FALSE];
page ← n ← 0;
ProcessDefs.DisableInterrupts[];
segment ← Status[rover].seg;
IF segment # NIL THEN rover ← segment.VMpage MOD PagesPerRegion;
base ← rover;
DO
-- until we've looked at them all twice
okay: BOOLEAN;
status: PageStatus;
[segment, status] ← Status[rover];
okay ← FALSE;
SELECT status FROM
inuse =>
WITH s: segment SELECT FROM
data => inc ← s.pages;
file =>
BEGIN
IF s.lock = 0 AND ~s.write THEN
BEGIN
IF readMap THEN {
t: Map.Entry ← Map.Clean;
FOR p: CARDINAL IN [s.VMpage..s.VMpage + s.pages) DO
t ← InlineDefs.BITOR[t, Map.SETF[p, Map.Clean]]; ENDLOOP;
IF ~t.flags.R THEN okay ← TRUE}
ELSE
IF s.class = code THEN
BEGIN
p: POINTER ← AddressFromPage[s.VMpage];
info: CARDINAL ← ReadPrefixInfo[p];
IF info > 1 THEN
BEGIN p ← p + info; info ← ReadPrefixInfo[p]; END;
IF info = 0 THEN okay ← TRUE ELSE WritePrefixInfo[0, p];
END
ELSE IF s.inuse THEN s.inuse ← FALSE ELSE okay ← TRUE;
END;
inc ← s.pages;
END;
ENDCASE;
ENDCASE => BEGIN IF status = free THEN okay ← TRUE; inc ← 1; END;
IF ~okay THEN {
page ← n ← 0; IF pass = quit THEN BEGIN foundHole ← FALSE; EXIT END}
ELSE
BEGIN
IF page = 0 THEN page ← rover;
IF (n ← n + inc) >= needed THEN BEGIN foundHole ← TRUE; EXIT END;
END;
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;
rover ← base ← page + n;
IF rover > MaxRegionPage THEN rover ← 1;
WHILE page < base DO
segment ← Status[page].seg;
IF segment # NIL THEN
BEGIN
relPage: Page = segment.VMpage MOD PagesPerRegion;
WITH s: segment SELECT FROM
data => page ← relPage + s.pages;
file =>
BEGIN
IF s.lock = 0 THEN
BEGIN
IF s.class = code THEN UpdateCodebases[@s];
s.swappedin ← FALSE;
s.file.swapcount ← s.file.swapcount - 1;
Update[relPage, s.pages, FreePage, FALSE];
END;
page ← relPage + s.pages; -- cross jumped to data select arm
END;
ENDCASE;
END
ELSE page ← page + 1;
ENDLOOP;
ProcessDefs.EnableInterrupts[];
RETURN[foundHole]
END;
ImmovableSegmentInXM: SIGNAL [seg: SegmentHandle] = CODE;
Disable: PROCEDURE [abandon: BOOLEAN] =
BEGIN
page: Page ← 1;
seg: SegmentHandle;
IF disabled THEN RETURN;
disabled ← TRUE;
IF abandon THEN {LiberateObject[mapSegment]; RETURN};
WHILE page <= MaxRegionPage DO
seg ← ReadMap[page: page];
IF seg = BusyPage OR seg = FreePage THEN {page ← page + 1; LOOP};
WITH s: seg SELECT FROM
data => {SIGNAL ImmovableSegmentInXM[@s]; page ← page + s.pages};
file => {
IF s.lock # 0 THEN SIGNAL ImmovableSegmentInXM[@s]
ELSE IF s.class # code THEN SwapOut[@s] ELSE {
UpdateCodebases[@s];
s.swappedin ← FALSE;
s.file.swapcount ← s.file.swapcount - 1};
page ← page + s.pages};
ENDCASE;
ENDLOOP;
LiberateObject[mapSegment];
END;
Initialize: PROCEDURE RETURNS [Handle] =
BEGIN
page: Page;
myRegion ←
[basePage: index*PagesPerRegion, alloc: Alloc, update: Update,
available: Available, status: Status, swap: CodeSwap, disable: Disable,
hole:];
FOR page IN Page DO WriteMap[page: page, seg: FreePage]; ENDLOOP;
disabled ← FALSE;
freeList ← NIL;
rover ← ff ← 1;
IF memConfig.AltoType = AltoIIXM THEN
BEGIN
WriteMap[page: 376B, seg: BusyPage];
WriteMap[page: 377B, seg: BusyPage];
AddNode[base: 1, pages: lf ← PagesPerRegion - 3];
myRegion.hole ← lf;
END
ELSE
BEGIN
FOR page DECREASING IN [0..PagesPerRegion) DO
IF PageThere[myRegion.basePage + page] THEN EXIT;
WriteMap[page: page, seg: BusyPage];
ENDLOOP;
AddNode[base: 1, pages: lf ← page];
myRegion.hole ← lf;
END;
mapSegment ← LOOPHOLE[AllocateObject[SIZE[data segment SegmentDefs.Object]]];
mapSegment↑ ←
[busy: FALSE,
body: segment[
VMpage: myRegion.basePage, info: data[type: TableDS, pages: 1]]];
WriteMap[page: 0, seg: mapSegment];
RETURN[@myRegion]
END;
PageThere: PROCEDURE [page: CARDINAL] RETURNS [BOOLEAN] =
BEGIN
t: Map.Entry;
t ← Map.SETF[page, Map.Clean];
[] ← Map.SETF[page, t];
RETURN[t.flags # Map.VacantFlags];
END;
RETURN[Initialize[]];
END.....