-- MDSRegion.Mesa  Edited by Sandman on August 18, 1980  10:30 AM
-- Copyright  Xerox Corporation 1979, 1980

DIRECTORY
  AllocDefs USING [SwappingProcedure, SwapStrategy],
  AltoDefs USING [PageCount, PageNumber, PageSize],
  ControlDefs USING [
    GFT, GlobalFrameHandle, NullGlobalFrame, PrefixHandle, PrefixHeader],
  InlineDefs USING [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 InlineDefs, Map, ProcessDefs, SegmentDefs
  EXPORTS AllocDefs, NucleusOps, SwapperOps, SegmentDefs
  SHARES SegmentDefs =PUBLIC

  BEGIN OPEN SegmentDefs, AltoDefs, SwapperOps, AllocDefs, Region;

  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 =>
	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 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 =>
	      BEGIN
	      base _ n.base;
	      n.back.fwd _ n.fwd;
	      n.fwd.back _ n.back;
	      EXIT;
	      END;
	    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 =>
	    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 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;
    status: PageStatus;
    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
      [segment, status] _ Status[rover];
      okay _ FALSE;
      SELECT (segment _ map[rover]) FROM
	BusyPage => inc _ 1;
	FreePage => {okay _ TRUE; inc _ 1};
	ENDCASE =>
	  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 _ InlineDefs.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
	BEGIN
	page _ n _ 0;
	IF pass = quit THEN BEGIN foundHole _ FALSE; EXIT END;
	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;
    base _ rover _ page + n;
    WHILE page < base DO
      SELECT (segment _ map[page]) FROM
	BusyPage, FreePage => page _ page + 1;
	ENDCASE =>
	  IF segment # NIL THEN {
	    relPage: Page = 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];
		  IF ~s.write THEN {
		    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;

  SwapOutUnlocked: PUBLIC PROCEDURE [seg: FileSegmentHandle] =
    BEGIN
    ProcessDefs.DisableInterrupts[];
    seg.swappedin _ FALSE;
    seg.file.swapcount _ seg.file.swapcount - 1;
    ProcessDefs.EnableInterrupts[];
    END;

  UpdateCodebases: PUBLIC PROCEDURE [seg: FileSegmentHandle] =
    BEGIN OPEN ControlDefs;
    lastUser, f: ControlDefs.GlobalFrameHandle;
    nUsers, i: CARDINAL;
    epbase: CARDINAL;
    segBase: PageNumber;
    vmpage: PageNumber;
    ProcessDefs.DisableInterrupts[];
    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*f.code.otherByte;
	  segBase _ seg.VMpage;
	  IF vmpage ~IN [segBase..segBase + seg.pages) THEN LOOP;
	  f.code.offset _ f.code.offset - AltoDefs.PageSize*segBase;
	  f.code.handle _ LOOPHOLE[seg];
	  f.code.out _ TRUE;
	  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.....