SMALC	X0004 - STORAGE MAP ALL	MACRO M1110  21-AUG-78 20:54  PAGE 3





      1	000000					$BEGIN	SMALC,0004,<STORAGE MAP ALLOCATION>

						.TITLE	SMALC	X0004 - STORAGE MAP ALLOCATION

						.IDENT	"X0004"

      2

      3					;

      4					; COPYRIGHT (C) 1976 BY DIGITAL EQUIPMENT CORPORATION,

      5					; MAYNARD, MASSACHUSETTS

      6					;

      7					; THIS SOFTWARE IS FURNISHED UNDER A LICENSE FOR USE ONLY ON A

      8					; SINGLE  COMPUTER  SYSTEM AND MAY BE COPIED ONLY WITH THE IN-

      9					; CLUSION OF THE ABOVE COPYRIGHT NOTICE.   THIS  SOFTWARE,  OR

     10					; ANY  OTHER  COPIES THEREOF, MAY NOT BE PROVIDED OR OTHERWISE

     11					; MADE AVAILABLE TO ANY OTHER PERSON EXCEPT FOR  USE  ON  SUCH

     12					; SYSTEM  AND TO ONE WHO AGREES TO THESE LICENSE TERMS.  TITLE

     13					; TO AND OWNERSHIP OF THE SOFTWARE SHALL AT ALL  TIMES  REMAIN

     14					; IN DIGITAL.

     15					;

     16					; THE INFORMATION IN THIS SOFTWARE IS SUBJECT TO CHANGE  WITH-

     17					; OUT  NOTICE  AND  SHOULD NOT BE CONSTRUED AS A COMMITMENT BY

     18					; DIGITAL EQUIPMENT CORPORATION.

     19					;

     20					; DIGITAL EQUIPMENT CORPORATION ASSUMES NO RESPONSIBILITY  FOR

     21					; THE USE OR RELIABILITY OF ITS SOFTWARE ON EQUIPMENT WHICH IS

     22					; NOT SUPPLIED BY DIGITAL.

     23					;

     24					; ANDREW C. GOLDSTEIN  20-AUG-76  1:24

     25					; PETER H. LIPMAN	25-FEB-74

     26					;

     27					; THIS ROUTINE IS CRIBBED ALMOST VERBATIM FROM THE STORAGE MAP

     28					; ALLOCATOR IN F11ACP.

     29					; "PLAGIARIZE! PLAGIARIZE! (BUT REMEMBER ALWAYS TO CALL IT, PLEASE,

     30					; RESEARCH.)" - N. I. LOBACHEVSKY.

     31					; CORRECTED 11-MAR-77 G.RITTENBURG  001 [SEELINE 60$ +1 ]

SMALC	X0004 - STORAGE MAP ALL	MACRO M1110  21-AUG-78 20:54  PAGE 4





     33					;+

     34					;

     35					; *** - .SMALC	STORAGE MAP ALLOCATION ROUTINE

     36					;

     37					; THIS ROUTINE ALLOCATES THE SPECIFIED NUMBER OF BLOCKS TO THE FILE.

     38					; IF A NONCONTIGUOUS ALLOCATION IS REQUESTED, THEN IT ALLOCATES

     39					; THE FIRST CHUNK OF BLOCKS IT FINDS LESS THAN OR EQUAL TO THE DESIRED NUMBER

     40					; OF BLOCKS.

     41					;

     42					; INPUTS:

     43					;

     44					;	R0,R1 = NUMBER OF BLOCKS TO ALLOCATE

     45					;	R4 = DEVICE TABLE ENTRY

     46					;	.SMCTL = ALLOCATION CONTROL BYTE

     47					;

     48					; OUTPUT:

     49					;

     50					;	C = 0 IF SUCCESSFUL

     51					;	C = 1 IF DEVICE FULL

     52					;	R0,R1 = COUNT OF ALLOCATED BLOCKS

     53					;	R2,R3 = LBN IF C = 0

     54					;	R5 ALTERED, R4 PRESERVED

     55					;

     56					; EFFECTS:

     57					;

     58					;	.SMBUF MAY CONTAIN A DIFFERENT STORAGE MAP BLOCK

     59					;

     60					;-

     61	000000				.SMALC::

     62	000000	005067 	000000G			CLR	.SM2BT		; ZERO BIGGEST CHUNK FOUND SO FAR

     63	000004	005067 	000002G			CLR	.SM2BT+2

     64	000010	010102 				MOV	R1,R2

     65	000012	010001 				MOV	R0,R1

     66	000014	016400 	000000G			MOV	V.CLF(R4),R0	; R0=STORAGE MAP CLUSTER FACTOR

     67	000020	004767 	000000G			CALL	$DDIV		; FORM R1,R2=NO. OF BITS DESIRED

     68	000024	005700 				TST	R0		; ROUND UP IF REMAINDER IS NOT ZERO

     69	000026	001403 				BEQ	10$

     70	000030	062702 	000001 			ADD	#1,R2

     71	000034	005501 				ADC	R1

     72	000036	010167 	000000G		10$:	MOV	R1,.SM1BT	; SAVE DESIRED NO. OF BITS

     73	000042	010267 	000002G			MOV	R2,.SM1BT+2

     74	000046	012701 	000000G			MOV	#.SMBUF,R1	; START AT FIRST WORD

     75	000052	012700 	000001 			MOV	#1,R0		; AND FIRST BIT

     76					;

     77					; CALCULATE THE BLOCK COUNT TO SCAN, ALLOWING A SCAN FROM THE CURRENT

     78					; VBN TO THE END, AND IF NECESSARY FROM VBN 1 TO THE END AGAIN.

     79					; THIS ALLOWS THE CONTIGUOUS ALLOCATION FROM THE CURRENT VBN -1 TO THE

     80					; END OF THE STORAGE BIT MAP IF THAT PROVES TO BE THE ONLY WAY TO

     81					; ALLOCATE THE DESIRED CONTIGUOUS CHUNK.

     82					;

     83	000056	016703 	000000G			MOV	.SMVBN,R3	; R3=CURRENT VIRTUAL BLOCK NO. IN MEMORY

     84	000062	005303 				DEC	R3		; IF VBN 1 IS IN MEMORY

     85	000064	001403 				BEQ	30$		; NEED ONLY TAKE ONE FULL SCAN

     86	000066	005403 				NEG	R3		; OTHERWISE CALCULATE BLOCKS LEFT TO END

     87	000070	066403 	000000G			ADD	V.SBSZ(R4),R3

     88	000074	066403 	000000G		30$:	ADD	V.SBSZ(R4),R3	; ADD THE STORAGE BIT MAP SIZE

     89	000100	010367 	000000G			MOV	R3,.SMCNT	; STORE BLOCK COUNT THAT MAY BE SCANNED

SMALC	X0004 - STORAGE MAP ALL	MACRO M1110  21-AUG-78 20:54  PAGE 4-1





     90					;

     91					; R0=BIT MASK, R1=BIT WORD ADDRESS SEARCH FOR A FREE BIT

     92					; FIRST SEARCH WORD BY WORD FOR SPEED

     93					;

     94	000104	005711 			40$:	TST	(R1)		; CHECK CURRENT WORD

     95	000106	001010 				BNE	70$		; BRANCH IF ANY BITS ARE FREE

     96	000110	020127 	000776G		50$:	CMP	R1,#.SMBUF+512.-2 ; CHECK FOR END OF BUFFER

     97	000114	103013 				BHIS	80$		; BRANCH IF YES

     98	000116	005721 				TST	(R1)+		; ADVANCE TO NEXT WORD

     99	000120	000771 				BR	40$		; AND LOOP

    100					;

    101					; ENTER HERE TO RESUME SCANNING AFTER CONTIGUOUS CHECK HAS FAILED

    102					;

    103	000122	005767 	000000G		60$:	TST	.SMCNT		; ALREADY TESTED THE LAST BLOCK OF BITS?

    104	000126	003406 				BLE	80$		; BRANCH IF YES

    105									;   001   ABOVE LINE WAS BLE 60$

    106					;

    107					; CHECK INDIVIDUAL BITS OF A WORD

    108					;

    109	000130	030011 			70$:	BIT	R0,(R1)		; IF THIS BIT AVAILABLE

    110	000132	001012 				BNE	90$		; BRANCH IF YES

    111	000134	006300 				ASL	R0		; MOVE TO NEXT BIT

    112	000136	103374 				BCC	70$		; AND TRY

    113	000140	006100 				ROL	R0		; CHECKED ALL BITS IN WORD - WRAP TO

    114	000142	000762 				BR	50$		; FIRST AND TRY NEXT WORD

    115

    116	000144	012700 	100000 		80$:	MOV	#100000,R0	; END OF BUFFER - SET LAST BIT

    117	000150	004767 	000000G			CALL	.SMNXB		; SET UP TO TEST NEXT BLOCK

    118	000154	103353 				BCC	40$		; BRANCH IF MORE BITS TO TEST

    119	000156					RETURN			; ALLOCATION FAILED - RETURN C SET

    120					;

    121					; FOUND FIRST FREE BIT, SCAN FOR DESIRED SIZE CHUNK

    122					;

    123	000160	012705 	000000G		90$:	MOV	#.SM1BT,R5

    124	000164	012502 				MOV	(R5)+,R2	; R2,R3=DESIRED BIT COUNT

    125	000166	012503 				MOV	(R5)+,R3

    126	000170	010025 				MOV	R0,(R5)+	; SAVE MASK WORD

    127	000172	010125 				MOV	R1,(R5)+	; AND BIT WORD ADDRESS

    128	000174	016715 	000000G			MOV	.SMVBN,(R5)	; AND CURRENT VBN IN CORE

    129	000200	010346 				MOV	R3,-(SP)	; SAVE DESIRED COUNT (LOW BITS)

    130	000202	010246 				MOV	R2,-(SP)	; AND HIGH BITS

    131					;

    132					; SCAN FOR DESIRED NO. OF BITS FREE STARTING AT BIT IN R0, WORD IN R1

    133					;

    134					; WRAP AROUND ALLOCATION IS PREVENTED BY THE FACT THAT LOGICAL BLOCK 0

    135					; IS ALLOCATED IN A FILES 11 STRUCTURE AS THE 1ST VBN OF THE INDEX FILE

    136					;

    137	000204	012705 	000000G			MOV	#.CKFRE,R5

    138	000210	004767 	000000G			CALL	.SMSCN

    139	000214	103030 				BCC	120$		; BRANCH IF FOUND SPACE

    140					;

    141					; CALCULATE SIZE OF CONTIGUOUS CHUNK FOUND ON TOP OF STACK

    142					;

    143	000216	160366 	000002 			SUB	R3,2(SP)

    144	000222	005616 				SBC	(SP)

    145	000224	160216 				SUB	R2,(SP)

    146	000226	132767 	000000G	000000G		BITB	#EX.AC1,.SMCTL	; IF NON CONTIGUOUS EXTEND, THEN ALL SET

SMALC	X0004 - STORAGE MAP ALL	MACRO M1110  21-AUG-78 20:54  PAGE 4-2





    147	000234	001420 				BEQ	120$		; NO. OF BITS ALLOCATED ON TOP OF STACK

    148					;

    149					; CONTIGUOUS EXTEND AND DIDN'T FIND ENOUGH SPACE, KEEP TRACK OF

    150					; BIGGEST CONTIGUOUS CHUNK FOUND.

    151					;

    152	000236	012705 	000000G			MOV	#.SM2BT,R5

    153	000242	012602 				MOV	(SP)+,R2	; R2,R3=SIZE OF CHUNK IN BITS

    154	000244	012603 				MOV	(SP)+,R3

    155	000246	020225 				CMP	R2,(R5)+	; IS IT LARGER THAN CURRENT LARGEST?

    156	000250	001001 				BNE	100$

    157	000252	020315 				CMP	R3,(R5)

    158	000254	101407 			100$:	BLOS	110$		; BRANCH IF NO

    159					;

    160					; SAVE THIS AS THE LARGEST AREA

    161					;

    162	000256	010315 				MOV	R3,(R5)

    163	000260	010245 				MOV	R2,-(R5)

    164	000262	012702 	000000G			MOV	#.SM1MK,R2

    165	000266	012245 				MOV	(R2)+,-(R5)	; SM1MK TO SM2MK

    166	000270	012245 				MOV	(R2)+,-(R5)	; SM1AD TO SM2AD

    167	000272	012245 				MOV	(R2)+,-(R5)	; SM1VB TO SM2VB

    168					;

    169					; R0=MASK WORD, R1=ADDRESS - TRY TO FIND A BIG ENOUGH PIECE

    170					;

    171	000274				110$:

    172	000274	000712 				BR	60$

    173					;

    174					; SUCCESSFUL ALLOCATION, NO. OF BITS ALLOCATED ON TOP OF STACK

    175					; 0(SP)=HIGH BITS OF COUNT, 2(SP)=LOW BITS.

    176					;

    177	000276	016467 	000000G	000000G	120$:	MOV	V.SBSZ(R4),.SMCNT ; DISABLE BLOCK COUNT LOGIC IN .SMNXT

    178	000304	016703 	000000G			MOV	.SM1VB,R3	; R3=VBN FOR 1ST BIT

    179	000310	004767 	000000G			CALL	.SMRVB		; MAKE SURE STARTING BIT MAP BLOCK IS IN

    180	000314	011602 				MOV	(SP),R2		; R2,R3=NO. OF BITS

    181	000316	016603 	000002 			MOV	2(SP),R3

    182	000322	016700 	000000G			MOV	.SM1MK,R0	; R0=STARTING MASK WORD

    183	000326	016701 	000000G			MOV	.SM1AD,R1	; R1=STARTING WORD ADDRESS

    184	000332	012705 	000000G			MOV	#.ALOBT,R5	; ALLOCATE THE BITS FOUND

    185	000336	004767 	000000G			CALL	.SMSCN

    186					;

    187					; CALCULATE NO. OF BLOCKS ALLOCATED AND STARTING LBN,

    188					;

    189	000342	016400 	000000G		130$:	MOV	V.CLF(R4),R0	; R0=CLUSTER FACTOR

    190	000346	012602 				MOV	(SP)+,R2	; R2,R3=BIT COUNT ALLOCATED

    191	000350	012603 				MOV	(SP)+,R3

    192	000352	004767 	000000G			CALL	$DMUL		; CALCULATE R0,R1=NO. OF BLOCKS

    193	000356	010067 	000000G			MOV	R0,.SM1BT	; STORE NO. OF BLOCK ALLOCATED

    194	000362	010167 	000002G			MOV	R1,.SM1BT+2

    195					;

    196					; CALCULATE LOGICAL BLOCK NUMBER

    197					;

    198	000366	016701 	000000G			MOV	.SM1AD,R1

    199	000372	162701 	000000G			SUB	#.SMBUF,R1	; R1=BYTE NO. IN BUFFER

    200	000376	006301 				ASL	R1		; CALCULATE R1=BITS UP TO THE MARKED WORD

    201	000400	006301 				ASL	R1

    202	000402	006301 				ASL	R1

    203	000404	016702 	000000G			MOV	.SM1MK,R2	; R2=MASK WORD

SMALC	X0004 - STORAGE MAP ALL	MACRO M1110  21-AUG-78 20:54  PAGE 4-3





    204	000410	000241 				CLC

    205	000412	006002 			140$:	ROR	R2		; SHIFT MASK BIT

    206	000414	103402 				BCS	150$		; IF C=1, MASK=0

    207	000416	005201 				INC	R1		; COUNT THE BITS

    208	000420	000774 				BR	140$

    209	000422	010103 			150$:	MOV	R1,R3		; BIT NUMBER IN THIS BLOCK, R2=0

    210	000424	016700 	000000G			MOV	.SM1VB,R0	; VBN OF BIT MAP BLOCK (STARTS AT 1)

    211	000430	000403 				BR	170$

    212	000432	062703 	010000 		160$:	ADD	#512.*8.,R3	; ADD NO. OF BITS  PER BLOCK

    213	000436	005502 				ADC	R2

    214	000440				170$:	SOB	R0,160$		; FOR EACH VBN UP TO THIS ONE

    215	000444	016400 	000000G			MOV	V.CLF(R4),R0	; R0=CLUSTER FACTOR

    216	000450	004767 	000000G			CALL	$DMUL		; FORM LBN IN R0,R1, RETURN C=0

    217	000454	010103 				MOV	R1,R3		; MOVE LBN TO R2,R3

    218	000456	010002 				MOV	R0,R2

    219	000460	016700 	000000G			MOV	.SM1BT,R0	; GET COUNT IN R0,R1

    220	000464	016701 	000002G			MOV	.SM1BT+2,R1

    221	000470					RETURN

    222

    223

    224

    225		000001 				.END

SMALC	X0004 - STORAGE MAP ALL	MACRO M1110  21-AUG-78 20:54  PAGE 4-4

SYMBOL TABLE



EX.AC1= ****** GX	$DMUL = ****** GX	$SUPMC= 000043   	.SMCNT= ****** GX	.SM1AD= ****** GX

IIII  = 177777   	$EF$  = 000000   	$T    = 000000   	.SMCTL= ****** GX	.SM1BT= ****** GX

V.CLF = ****** GX	$E$   = 000001   	.ALOBT= ****** GX	.SMNXB= ****** GX	.SM1MK= ****** GX

V.SBSZ= ****** GX	$L    = 000000   	.CKFRE= ****** GX	.SMRVB= ****** GX	.SM1VB= ****** GX

$DDIV = ****** GX	$L$   = 000000   	.SMALC  000000RG 	.SMSCN= ****** GX	.SM2BT= ****** GX

$DIDDO= 000000   	$R    = 177777   	.SMBUF= ****** GX	.SMVBN= ****** GX



. ABS.	000000	   000

      	000472	   001

ERRORS DETECTED:  0



VIRTUAL MEMORY USED:  11309 WORDS  ( 45 PAGES)

DYNAMIC MEMORY:  12276 WORDS  ( 47 PAGES)

ELAPSED TIME:  00:00:24

EXE$:SMALC,LIS$:SMALC/-SP=SRC$:SMAC/PA:1,DSCPRE,SMALC

