Enter your search terms Submit search form
	Web pdp-10.trailing-edge.com

TITLE	QSRMEM -- Memory Manager for QUASAR
SUBTTL	Chuck O'Toole	12 Nov 76

;***Copyright (C) 1974, 1975, 1976, 1977, Digital Equipment Corp., Maynard, MA.***

	SEARCH	QSRMAC		;PARAMETER FILE

	PROLOGUE(QSRMEM)	;GENERATE THE NECESSARY SYMBOLS
COMMENT\

	Entry points found in QSRMEM

M$INIT	Initialization entry point
M$ACQP	Acquire a page from the page map
M$RELP	Return page 'AP' to the page map
M$IPSN	Notification that IPCF send of page 'AP' is about to occur
M$NXPG	Get a non-existant page for an IPCF receive
M$IPRC	Notification that IPCF receive of a page has occurred
M$IPRM	Make room for IPCF page we couldn't fit in core
M$GCOL	A "Preventive" Garbage Collector for the Top Level
M$GFRE	Get a cell from the free list for queue 'H'
M$PFRE	Put cell 'AP' back on the free list for queue 'H'
M$RFRE	Remove cell 'AP' from the queue 'H' and return it to the free list
M$DLNK	Remove cell 'AP' from the queue 'H'
M$LINK	Link cell 'AP' into the queue 'H' before entry 'E'
M$ELNK	Link cell 'AP' at the end of the queue 'H'
M$FLNK	Link cell 'AP' at the front of the queue 'H'
M$MOVE	Move cell 'AP' from queue 'H' to queue 'S1'
M$PCNT	Determine whether 'S1' pages can be acquired

	STOPCDs found in QSRMEM

ASE	ADDRESSING SPACE EXHAUSTED
BPN	BAD PAGE NUMBER
CCC	CELL COUNTS CONFUSED
CCP	CANNOT CREATE PAGE
CGA	CANNOT GIVE ACCESS TO PAGE
CRC	CANNOT REDUCE CORE
FCE	FREE COUNT EXCEEDS FREINI
FCN	FREE COUNT NEGATIVE
MDL	MOVING DIFFERENT LEVEL
NTS	NOTHING TO SWAP OUT
PAF	PAGE ACCESS CHECK FAILED
PDF	PAGE DESTROY FAILED
PIF	PAGE IN FAILURE
PLL	PAGE LINK LOST
POF	PAGE OUT FAILURE
QSZ	QUEUE SIZE ZERO
RFP	RELEASING FREE PAGE
RNP	RECEIVED NON-EXISTANT PAGE
UPF	UNKNOWN PAGE FAULT TYPE

\

	LVL==M		;LEVEL (CLASS) FOR FREE SPACE
	LVLMAX==1	;MAXIMUM LEVEL.  ( 0 = IPCF, 1 = ANYTHING ELSE )

; FOLLOWING SYMBOLS REFERENCE "LVLTAB(LVL)"

	LVLNFC==777B35	; ORIGINAL FREE COUNT PER PAGE THIS CLASS
	LVLSIZ==777B26	; SIZE OF A QUEUE ENTRY THIS CLASS
	LVLFPG==777B17	; FIRST PAGE IN THE CHAIN FOR THIS CLASS
	LVLXXX==777B8	; UNUSED


	PADING==5	;NUMBER OF PAGES TO LEAVE FREE FOR EMERGENCIES

SUBTTL	Initialization Entry Point

;CALLED BY QUASAR AT FIRST START-UP TO INITIALIZE THE MEMORY MANAGER

	INTERN	M$INIT

M$INIT:	PUSHJ	P,.SAVE1##		;SAVE P1
	PUSHJ	P,I$MFFP##		;GET FIRST FREE PAGE
	MOVEM	S1,PAGSTA		;STORE FOR PAGE SEARCHING LOOPS
	MOVEI	S2,^D512		;NOW COMPUTE THE REMAINING ADDRESS SPACE
	SUB	S2,S1			;OFFSET FOR CODE
	MOVEM	S2,FREPGS		;SAVE FOR M$NXPG CHECK
	MOVEM	S2,FREINI		;SAVE INITIAL VALUE FOR CHECKS
	ZERO	ZERLOC			;START WITH A CLEAR PAGE MAP
	MOVE	S1,[ZERLOC,,ZERLOC+1]	;SET UP FOR THE BLT
	BLT	S1,ZERLAS		;CLEAR THE WHOLE THING

IFN FTUUOS,<	;TOPS10 INITIALIZATION
	MOVE	S1,[PFHEND,,PFHBGN]	;PAGE FAULT HANDLER POINTERS
	MOVE	S2,PFHBGN		;TOUCH THE FIRST LOCATION AND THE LAST
	MOVE	S2,PFHEND		;TO GUARANTEE PFH IS IN CORE
	MOVEM	S1,.JBPFH##		;NOW SET UP OUR OWN HANDLER
	MOVE	S1,[.STTVM,,0]		;SET VIRTUAL TIME TRAP = NONE
	SETUUO	S1,			;SET TO NOT GIVE TIMER TRAPS
	  JFCL				;OH WELL!!
	MOVE	AP,PAGSTA		;GET THE STARTING PAGE NUMBER
	DECR	AP			;IT GETS AOS'ED LATER
	MOVEM	AP,SWPSTA		;START OF THE SWAPPING TABLE
	PG2ADR	AP			;CONVERT TO ADDRESS
	MOVEI	AP,777(AP)		;LAST LOCATION WE KNOW ABOUT
	CORE	AP,			;DON'T CARE ABOUT ANYTHING ELSE
	  STOPCD(CRC,FATAL)		;++CANNOT REDUCE CORE
>  ;END OF IFN FTUUOS

	MOVEI	H,TBLHDR##		;START OF THE QUEUE HEADERS
	MOVEI	P1,NQUEUE##		;AND THE NUMBER OF THEM
INIT.1:	PUSHJ	P,SETLVL		;SET UP CLASS FOR THIS QUEUE
	LOAD	S1,.QHPAG(H),QH.SIZ	;SIZE OF AN ENTRY IN THIS QUEUE
	JUMPN	LVL,INIT.2		;JUMP IF NOT AN IPCF QUEUE (=0)
	ADD	S1,G$MPS##		;ADD IN MAXIMUM PACKET SIZE
	STORE	S1,.QHPAG(H),QH.SIZ	;UPDATE QUEUE SIZE
INIT.2:	LOAD	S2,LVLTBL(LVL),LVLSIZ	;CURRENT SIZE IN THIS LEVEL
	CAMGE	S2,S1			;THIS QUEUE LARGER THAN CURRENT
	  MOVE	S2,S1			;YES, GET S2 = LARGEST SIZE SO FAR
	STORE	S2,LVLTBL(LVL),LVLSIZ	;REMEMBER LARGEST IN CLASS
	SKIPN	S2			;ERROR CHECK IT NOW
	  STOPCD(QSZ,FATAL)		;++QUEUE SIZE ZERO
	MOVEI	S1,777			;FREE WORDS PER PAGE
	IDIVI	S1,(S2)			;COMPUTE FREE CELLS PER PAGE
	STORE	S1,LVLTBL(LVL),LVLNFC	;REMEMBER FOR FREE SPACE ROUTINES
	MOVEI	H,QHSIZE(H)		;STEP TO NEXT QUEUE HEADER
	SOJG	P1,INIT.1		;GET ALL QUEUES
	POPJ	P,			;AND RETURN

SUBTTL	Free Space Management Subroutines

;ROUTINE TO GET A FREE CELL FOR A QUEUE
;CALL	H = QUEUE HEADER POINTER
;	PUSHJ	P,M$GFRE
;	  RETURNS AP = CELL ADDRESS
;DESTROYS S1,S2
;CALLS M$ACQP, BLDFRE

	INTERN	M$GFRE

M$GFRE:	SAVE	LVL			;SAVE CALLERS
	PUSHJ	P,SETLVL		;SET UP QUEUE CLASS
	SKIPN	LVL			;IPCF TYPE (=0)
	  PUSHJ	P,I$NOIN##		;YES, TURN OFF IPCF INTERRUPTS
	SKIPN	LVFCNT(LVL)		;ANY FREE CELLS LEFT FOR LEVEL?
	JRST	GFRE.3			;NO, GET A PAGE WORTH
	LOAD	AP,LVLTBL(LVL),LVLFPG	;GET FIRST PAGE IN THE CHAIN
	ZERO	S2			;CLEAR IN CASE NO FREE SPACE
GFRE.1:	LOAD	S1,PAGTBL(AP),PT.CNT	;CELLS REMAINING IN THIS PAGE
	JUMPE	S1,GFRE.2		;THIS PAGE IS FULL, TRY THE NEXT
	TRNE	S2,-1			;IS THIS THE FIRST PAGE WE'VE LOOKED AT
	 CAIGE	S1,(S2)			;NO, USE THE ONE WITH THE LEAST FREE SPACE
	  SKIPA				;THIS ONE IS BETTER (OR THE FIRST)
	   JRST	GFRE.2			;SKIP THIS PAGE
	HRLI	S2,(AP)			;SAVE PAGE NUMBER OF THE BEST
	HRRI	S2,(S1)			;AND ITS COUNT
GFRE.2:	LOAD	AP,PAGTBL(AP),PT.LNK	;GET CHAIN TO THE NEXT PAGE
	JUMPN	AP,GFRE.1		;LOOK AT THE NEXT PAGE IF ANY
	HLRZ	AP,S2			;GET THE NUMBER OF THE BEST PAGE
	JUMPN	AP,GFRE.4		;THERE WAS ONE, TAKE A CELL
	STOPCD	(LCC,FATAL)		;++LEVEL COUNT CONFUSED
GFRE.3:	PUSHJ	P,M$ACQP		;ACQUIRE A FRESH PAGE
	PUSHJ	P,BLDFRE		;GENERATE THE FREE SPACE IN THIS NEW PAGE
GFRE.4:	DECR	PAGTBL(AP),PT.CNT	;DECREMENT THE FREE COUNT FOR THIS PAGE
	SOS	LVFCNT(LVL)		;AND TOTAL FREE SPACE IN THIS CLASS
	PG2ADR	AP			;CONVERT TO AN ADDRESS
	HRRZ	S1,(AP)			;GET THE CELL FROM THIS PAGE
	LOAD	S2,.QELNK(S1),QE.PTN	;FIND THE NEXT
	HRRM	S2,(AP)			;DISSOLVE THE LINK
	MOVEI	AP,(S1)			;RETURN CELL ADDRESS IN AP
	POPJ	P,			;AND RETURN

;ROUTINES TO RETURN A CELL TO THE CORRECT FREE LIST
;CALL	AP = CELL ADDRESS (MAY BE DESTROYED)
;	H  = QUEUE HEADER POINTER
;	PUSHJ	P,M$PFRE (M$RFRE IF ENTRY MUST BE DE-LINKED)
;DESTROYS S1,S2,AP,TEMP
;CALLS M$DLNK, M$RELP

	INTERN	M$PFRE,M$RFRE

M$RFRE:	PUSHJ	P,M$DLNK		;DE-LINK THIS ENTRY BEFORE RETURNING IT
M$PFRE:	SAVE	LVL			;SAVE CALLERS
	PUSHJ	P,SETLVL		;SET UP QUEUE CLASS
	SKIPN	LVL			;IPCF TYPE (=0)
	  PUSHJ	P,I$NOIN##		;YES, TURN OFF IPCF INTERRUPTS
	MOVEI	S1,(AP)			;COPY THE CELL ADDRESS
	ADR2PG	S1			;CONVERT TO A PAGE NUMBER
	EXCH	AP,S1			;SET UP FOR VALIDITY CHECKS
	PUSHJ	P,VALPAG		;SEE IF 'AP' IS A GOOD PAGE NUMBER
	EXCH	AP,S1			;OK, GET THEM BACK IN THE RIGHT ORDER
	INCR	PAGTBL(S1),PT.CNT	;BUMP FREE COUNT FOR THIS PAGE
	AOS	LVFCNT(LVL)		;AND TOTAL FOR THIS CLASS
	LOAD	TEMP,PAGTBL(S1),PT.CNT	;GET THE COUNT NOW
	PG2ADR	S1			;BACK TO THE ADDRESS OF THIS PAGE
	HRRZ	S2,(S1)			;GET THE LINK TO THE FIRST FREE IN THIS PAGE
	HRRM	AP,(S1)			;STORE THIS ENTRY AS THE FIRST NOW
	STORE	S2,.QELNK(AP),QE.PTN	;LINK THIS ENTRY TO THE NEXT
	LOAD	S2,LVLTBL(LVL),LVLNFC	;GET THE COUNT IF THIS PAGE IS EMPTY
	CAMGE	S2,LVFCNT(LVL)		;MORE THAN 1 PAGE WORTH OF FREE SPACE
	  SETOM	DOGCOL			;YES, GARBAGE COLLECTION WILL WIN
	CAIE	TEMP,(S2)		;IS IT EMPTY NOW
	  POPJ	P,			;NO, JUST RETURN
	ADR2PG	AP			;BACK TO A PAGE NUMBER
	ZERO	S2			;CLEAR IN CASE THIS IS THE FIRST PAGE
	LOAD	S1,LVLTBL(LVL),LVLFPG	;GET FIRST PAGE IN THE CHAIN
PFRE.1:	CAIN	AP,(S1)			;FIND THE PAGE THAT POINTS TO ME
	  JRST	PFRE.2			;THIS IS IT
	MOVE	S2,S1			;COPY THE PAGE NUMBER
	LOAD	S1,PAGTBL(S2),PT.LNK	;LINK TO THE NEXT PAGE IN THE CHAIN
	JUMPN	S1,PFRE.1		;LOOK AT THIS ONE
	STOPCD	(PLL,FATAL)		;++PAGE LINK LOST
PFRE.2:	LOAD	S1,PAGTBL(AP),PT.LNK	;GET WHERE I POINT TO
	JUMPE	S2,PFRE.3		;JUMP IF I AM THE FIRST
	STORE	S1,PAGTBL(S2),PT.LNK	;REMOVE ME FROM THE CHAIN
	JRST	PFRE.4			;ADJUST COUNTS AND RETURN PAGE
PFRE.3:	PJUMPE	S1,.POPJ##		;RETURN IF I AM THE ONLY
	STORE	S1,LVLTBL(LVL),LVLFPG	;THAT IS NOW THE FIRST
PFRE.4:	LOAD	S1,LVLTBL(LVL),LVLNFC	;GET A PAGE WORTH OF FREE SPACE
	MOVNS	S1			; - THAT
	ADDM	S1,LVFCNT(LVL)		;DECREMENT TOTAL FOR THIS CLASS
	PJRST	M$RELP			;RETURN THE PAGE AND RETURN

;THE GARBAGE COLLECTOR IS CALLED FROM THE TOP LEVEL AND IS "PREVENTIVE"
;	RATHER THAN "CORRECTIVE".  IT MUST NOT BE CALLED IN AN ATTEMPT
;	TO ACQUIRE MORE CORE IN CASE THERE IS NONE AVAILABLE SINCE THE
;	STATE OF QUEUES AND LISTS ARE UNCERTAIN AT THOSE TIMES.

	INTERN	M$GCOL

M$GCOL:	SKIPN	DOGCOL			;IS THERE ANYTHING TO COLLECT?
	POPJ	P,			;NO, JUST RETURN
	PUSHJ	P,I$NOIN##		;TURN OFF IPCF INTERRUPTS
	PUSHJ	P,.SAVE3##		;SAVE P1-P3
	$COUNT	(NGCC)			;COUNT GARBAGE COLLECTION CALLS
	MOVEI	P1,LVLMAX		;DRIVE LOOP FROM LVLMAX TO 0
GCOL.1:	MOVE	LVL,P1			;COPY CURRENT LEVEL NUMBER
	PUSHJ	P,CHKELM		;CHECK IF WE CAN ELIMINATE A PAGE
	JUMPE	S1,GCOL.4		;CAN'T, TRY THE NEXT LEVEL
	$COUNT	(NPGC)			;COUNT COLLECTED PAGES
	MOVEI	H,TBLHDR##		;THE START OF THE QUEUE HEADERS
	MOVEI	P2,NQUEUE##		;AND THE NUMBER OF QUEUES DEFINED
	MOVX	P3,PT.USE		;GET THE IN USE BIT FOR CHECKS
	MOVE	AP,S1			;COPY THE PAGE TO ELIMINATE
GCOL.2:	PUSHJ	P,SETLVL		;LEVEL OF THIS QUEUE
	SKIPE	.QHLNK(H)		;QUEUE EMPTY
	 CAME	LVL,P1			;NO, SAME CLASS AS FOR THIS PASS
	  JRST	GCOL.3			;EMPTY OR NOT SAME LEVEL, TRY NEXT QUEUE
	PUSHJ	P,DOELIM		;TRY TO ELIMINATE THE PAGE HERE
	TDNN	P3,PAGTBL(AP)		;PAGE GONE YET
	  JRST	GCOL.1			;YES, TRY FOR ANOTHER PAGE IN THIS CLASS
GCOL.3:	MOVEI	H,QHSIZE(H)		;BUMP TO THE NEXT QUEUE HEADER
	SOJG	P2,GCOL.2		;AND DO THAT ONE
	STOPCD(CCC,FATAL)		;++CELL COUNTS CONFUSED
GCOL.4:	SOJGE	P1,GCOL.1		;TRY THE NEXT CLASS (LEVEL)
	SETZM	DOGCOL			;WE'VE COLLECTED
	POPJ	P,			;THEN RETURN

;ROUTINES TO LINK AN ENTRY INTO A QUEUE
;CALL	AP = ENTRY TO LINK
;	H  = QUEUE HEADER POINTER
;	E  = SUCCESSOR OF THIS ENTRY (FOR ORDERING IF CALLING M$LINK)
;	PUSHJ	P,M$xxxx
;		WHERE xxxx IS
;			'LINK' TO LINK ENTRY BEFORE 'E'
;			'ELNK' TO LINK AT THE END OF THE QUEUE
;			'FLNK' TO LINK AT THE BEGINNING OF THE QUEUE
;DESTROYS S1

	INTERN	M$LINK,M$ELNK,M$FLNK

M$ELNK:	CAIN	H,HDRIPC##		;LINKING THE IPCF QUEUE
	  PUSHJ	P,I$NOIN##		;YES, TURN OFF IPCF INTERRUPTS
	LOAD	S1,.QHLNK(H),QH.PTL	;FIND THE LAST
	STORE	AP,.QHLNK(H),QH.PTL	;THIS IS NOW THE LAST
	STORE	S1,.QELNK(AP),QE.PTP	;POINT BACK AT THE OLD LAST
	ZERO	.QELNK(AP),QE.PTN	;LAST HAS NO NEXT
	JUMPE	S1,ELNK.1		;JUMP IF THIS IS THE FIRST
	STORE	AP,.QELNK(S1),QE.PTN	;LINK THE OLD LAST TO THIS ONE
	POPJ	P,			;AND RETURN
ELNK.1:	STORE	AP,.QHLNK(H),QH.PTF	;STORE AS FIRST IN QUEUE ALSO
	POPJ	P,			;AND RETURN

M$FLNK:	CAIN	H,HDRIPC##		;LINKING THE IPCF QUEUE
	  PUSHJ	P,I$NOIN##		;YES, TURN OFF IPCF INTERRUPTS
	LOAD	S1,.QHLNK(H),QH.PTF	;FIND THE FIRST
	STORE	AP,.QHLNK(H),QH.PTF	;THIS IS NOW THE FIRST
	STORE	S1,.QELNK(AP),QE.PTN	;POINT TO THE OLD FIRST
	ZERO	.QELNK(AP),QE.PTP	;FIRST HAS NO PREVIOUS
	JUMPE	S1,FLNK.1		;JUMP IF THIS IS THE LAST
	STORE	AP,.QELNK(S1),QE.PTP	;LINK THE OLD FIRST BACK TO THIS
	POPJ	P,			;AND RETURN
FLNK.1:	STORE	AP,.QHLNK(H),QH.PTL	;STORE THIS AS LAST IN QUEUE ALSO
	POPJ	P,			;AND RETURN

M$LINK:	JUMPE	E,M$ELNK		;USE THE SPECIAL CASE IF THIS IS TO BE THE LAST
	CAIN	H,HDRIPC##		;LINKING THE IPCF QUEUE
	  PUSHJ	P,I$NOIN##		;YES, TURN OFF IPCF INTERRUPTS
	LOAD	S1,.QELNK(E),QE.PTP	;LOAD SUCCESSORS PREVIOUS
	JUMPE	S1,M$FLNK		;JUMP IF THIS IS TO BE THE FIRST
	STORE	S1,.QELNK(AP),QE.PTP	;THAT IS MY PREVIOUS
	STORE	AP,.QELNK(S1),QE.PTN	;AND I AM ITS NEXT
	STORE	E,.QELNK(AP),QE.PTN	;POINT TO THE SUCESSOR
	STORE	AP,.QELNK(E),QE.PTP	;I AM ITS PREVIOUS
	POPJ	P,			;AND RETURN

;ROUTINE TO DISSOLVE THE LINKS OF AN ENTRY
;NORMALLY CALLED BEFORE THE CALL TO M$PFRE AND IS CALLED BY M$RFRE
;CALL	AP = CELL TO REMOVE
;	H  = QUEUE HEADER POINTER
;	PUSHJ	P,M$DLNK
;DESTROYS S1,S2

	INTERN	M$DLNK

M$DLNK:	CAIN	H,HDRIPC##		;DELINKING THE IPCF QUEUE
	  PUSHJ	P,I$NOIN##		;YES, TURN OFF IPCF INTERRUPTS
	LOAD	S1,.QELNK(AP),QE.PTP	;GET LINKS OF THE ENTRY TO BE REMOVED
	LOAD	S2,.QELNK(AP),QE.PTN	;S1 = PREVIOUS, S2 = SUCCESSOR
	JUMPE	S1,DLNK.1		;JUMP IF REMOVING THE FIRST
	JUMPE	S2,DLNK.3		;JUMP IF REMOVING THE LAST
	STORE	S1,.QELNK(S2),QE.PTP	;LINK THE REMAINING ENTRIES TOGETHER
	STORE	S2,.QELNK(S1),QE.PTN	;TO COMPLETELY DISSOLVE THE OLD LINKS
	POPJ	P,			;AND RETURN
DLNK.1:	JUMPE	S2,DLNK.2		;JUMP IF REMOVING THE ONLY
	STORE	S2,.QHLNK(H),QH.PTF	;STORE SUCCESSOR AS THE NEW FIRST
	ZERO	.QELNK(S2),QE.PTP	;AND CLEAR ITS BACKWARD LINK
	POPJ	P,			;AND RETURN
DLNK.2:	ZERO	.QHLNK(H)		;IF REMOVING THE ONLY, CLEAR THE HEADER
	POPJ	P,			;AND RETURN
DLNK.3:	STORE	S1,.QHLNK(H),QH.PTL	;STORE PREVIOUS AS NEW LAST
	ZERO	.QELNK(S1),QE.PTN	;AND CLEAR ITS FORWARD LINK
	POPJ	P,			;AND RETURN


;ROUTINE TO MOVE A CELL FROM ONE QUEUE TO ANOTHER (PROCESSING TO USE, ETC..)
;CALL	H  = CURRENT QUEUE
;	AP = THE CELL TO MOVE
;	S1 = NEW QUEUE
;	PUSHJ	P,M$MOVE
;RETURNS AP & H UPDATED TO REFLECT NEW CELL
;DESTROYS S1,S2

	INTERN	M$MOVE

M$MOVE:	SAVE	LVL			;SAVE CALLERS
	PUSH	P,S1			;SAVE NEW HEADER
	PUSHJ	P,M$DLNK		;REMOVE CELL FROM OLD QUEUE
	PUSHJ	P,SETLVL		;DETERMINE LEVEL (CLASS) OF OLD QUEUE
	MOVE	S1,LVL			;SAVE LEVEL OF OLD QUEUE
	POP	P,H			;NEW HEADER
	PUSHJ	P,SETLVL		;FIND LEVEL OF NEW QUEUE
	CAIE	S1,(LVL)		;MOVING ACROSS LEVELS
	  STOPCD(MDL,FATAL)		;++MOVING DIFFERENT LEVEL
	LOAD	S1,.QHPAG(H),QH.SCH	;BASE SCHEDULER VECTOR FOR NEW QUEUE
	PJUMPE	S1,M$ELNK		;IF NO VECTOR TACK IT TO THE END
	PJRST	SCHLNK(S1)		;LINK IT IN AND RETURN

;ROUTINE TO BUILD THE FREE LIST IN A PAGE
;NORMALLY CALLED AFTER THE RETURN FROM M$ACQP
;CALL	AP = THE NEWLY ACQUIRED PAGE NUMBER
;	H  = QUEUE HEADER POINTER
;	LVL= QUEUE CLASS (LEVEL)
;	PUSHJ	P,BLDFRE
;DESTROYS S1,S2

BLDFRE:	PUSHJ	P,.SAVE2##		;SAVE P1,P2
	LOAD	S1,LVLTBL(LVL),LVLFPG	;GET FIRST PAGE IN THE CHAIN
	STORE	AP,LVLTBL(LVL),LVLFPG	;START WITH THE NEW ONE ACQUIRED
	STORE	S1,PAGTBL(AP),PT.LNK	;AND LINK NEW ONE TO OLD FIRST
	MOVEI	S1,(AP)			;COPY THE PAGE NUMBER
	PG2ADR	S1			;MAKE AN ADDRESS FROM IT
	MOVEI	S1,1(S1)		;WORD 0 IS THE LINK FOR FUTURE FREE SPACE
	MOVEM	S1,-1(S1)		;STORE AS A LINK TO WORD 1
	LOAD	S2,LVLTBL(LVL),LVLSIZ	;GET SIZE OF AN ENTRY IN THIS CLASS
	LOAD	P1,LVLTBL(LVL),LVLNFC	;GET NUMBER OF FREE CELLS IN A PAGE
	ADDM	P1,LVFCNT(LVL)		;INCLUDE NEW PAGE IN THE TOTAL
	STORE	P1,PAGTBL(AP),PT.CNT	;STORE THE COUNT OF FREE CELLS IN THIS PAGE
	SOJE	P1,BLDF.2		;DECREMENT FOR LOOP, JUMP IF ONLY ONE FITS
	MOVEI	P2,(S1)			;START COMPUTATIONS THE NEXT IN THIS PAGE
BLDF.1:	ADDI	P2,(S2)			;P2 = NEXT ENTRY
	STORE	P2,.QELNK(S1),QE.PTN	;LINK OF THIS POINTS TO NEXT
	MOVEI	S1,(P2)			;NOW POINT TO NEXT ENTRY
	SOJG	P1,BLDF.1		;AND LOOP FOR ALL ENTRIES - 1
BLDF.2:	ZERO	.QELNK(S1),QE.PTN	;LAST LINKS TO NOWHERE
	POPJ	P,			;AND RETURN

;ROUTINE TO ESTABLISH THE QUEUE CLASS (LEVEL) FOR QUEUE 'H'
;CALL	H = THE QUEUE HEADER
;	SAVE	LVL
;	PUSHJ	P,SETLVL
;RETURNS LVL = THE QUEUE CLASS (CALLER MUST SAVE IT FIRST)

SETLVL:	LOAD	LVL,.QHTYP(H),QH.IPC	;GET 'IPCF' QUEUE BIT
	TRC	LVL,1			;FLIP SO 0 = IPCF, 1 = ANYTHING ELSE
	POPJ	P,			;AND RETURN

;ROUTINE TO CHECK IF GARBAGE COLLECTION WILL ACCOMPLISH ANYTHING
;CALL	 LVL= CURRENT QUEUE CLASS (LEVEL)
;RETURNS S1 = PAGE THAT CAN BE ELIMINATED OR 0 IF CANT ELIMINATE ANYTHING

;THE DEPENDENCE ON THE METHODS USED BY M$PFRE AND M$GFRE MUST BE NOTED.
;	IN THE DETERMINATION OF THE PAGE TO BE ELIMINATED, THE PAGE WITH THE
;	"MOST" AMOUNT OF FREE SPACE IS USED, SINCE M$GFRE USES THE PAGE WITH
;	THE "LEAST" AMOUNT.  IF MULTIPLE PAGES HAVE THE SAME AMOUNT, M$GFRE USES
;	THE FIRST IN THE CHAIN, THEREFORE, TO ELIMINATE ONE, PICK THE LAST ONE.
;	M$PFRE (M$RFRE) WILL M$RELP A PAGE WHEN IT BECOMES COMPLETELY EMPTY.

CHKELM:	PUSHJ	P,.SAVET##		;SAVE THE T REGS
	LOAD	T1,LVLTBL(LVL),LVLFPG	;GET FIRST PAGE IN THE CHAIN
	JUMPE	T1,.FALSE##		;RETURN 0 IF EMPTY
	SETZB	T2,T3			;FOR FINDING FREE SPACE AND TOTALS
CHKE.1:	LOAD	T4,PAGTBL(T1),PT.CNT	;COUNT OF FREE CELLS IN THIS PAGE
	CAIGE	T4,(T2)			;THIS HAVE THE MOST YET
	  JRST	CHKE.2			;EQUAL CASE MUST BE CONSISTANT WITH M$GFRE
	MOVEI	S1,(T1)			;REMEMBER "BEST" PAGE
	MOVEI	T2,(T4)			;AND ITS CELL COUNT
CHKE.2:	ADDI	T3,(T4)			;INCLUDE IN THE TOTAL FREE
	LOAD	T1,PAGTBL(T1),PT.LNK	;FIND THE NEXT IN THE CHAIN
	JUMPN	T1,CHKE.1		;KEEP GOING IF THERE'S ANOTHER
	JUMPE	T3,.FALSE##		;RETURN 0 IF NO FREE CELLS LEFT
	CAME	T3,LVFCNT(LVL)		;COMPUTED AND RUNNING TALLIES AGREE
	  STOPCD(FNA,FATAL)		;++FREE TALLIES DO NOT AGREE
	LOAD	T1,LVLTBL(LVL),LVLNFC	;NUMBER OF FREE CELLS PER PAGE
	CAMG	T3,T1			;MOVE THAN 1 PAGE OF FREE SPACE
	  JRST	.FALSE##		;NO, CANNOT REDUCE
	POPJ	P,			;YES, RETURN WITH S1 = THE PAGE NUMBER

;SUBROUTINE TO ELIMINATE A PAGE FOR THE GARBAGE COLLECTOR
;CALL AP = THE PAGE TO ELIMINATE (OUTPUT FROM CHKELM)
;     H  = THE QUEUE HEADER
;     LVL= THE QUEUE LEVEL(CLASS)

DOELIM:	PUSHJ	P,.SAVET##		;SAVE ALL THE T REGS
	SAVE	E			;AND E
	SAVE	AP			;AND THE PAGE NUMBER
	MOVE	T1,AP			;SAVE THE PAGE NUMBER
	LOAD	T2,LVLTBL(LVL),LVLSIZ	;GET SIZE OF AN ENTRY THIS CLASS
	LOAD	E,.QHLNK(H),QH.PTF	;FIND FIRST IN THIS QUEUE
DOEL.1:	JUMPE	E,.POPJ##		;RETURN IF AT END OF LIST
	MOVEI	T3,(E)			;COPY CELL ADDRESS
	ADR2PG	T3			;CONVERT TO A PAGE NUMBER
	CAIE	T3,(T1)			;PAGE TRYING TO ELIMINATE
	  JRST	DOEL.2			;NO, TRY ANOTHER
	PUSHJ	P,M$GFRE		;YES, GET A NEW FREE CELL
	HRLI	T3,(E)			;SOURCE IS OLD ENTRY
	HRRI	T3,(AP)			;DESTINATION IS NEW ONE
	MOVEI	T4,(AP)			;NOW FIND HOW MUCH TO MOVE
	ADDI	T4,-1(T2)		;AS NEW + LENGTH OF ENTRY - 1
	BLT	T3,(T4)			;MOVE THE ENTRY TO ANOTHER PAGE
	MOVEI	T3,(E)			;COPY CELL ADDRESS AGAIN
	LOAD	E,.QELNK(E),QE.PTN	;FIND THE NEXT NOW
	PUSHJ	P,M$LINK		;PUT NEW IN CORRECT ORDER
	MOVEI	AP,(T3)			;NOW GET OLD CELL ADDRESS
	PUSHJ	P,M$RFRE		;AND UNLINK AND RETURN IT
	MOVX	AP,PT.USE		;THE IN USE BIT
	TDNN	AP,PAGTBL(T1)		;DID THE PAGE GO AWAY AFTER THAT RETURN
	  POPJ	P,			;YES, HAVE ELIMINATED IT
	JRST	DOEL.1			;NO, TRY ANOTHER CELL
DOEL.2:	LOAD	E,.QELNK(E),QE.PTN	;LINK TO THE NEXT ENTRY
	JRST	DOEL.1			;AND TRY THAT ONE

SUBTTL	Page Management Subroutines

;ROUTINE TO ACQUIRE A FRESH PAGE FROM THE PAGE MAP
;CALL	PUSHJ	P,M$ACQP
;	  RETURNS AP = PAGE NUMBER
;DESTROYS S1
;CALLS FNDPAG, PGSOUT, PGSDES, ANYOUT

	INTERN	M$ACQP

M$ACQP:	PUSHJ	P,I$NOIN##		;TURN OFF IPCF INTERRUPTS
	PUSHJ	P,FNDPAG		;FIND THE BEST AVAILABLE PAGE
	SKIPN	AP			;SKIP IF ONE FOUND
	  STOPCD(ASE,FATAL)		;++ADDRESSING SPACE EXHAUSTED

IFN FTJSYS,<

ACQP.1:	MOVX	S1,PT.USE!PT.WRK!PT.ADR	;GET ALL THE BITS
	IORM	S1,PAGTBL(AP)		;INCLUDE THEM
	PJRST	REDUCE			;REDUCE COUNT OF FREE CORE AND RETURN

>  ;END OF IFN FTJSYS

IFN FTUUOS,<

ACQP.1:	PUSHJ	P,REDUCE		;REDUCE COUNT OF FREE PAGES
	MOVX	S1,PT.USE		;GET THE INUSE BIT
	IORB	S1,PAGTBL(AP)		;SET IN USE, GET THE OTHERS
	TXNE	S1,PT.ADR		;IS IT ADDRESSABLE
	  POPJ	P,			;YES, RETURN (MAY PAGE FAULT IT IN LATER)
	PUSHJ	P,.SAVE3##		;SAVE P1-P3
ACQP.2:	MOVEI	P3,(AP)			;ARGUMENT FOR CREATE A PAGE
	MOVEI	P2,1			;ONLY 1 ARGUMENT
	MOVE	P1,[.PAGCD,,P2]		;FUNCTION CREATE/DESTROY,,ARGUMENTS
	PAGE.	P1,			;TRY THE CREATE
	  JRST	ACQP.3			;ANALYZE THE ERROR
	MOVX	S1,PT.WRK!PT.ADR	;IN THE WORKING SET, ADDRESSABLE
	IORM	S1,PAGTBL(AP)		;INCLUDE THE FLAG
	POPJ	P,			;AND RETURN
ACQP.3:	PUSH	P,AP			;SAVE THE PAGE WE'RE TRYING TO CREATE
	CAIE	P1,PAGNS%		;OUT OF SWAPPING SPACE
	  JRST	ACQP.4			;NO, LOOK AGAIN
	MOVEI	AP,5			;TAKE A QUICK NAP FIRST
	SLEEP	AP,			;IN CASE SOME FREES UP
	PUSHJ	P,PGSDES		;FREE SOME SWAPPING SPACE
	POP	P,AP			;RESTORE AP
	JRST	ACQP.2			;AND RETRY THE CREATE
ACQP.4:	CAIE	P1,PAGLE%		;MY LIMIT EXCEEDED
	  STOPCD(CCP,FATAL)		;++CANNOT CREATE PAGE
	PUSHJ	P,ANYOUT		;SWAP OUT ANYTHING
	POP	P,AP			;RESTORE AP
	JRST	ACQP.2			;RETRY THE CREATE

>  ;END OF IFN FTUUOS

;ROUTINE TO ACQUIRE A FRESH (UNADDRESSABLE) PAGE FROM THE PAGE MAP FOR IPCF
;CALL	PUSHJ	P,M$NXPG
;	  RETURNS AP = THE PAGE NUMBER AVAILABLE FOR IPCF RECEIVE
;			0 IF NONE AVAILABLE (NO CORE AVB)
;		NORMALLY, A CALL TO M$IPRC FOLLOWS THE RECEIVE AND THE PAGE IS INCLUDED
;			IN FACT, THE CALL TO M$IPRC IS REQUIRED TO KEEP FREPGS STRAIGHT
;DESTROYS S1
;CALLS FNDPAG, PGSOUT, PGSDES

	INTERN	M$NXPG

M$NXPG:	PUSHJ	P,I$NOIN##		;TURN OFF IPCF INTERRUPTS
	MOVE	S1,FREPGS		;GET FREE CORE LEFT
	CAIL	S1,PADING		;INSURE IPCF WON'T FILL OUR SPACE
	  JRST	NXPG.1			;GO TRY TO GET ONE
NXPG.0:	ZERO	AP			;RETURN A ZERO
	POPJ	P,			;THAT WILL SHUT IT OFF

IFN FTJSYS,<			;TOPS20 WILL REPLACE ANY EXISTING PAGE WITH THE MESSAGE

NXPG.1:	PUSHJ	P,FNDPAG		;ESSENTUALLY DUPLICATE M$ACQP
	PJUMPE	AP,.POPJ##		;RETURN 0 IF CANT GET ONE NOW
	MOVX	S1,PT.USE		;SET THE TEMP STATE
	IORM	S1,PAGTBL(AP)		;OF INUSE BUT NOT ADDRESSABLE
	POPJ	P,			;AND RETURN

>  ;END OF IFN FTJSYS

IFN FTUUOS,<			;TOPS10 REQUIRES A NON-EXISTANT PAGE

NXPG.1:	PUSHJ	P,NXPG.3		;FIND A COMPLETELY MISSING PAGE
	JUMPN	AP,NXPG.2		;TAKE THIS ONE
	PUSHJ	P,.SAVE3##		;SAVE P1-P3
	PUSHJ	P,PGSDES		;DESTROY ALL I CAN
	PUSHJ	P,NXPG.3		;NOW TRY TO FIND ONE
	PJUMPE	AP,.POPJ##		;RETURN 0 IF CANT GET ONE NOW
NXPG.2:	MOVX	S1,PT.USE		;SET THE TEMP STATE
	IORM	S1,PAGTBL(AP)		;OF INUSE BUT NOT ADDRESSABLE
	POPJ	P,			;AND RETURN

NXPG.3:	MOVE	AP,PAGSTA		;START AT THE FIRST AVAILABLE PAGE
NXPG.4:	CAIL	AP,^D512		;END OF THE ADDRESSING SPACE
	  JRST	NXPG.0			;YES, RETURN A ZERO
	MOVE	S1,PAGTBL(AP)		;GET THE TABLE ENTRY
	TXNN	S1,PT.USE!PT.WRK!PT.ADR	;IS THIS PAGE THERE
	  POPJ	P,			;NO BITS MEANS NON-EXISTANT
	AOJA	AP,NXPG.4		;WELL, TRY THE NEXT

>  ;END OF IFN FTUUOS

;ROUTINE TO RETURN A PAGE TO THE PAGE MAP
;CALL	AP = PAGE NUMBER
;	PUSHJ	P,M$RELP
;DESTROYS S1

	INTERN	M$RELP

M$RELP:	PUSHJ	P,VALPAG		;CONSISTENCY CHECK 'AP'
	MOVE	S1,PAGTBL(AP)		;GET THE FLAGS
	TXZN	S1,PT.USE		;CLEAR IN USE
	  STOPCD(RFP,FATAL)		;++RELEASING FREE PAGE
	TXNE	S1,PT.ADR		;IS THIS THE ONE IPCF'ED AWAY
	  JRST	RELP.1			;NO, GO FIX THE COUNTS
	ZERO	PAGTBL(AP)		;CLEAR THE ENTRY
	POPJ	P,			;AND RETURN
RELP.1:	MOVEM	S1,PAGTBL(AP)		;STORE NEW SETTINGS
	TXNE	S1,PT.WRK		;THIS PAGE LEFT IN CORE
	  AOS	AVBPGS			;YES, COUNT IT
	PJRST	INCLUD			;BUMP FREE PAGE COUNT AND RETURN

;ROUTINE TO SET NOTIFICATION OF A PAGE BEING IPCF'ed FROM OUR ADDRESSING SPACE
;CALL	AP = PAGE NUMBER
;	PUSHJ	P,M$IPSN
;DESTORYS S1

	INTERN	M$IPSN

M$IPSN:	PUSHJ	P,VALPAG		;CONSISTENCY CHECK 'AP'
	MOVX	S1,PT.WRK!PT.ADR	;CLEAR IN THE WORKING SET, ADDRESSABLE
	ANDCAM	S1,PAGTBL(AP)		;SO THAT WE DON'T GET CONFUSED
	PJRST	INCLUD			;BUMP FREE PAGE COUNT AND RETURN

;ROUTINE TO INCLUDE A PAGE RECEIVED BY IPCF INTO OUR ADDRESSING SPACE
;CALL	AP = THE PAGE NUMBER
;	PUSHJ	P,M$IPRC
;DESTROYS S1,S2

	INTERN	M$IPRC

IFN FTUUOS,<	;NOW NEED TO KNOW IF THE PAGE IS IN THE WORKING SET

M$IPRC:	PUSHJ	P,VALPAG		;CONSISTENCY CHECK 'AP'
	MOVEI	S2,(AP)			;FOR PAGE 'AP'
	HRLI	S2,.PAGCA		;CHECK ITS ACCESS BITS
	PAGE.	S2,			;SEE IF THE PAGE IS SWAPPED OUT
	  STOPCD(PAF,FATAL)		;++PAGE ACCESS CHECK FAILED
	MOVX	S1,PT.WRK!PT.ADR	;IN THE WORKING SET, ADDRESSABLE
	TXNE	S2,PA.GNE		;PAGE DOESN'T EXIST
	  STOPCD(RNP,FATAL)		;++RECEIVED NON-EXISTANT PAGE
	TXNE	S2,PA.GPO		;IS IT PAGED OUT
	  TXZ	S1,PT.WRK		;YES, CLEAR IN THE WORKING SET
	IORM	S1,PAGTBL(AP)		;INCLUDE THE FLAG(S)
	PJRST	REDUCE			;REDUCE COUNT OF FREE PAGES AND RETURN

>  ;END OF IFN FTUUOS

IFN FTJSYS,<

M$IPRC:	PUSHJ	P,VALPAG		;CONSISTENCY CHECK 'AP'
	MOVX	S1,PT.WRK!PT.ADR	;IN THE WORKING SET, ADDRESSABLE
	IORM	S1,PAGTBL(AP)		;INCLUDE THE FLAGS
	PJRST	REDUCE			;REDUCE COUNT OF FREE PAGES AND RETURN

>  ;END OF IFN FTJSYS

;ROUTINE TO DETERMINE WHETHER A PARTICULAR NUMBER OF PAGES CAN BE
;	ACQUIRED.
;CALL	S1 = NUMBER OF PAGES
;	PUSHJ P,M$PCNT
;	  RETURN TRUE OR FALSE
;
;NOTE: UNLESS THE CALLER DISABLES INTERRUPTS THE NUMBER OF AVAILABLE
;	PAGES IS VERY VOLATILE.

	INTERN	M$PCNT

M$PCNT:	ADDI	S1,PADING		;INCLUDE BUILD IN PADING
	CAMLE	S1,FREPGS		;CAN WE GET IT?
	PJRST	.FALSE##		;NO, TELL HIM HE LOSES
	PJRST	.TRUE##			;YUP, WIN!!

;ROUTINE TO SEARCH THE PAGE MAP FOR THE BEST PAGE FOR M$ACQP TO USE

;CALL	PUSHJ P,FNDPAG
;	  RETURNS AP = THE PAGE OR 0 IF OUT OF ADDRESSING SPACE
;DESTROYS S1

FNDPAG:	MOVE	AP,PAGSTA		;FIRST AVAILABLE PAGE
FNDP.1:	CAIL	AP,^D512		;OFF THE END
	  JRST	FNDP.2			;YES, DIDN'T FIND ANY, RETURN 0
	MOVE	S1,PAGTBL(AP)		;GET THE TABLE ENTRY
	TXNE	S1,PT.USE		;THIS ONE IN USE
	  AOJA	AP,FNDP.1		;YES, DON'T EVEN BOTHER
	TXC	S1,PT.WRK!PT.ADR	;FLIP
	TXCN	S1,PT.WRK!PT.ADR	;BACK, P.S. IS IT INCORE AND FREE
	  JRST	FNDP.3			;CAN'T GET ANY BETTER THAN THAT
	SKIPN	AVBPGS			;WILL ANOTHER PASS FIND ANYTHING
	  POPJ	P,			;NO, TAKE THIS FREE PAGE NOW
	AOJA	AP,FNDP.1		;YES IT WILL, GO FIND IN CORE PAGE
FNDP.2:	TDZA	AP,AP			;NO PAGES, RETURN 0
FNDP.3:	SOS	AVBPGS			;DECREMENT COUNT OF IN CORE PAGES
	POPJ	P,			;AND RETURN


;CONSISTENCY CHECKS ON THE NUMBER OF FREE PAGES IN OUR ADDRESSING SPACE
;"REDUCE" DECREMENTS THE FREE PAGE COUNT , "INCLUD" ADDS A FREE PAGE
;
;INCLUD DESTROYS S1

REDUCE:	SOSGE	FREPGS			;DECREMENT COUNT OF FREE PAGES
	  STOPCD(FCN,FATAL)		;++FREE COUNT NEGATIVE
	POPJ	P,			;RETURN IF OK

INCLUD:	AOS	S1,FREPGS		;ADD A FREE PAGE
	CAMLE	S1,FREINI		;MORE THAN WE STARTED OUT WITH
	  STOPCD(FCE,FATAL)		;++FREE COUNT EXCEEDS FREINI
	POPJ	P,			;RETURN IF OK STILL

;CONSISTENCY CHECK ON 'AP', THE PAGE NUMBER ARGUMENT TO
;	M$RELP, M$IPSN, M$IPRC

VALPAG:	CAIG	AP,^D511		;OVER THE TOP OF THE WORLD
	 CAMGE	AP,PAGSTA		;OR UNDER THE INITIAL VALUE
	  STOPCD(BPN,FATAL)		;++BAD PAGE NUMBER
	POPJ	P,			;RETURN, 'AP' IS IN RANGE

SUBTTL	The Page Fault Handler

;THIS IS THE ROUTINE CALLED BY THE TOPS10 SYSTEM SO THAT A USER MAY PROCESS
;HIS OWN PAGE FAULTS.  .JBPFH CONTAINS THE STARTING ADDRESS OF THE ROUTINE
;AND IS CALLED WHEN EITHER A FAGE FAULT OCCURS OR THE .STTVM TIMER HAS EXPIRED

IFN FTUUOS,<	;THIS CODE EXISTS ONLY FOR THE TOPS10 MONITOR

PFHBGN:	JRST	PFHSTA			;ENTERED HERE
PFH.PC:	0				;PC AT TIME OF TRAP
PFH.PN:	0				;PAGE FAULT WORD
PFH.TI:	0				;VIRTUAL AGE OF THE PAGE FAULT HANDLER
PFH.RA:	0				;CURRENT PAGING RATE
	BLOCK	4			;ROOM FOR FUTURE EXPANSION

PFHSTA:	MOVEM	P,PFHS.P		;SAVE SOMEBODY'S P
	MOVE	P,[IOWD PF.PSZ,PF.PDL]	;GET MY OWN PDL
	PUSH	P,P1			;BEGIN TO SAVE SEVERAL REGISTERS
	PUSH	P,P2			;CAUSE I'M GOING TO CALL SUBROUTINES
	PUSH	P,P3			;FOR SWAPPING AND SEARCHING
	PUSH	P,AP			;AND THESE ARE THE ARGUMENTS
	LOAD	P2,PFH.PN,PF.HFC	;THE FAULT TYPE
	CAIG	P2,PFHDCT		;RANGE CHECK
	  JRST	PFHDSP(P2)		;DISPATCH THE FAULT
PFHDSP:	JRST	PFHILL			;PAGE FAULT CODE = 0 OR TOO BIG
	JRST	PFHGVA			;.PFHNA = 1 = NO ACCESS
	JRST	PFHSWI			;.PFHNI = 2 = NOT IN CORE
	JRST	PFHSWI			;.PFHUU = 3 = NOT IN CORE FOR UUO
	JRST	PFHXIT			;.PFHTI = 4 = IGNORE TIMER TRAPS
PFHDCT==.-PFHDSP-1			;DISPATCH LENGTH (0-n)

PFHILL:	STOPCD	(UPF,FATAL)		;++UNKNOWN PAGE FAULT TYPE

PFHSWI:	LOAD	P3,PFH.PN,PF.HPN	;GET THE PAGE THAT CAUSED THE FAULT
	MOVEI	P2,1			;ONLY 1 PAGE
	MOVE	P1,[.PAGIO,,P2]		;FUNCTION PAGE IO,,ARGUMENT BLOCK
	PAGE.	P1,			;SWAP IT IN
	  JRST	PFHSWF			;FAILED, SEE WHY
	MOVX	P1,PT.WRK		;THE WORKING SET BIT
	IORM	P1,PAGTBL(P3)		;PAGE IS NOW IN CORE
	JRST	PFHXIT			;DISMISS THE FAULT
PFHSWF:	CAIE	P1,PAGLE%		;IS MY CORE LIMIT EXCEEDED
	  STOPCD(PIF,FATAL)		;++PAGE IN FAILURE
	PUSHJ	P,ANYOUT		;SWAP OUT SOMETHING (ANYTHING)
	JRST	PFHSWI			;TRY THE SWAPIN NOW

;;;CODE IS CONTINUED ON THE NEXT PAGE AND STILL UNDER FTUUOS CONDITIONAL

;HERE TO GIVE ACCESS TO A PAGE (CAN ONLY HAPPEN IF LOADED VIA GET.SHR)

PFHGVA:	LOAD	P3,PFH.PN,PF.HPN	;GET THE PAGE NUMBER WE CAN'T ACCESS
	TXO	P3,1B0			;SET TO ALLOW ACCESS
	MOVEI	P2,1			;ONLY ONE ARG
	MOVE	P1,[.PAGAA,,P2]		;GIVE ACCESS,,ARGS
	PAGE.	P1,			;SET ACCESS ALLOWED ON THAT PAGE
	  STOPCD(CGA,FATAL)		;++CANNOT GIVE ACCESS TO PAGE
PFHXIT:	POP	P,AP			;RESTORE AP
	POP	P,P3			;...
	POP	P,P2			;...
	POP	P,P1			;...
	MOVE	P,PFHS.P		;RESTORE THE OLD AC P
	JRSTF	@PFH.PC			;DISMISS THE FAULT

PFHS.P:	BLOCK	1			;SAVED P
PF.PDL:	BLOCK	^D12			;PDL FOR USE IN THE PAGE FAULT HANDLER
PF.PSZ==.-PF.PDL			;SIZE OF THE LIST

;ROUTINE TO DESTROY AS MANY PAGES THAT ARE SWAPPED OUT OR UNUSED
;CALL	PUSHJ	P,PGSDES
;	RETURNS AFTER DESTROYING AS MANY AS POSSIBLE
;DESTORYS AP,P1-P3 WITHOUT SAVING

PGSDES:	MOVE	AP,PAGSTA		;THE FIRST AVAILABLE PAGE
PGSD.1:	CAIL	AP,^D512		;OFF THE END OF THE WORLD
	  POPJ	P,			;YES, RETURN
	MOVE	P1,PAGTBL(AP)		;GET THE TABLE ENTRY
	TXC	P1,PT.ADR		;NEED CHECK FOR BOTH SO FLIP
	TXNN	P1,PT.USE!PT.ADR	;USED OR NOT ADDRESSABEL
	  PUSHJ	P,DESTRY		;DESTROY THE PAGE (COULD BE PAGED OUT)
	AOJA	AP,PGSD.1		;AND CONTINUE LOOPING

DESTRY:	MOVEI	P3,(AP)			;WANT IT IN P3
	TXO	P3,1B0			;SET TO DESTROY
	MOVEI	P2,1			;1 ARGUMENT
	MOVE	P1,[.PAGCD,,P2]		;CREATE/DESTROY,,ARGUMENT
	PAGE.	P1,			;TRY TO DESTROY IT
	  STOPCD(PDF,FATAL)		;++PAGE DESTROY FAILED
	ZERO	P1			;CLEAR A REG
	EXCH	P1,PAGTBL(AP)		;CLEAR PAGE MAP ENTRY, GET FLAGS
	TXNE	P1,PT.WRK		;JUST WIPE OUT AN INCORE PAGE
	  SOS	AVBPGS			;YES, REDUCE COUNTERS ACCORDINGLY
	POPJ	P,			;RETURN


;;;CODE IS CONTINUED ON THE NEXT PAGE AND STILL UNDER FTUUOS CONDITIONAL

;ROUTINE TO SWAP OUT ANYTHING POSSIBLE SO THAT A PAGEIN CAN OCCUR
;CALL	PUSHJ	P,ANYOUT
;	RETURNS AFTER A PAGE HAS BEEN SUCCESSFULLY PAGED OUT
;DESTROYS AP, P1-P3 WITHOUT SAVING
;COULD EXIT THROUGH DESTRY

	INTERN	M$IPRM

M$IPRM:	PUSHJ	P,.SAVE3##		;SAVE P1-P3
	SAVE	AP			;AND AP AND FALL INTO ANYOUT
ANYOUT:	MOVE	AP,PAGSTA		;FIRST MAKE A PASS LOOKING FOR ANY FREE
ANYO.1:	PUSHJ	P,ANYO.4		;PAGES THAT CAN BE DESTROYED
	JUMPE	AP,ANYO.2		;NONE, PAGE SOMETHING OUT
	TXNE	P1,PT.USE		;IS THIS IN-CORE PAGE USED
	  AOJA	AP,ANYO.1		;YES, LOOK FOR ANOTHER
	PJRST	DESTRY			;NO, DESTROY IT NOW AN SAVE A SWAP
ANYO.2:	AOS	AP,SWPSTA		;START WHERE WE LEFT OFF
	PUSHJ	P,ANYO.4		;FIND A SWAPPED IN PAGE
	JUMPN	AP,ANYO.3		;SWAP IT OUT
	MOVE	AP,PAGSTA		;RE-START AT THE FIRST
	PUSHJ	P,ANYO.4		;TRY NOW
	JUMPN	AP,ANYO.3		;FOUND ONE, SWAP IT OUT
	STOPCD	(NTS,FATAL)		;++NOTHING TO SWAP OUT
ANYO.3:	MOVEM	AP,SWPSTA		;REMEMBER FOR LATER
	MOVEI	P3,(AP)			;COPY THE PAGE NUMBER
	TXO	P3,1B0			;SET TO SWAP OUT INSTEAD OF SWAP IN
	MOVEI	P2,1			;ONLY 1 PAGE FOR NOW
	MOVE	P1,[.PAGIO,,P2]		;FUNCTION SWAP,,ARGUMENT BLOCK
	PAGE.	P1,			;OUT IT GOES
	  STOPCD(POF,FATAL)		;++PAGE OUT FAILURE
	MOVX	P1,PT.WRK		;GET THE WORKING SET BIT
	ANDCAB	P1,PAGTBL(P3)		;NOT THERE ANY MORE, GET NEW FLAGS
	TXNN	P1,PT.USE		;WAS SOMEBODY USING IT
	  SOS	AVBPGS			;NO, REDUCE COUNT OF INCORE FREE PAGES
	POPJ	P,			;AND RETURN FOR ANY RETRIES

ANYO.4:	CAIL	AP,^D512		;OVER THE TOP
	  JRST	ANYO.5			;YES, RETURN A ZERO
	MOVE	P1,PAGTBL(AP)		;GET THE STATUS FLAGS
	TXNE	P1,PT.ADR		;IS IT ADDRESSABLE
	 TXNN	P1,PT.WRK		;YES, IS IT IN THE WORKING SET
	  AOJA	AP,ANYO.4		;TRY THE NEXT PAGE
	POPJ	P,			;YES, A CANDIDATE FOR SWAP OUT
ANYO.5:	ZERO	AP			;RETURN 0 IF NONE FOUND
	POPJ	P,			;RETURN

SWPSTA:	BLOCK	1			;PAGE NUMBER FOR START OF SWAP OUT SEARCH

PFHEND:		;THE LAST LOCATION WITHIN THE PAGE FAULT HANDLER


>  ;END OF IFN FTUUOS

SUBTTL	Constants and Other Things

	XLIST			;FORCED OUT LITERAL POOL HERE
	LIT
	LIST
	SALL

FREPGS:	BLOCK	1		;COUNT OF FREE PAGES LEFT IN ADDRESSING SPACE
FREINI:	BLOCK	1		;THE INITIAL VALUE OF FREPGS FOR CONSISTENCY CHECKS
PAGSTA:	BLOCK	1		;THE STARTING POINT FOR PAGSRC SEARCHES

ZERLOC:				; BEGIN BLOCK ZERO'ED AT INITIALIZATION

AVBPGS:	BLOCK	1		;COUNT OF INCORE PAGES THAT AREN'T USED
DOGCOL:	BLOCK	1		;-1 IF GARBAGE COLLECTION WILL DO ANY GOOD
LVLTBL:	BLOCK	LVLMAX+1	;LH = MAX ENTRY SIZE, RH = FIRST PAGE IN CHAIN
LVFCNT:	BLOCK	LVLMAX+1	;CURRENT FREE CELL COUNTS PER LEVEL(CLASS)
PAGTBL:: BLOCK	^D512		;THE PAGE MAP

ZERLAS==.-1			; END OF THE BLOCK ZERO'ED AT ONCE ONLY

	END