-- HyperRegion.Mesa  Edited by Sandman on October 8, 1980  4:05 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,
    SwapOutCodeSeg, SwapOutUnlocked, UpdateCodebases];

HyperRegion: PROGRAM [index: Region.Index] RETURNS [Region.Handle]
  IMPORTS InlineDefs, Map, ProcessDefs, SegmentDefs, SwapperOps
  EXPORTS NucleusOps, Region, SegmentDefs
  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];
	    SwapOutUnlocked[@s];
	    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];
	      IF ~s.write THEN SwapOutUnlocked[@s];
	      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: PUBLIC 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 SwapOutCodeSeg[@s] ELSE SwapOut[@s];
	  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.....