.TITLE	ALLOC
;
; ROUTINES TO ALLOCATE CHECKPOINT SPACE FOR AN ACTIVE TASK.  MUST
; BE CALLED WITH THE ATL NODE ADDRESS OF THE TASK TO BE CHECKPOINTED
; IN R0 AND WITH CONTEXT SWITCHING INHIBITED.  THE ALGORITHM IS TAKEN
; FROM THE RSX-11D VERSION 6A EXECUTIVE.
;
; WRITTEN   AUGUST 1976   R B FRENCH   THE BOEING COMPANY
;
ALLOC:: MOV	R0,-(SP)    
	MOV	.CKPUD,R4	;;GET PUD ADDRESS OF CHECKPOINT DISK 
	BITB	#UF.RH,U.FB(R4) ;;IS THE HANDLER LOADED?  
	BEQ	10$		;;NO -- TAKE ERROR RETURN 
	MOV	A.TD(R0),R0	;;YES -- GET STD ADDRESS OF TASK   
	MOV	S.TZ(R0),R3	;;GET TASK SIZE    
	ASH	#CK.BF-3,R3	;;CONVERT SIZE TO # OF DISK BLOCKS REQUIRED,   
				;;INCLUDING BLOCKING FACTOR 
	INC	R3		;;ADD ONE FOR ROUNDING 
	MOV	.CKMBA,R0	;;SET UP REGISTERS FOR CALL TO '.ALLC'   
	MOV	.CKMEA,R1	 
	CMP	R0,R1		;;IS THERE A BITMAP SET UP  
	BEQ	10$		;;IF EQUAL NO SO EXIT 
;	  
	MOV	R0,R4		;;PUT MAP ADDRESS IN PAR FORMAT 
	ASH	#-6,R4	    
	ADD	#4,R4	 
	MOV	#406,-(SP)	;;MAP APR3 TO BITMAP    
	MOV	R4,-(SP)   
	JSR	PC,..SPD3	 
	CMP	(SP)+,(SP)+	;;CLEAN UP STACK   
	SUB	R0,R1		;;CHANGE ADDRESSES TO APR3  
	MOV	#60000,R0	 
	ADD	#60000,R1	 
	MOV	R0,R2		;;START ALLOCATION ATTEMPT FROM BEGINNING   
				;;OF CHECKPOINT BITMAP  
	JSR	PC,.ALLC	;;ALLOCATE THE BLOCKS 
	TST	R3		;;ALLOCATION OK?   
	BMI	10$		;;NO -- IT FAILED 
	ASH	#-CK.BF,R3	;;YES -- REMOVE BLOCKING FACTOR 
	MOV	.CKBLH,R2	;;GET DISK ADDRESS OF CHECKPOINT FILE    
	ADD	.CKBLO,R3	;;ADD LOW ORDER ADDRESS BITS TO FIRST    
				;;BLOCK ALLOCATED   
	ADC	R2		;;DOUBLE PRECISION ADD 
	MOV	(SP)+,R0	;;RESTORE R0   
	MOV	R2,A.IA(R0)	;;STORE DISK ADDRESS IN ATL NODE   
	MOV	R3,A.IA+2(R0)	 
	CLC			;;CLEAR CARRY FOR SUCCESSFUL RETURN  
	BR	20$	    
10$:	SEC			;;SET CARRY FOR ERROR RETURN 
	MOV	(SP)+,R0	;;RESTORE R0  
20$:	RTS	PC	    
	.PAGE	 
; THE FOLLOWING ROUTINES (.ALLC AND .SETC) WERE COPIED  
; VERBATUM FROM THE VERSION 6A EXECUTIVE.   
;	  
;	  
; RSX-11D GENERALIZED BITMAP ALLOCATE/DEALLOCATE ROUTINE    
;	  
;	  
; INPUT:    
;	  
; R0: BITMAP START ADDRESS (MUST BE EVEN)   
; R1: BITMAP END ADDRESS (MUST BE EVEN) 
; R2: LAST BYTE ALLOCATED FROM IN M 
; R3: NUMBER OF CONTIGUOUS BITS NEEDED   
;	  
;	  
;	  
; OUTPUT:	  
; R2: LAST BYTE ALLOCATED FROM IN MAP (UPDATED) 
; R3: 1ST BIT ALLOCATED IN MAP, OR -1 IF ALLOCATION FAILED  
;	  
;	  
;	  
; FIRST WE SEARCH FOR A CONTIGUOUS CHAIN OF BITS OF SUFFICIENT  
; LENGTH.  DURING THE SEARCH, THE REGISTERS AND STACK ARE USED  
; AS FOLLOWS;	  
;	  
;	  
; R0: TEMP   = CONTENTS OF CURRENT BYTE IN MAP  
; R1: WRAP   = DISTANCE FROM CURRENT BYTE TO END OF MAP IN WORDS    
; R2: BYTE   = POINTER TO CURRENT BYTE IN MAP   
; R3: LENGTH = NUMBER OF CONTIGUOUS BITS NEEDED 
; R4: COUNT  = NUMBER OF FREE BITS IN CHAIN SO FAR  
; R5: BITS   = NUMBER OF BITS LEFT TO EXAMINE IN CURRENT BYTE   
;	  
; (SP+2): DONE	= NUMBER OF WORDS TILL WHOLE MAP IS EXAMINED 
; (SP)	: START = BITMAP START ADDRES    
;	  
;	  
; REGISTER, STACK DEFINITIONS	  
;	  
	TEMP   = %0	   
	WRAP   = %1	   
	BYTE   = %2	   
	LENGTH = %3	   
	COUNT  = %4	   
	BITS   = %5	   
;	  
	DONE = 2   
;	  
;	  
;	  
.ALLC:	 
	CMPB	(R1)+,(R1)+	; STEP TO LAST BYTE IN MAP    
	MOV	R1,-(SP)	; ABOVE MADE IT LAST BYTE +2  
	SUB	R0,@SP		; LAST BYTE - 1ST BYTE = # BYTES IN MAP    
	ASR	@SP		; MAKE IT # OF WORDS = "DONE" 
	SUB	BYTE,WRAP	; LAST - CURRENT = DIST TILL WRAPARND    
	ASR	WRAP		; CONVERT TO WORDS   
	ADC	WRAP		; ROUND UP LOST BYTE 
	MOV	R0,-(SP)	; BEGIN OF BITMAP = "START"   
	MOVB	@BYTE,TEMP	; PICK UP FIRST BYTE TO EXAMINE    
	MOV	#9.,BITS	; EXAMINE WHOLE FIRST BYTE    
NOTCHN: CLR	COUNT		; NOT IN CHAIN -- ZERO # BITS IN CHN 
NXTBIT: DEC	BITS		; STEP TO NEXT BIT    
	BNE	GETBIT		; IF IN SAME BYTE GO GET IT    
NXTBYT: INC	BYTE		; STEP TO NEXT BYTE   
	BIT	#1,BYTE 	; IN NEW WORD ?   
	BNE	 GETBYT 	; NO-- GET THE BYTE   
NEWWRD: DEC	DONE(SP)	; ONE LESS WORD TILL FAILURE   
	BEQ	FAIL		; NO MORE WORDS -- FAILURE !!!   
	DEC	WRAP		; ONE LESS WORD TILL WRAP-AROUND 
	BNE	TSTWRD		; DON'T WRAP YET   
	MOV	(SP),BYTE	; WRAP NOW !!!   
	CLR	COUNT		; WRAP-AROUND BREAKS THE CHAIN  
TSTWRD: TST	@BYTE		; ANY FREE BITS IN THIS WORD ?   
	BNE	GETBYT		; YES -- GET A BYTE    
	CLR	COUNT		; NO -- BREAK THE CHAIN 
	TST	(BYTE)+ 	; AND STEP TO NEXT WORD   
	BR	NEWWRD		; AND TRY IT    
GETBYT: MOVB	@BYTE,TEMP	; GET BYTE -- ANY FREE BITS ?   
	BNE	FSTBIT		; YES -- START CHECKING THE BITS   
	CLR	COUNT		; NO -- BREAK THE CHAIN 
	BR	NXTBYT		; AND GO GET THE NEXT BYTE  
FSTBIT: MOV	#8.,BITS	; 1ST BIT IN A BYTE -- EIGHT TO DO 
GETBIT: RORB	TEMP		; CHECK BIT  
	BCC	NOTCHN		; ALLOCATED -- BREAK CHAIN & TRY NXT   
	INC	COUNT		; FREE -- INCREMENT CHAIN COUNT 
	CMP	COUNT,LENGTH	; CHAIN LONG ENOUGH YET ? 
	BNE	NXTBIT		; NO -- TRY NEXT BIT   
;	  
;	  
; OUR SEARCH HAS SUCCEEDED.  NOW WE SET UP FOR AND CALL THE BIT 
; STRING SETTING/CLEARING ROUTINE TO CLEAR THE CHAIN FOR US,SET THE 
; LAST BYTE ALLOCATED FROM, AND RETURN   
;	  
;	  
	MOV	BYTE,2(SP)	; SAVE LAST BYTE ALLOCATED FROM 
	SUB	(SP),BYTE	; GET DISPL OF LAST BYTE IN CHAIN    
	ASH	#3,BYTE 	; MAKE IT A BIT DIPLACEMENT   
	ADD	#9.,BYTE	; ABOVE + 9 - BITS LEFT IN LAST BYTE  
	SUB	BITS,BYTE	; = DISPL OF LAST BIT IN STRING +1   
	SUB	LENGTH,BYTE	; FIND 1ST BIT IN STRING   
	MOV	(SP)+,R0	; GET START ADRS OF MAP   
	CLR	R1		; SWITCH TO CLEAR THE BITS 
	MOV	R2,-(SP)	; SAVE 1ST BIT IN STRING  
	JSR	PC,.SETC	; ZAP THE WHOLE CHAIN 
	MOV	(SP)+,R3	; RETURN 1ST BIT ALLOCATED    
	MOV	(SP)+,R2	; RETURN LAST BYTE ALLOCATED FROM 
	RTS	PC	    
;	  
;	  
FAIL:	DEC	BYTE		; CURRENT BYTE POINTER IS ON NEXT NOT LAST BYTE 
	MOV	#-1,R3		; SEARCH FAILED !!!!!  
	CMP	(SP)+,(SP)+	; CLEAN STACK  
	RTS	PC	    
	.PAGE	 
; THIS IS THE BIT STRING SET/CLEAR SUBROUTINE.  
; IT IS CALLED BY BOTH "ALLOCATE" AND "DEALLOCATE.  
;	  
;	  
; INPUT:    
;	  
;R0: START ADRS OF BITMAP	  
;R1: 0 FOR "CLEAR", -1 FOR "SET"    
;R2: 1ST BIT IN STRING	 
;R3: LENGTH OF STRING	  
;	  
;	  
;	  
.SETC:	 
	MOV	R2,R5		; GET DISPL OF 1ST BIT IN STRING    
	ASH	#-4,R5		; GET DISPL OF 1ST WORD IN STRING  
	ASL	R5		; MAKE IT EVEN BYTE    
	ADD	R5,R0		; GET ADRS OF 1ST WORD IN STRING    
	BIC	#177760,R2	; GET DISPL OF 1ST BIT IN 1ST WORD  
	MOV	(R0),R4 	; GET 1ST WORD    
	NEG	R2		; WANT TO RIGHT SHIFT  
	ASHC	R2,R4		; MOVE LEADING BITS OF 1ST WRD INTO RESULT 
	MOV	R4,(R0) 	; SAVE IN CASE ONLY 1 WORD IN STRING  
	ADD	#16.,R2 	; COMPUTE # BITS LEFT IN 1ST WORD 
	BR	INIMSK		; 1ST TIME THRU MAY BE < 16 BITS  LEFT  
MSKLOP: MOV	#16.,R2 	; AFTER 1ST TIME ALWAYS 16. BITS LEFT IN WRD   
INIMSK: MOV	R1,R4		; GET MASK IN SHIFT REGISTER 
	CMP	R3,R2		; LAST WORD IN STRING ??    
	BGT	SHIFT		;   
	MOV	R3,-(SP)	; YES-- PUT -[# BITS IN WRD NOT IN STRING]    
	SUB	R2,(SP) 	; ON STACK FOR USE AFTER SHIFTING IN MS BITS BIT  
	MOV	R3,R2		; AND DO ONLY THE NUMBER LEFT IN STRING 
SHIFT:	NEG	R2		; RIGHT SHIFT    
	ASHC	R2,R4		; MOVE APPROPRIATE # MASK BITS INTO RESULT 
	ADD	R2,R3		; THAT MANY FEWER LEFT TO GO IN STRING  
	BEQ	LSTBIT		; AT LAST BIT IN STRING ?  
	MOV	R5,(R0)+	; NO-- SAVE THE WORD, STEP TO NEXT    
	BR	MSKLOP		; AND LOOP  
LSTBIT: MOV	(R0),R4 	; AT LAST BIT-- GET CURRENT WORD   
	ASH	R2,R4		; SKIP OVER ALL BITS OF WORD IN STRING  
	ASHC	(SP)+,R4	; MOVE IN THE TRAILING BITS  
	MOV	R5,(R0) 	; SAVE THE LAST WORD  
	RTS	PC	    
	.END