.TITLE RECLAIM ; JEFFREY KODOSKY ARL NOV75 ; ; SUBR: GARBAGE COLLECTOR ; ENTRY: NO ARGS ; EXIT: 1 ARG NIL ; ERRORS: NONE ; CALLS: GET, SEARCH PROPERTY LIST ; TIMER, COMPUTE ELAPSED TIME ; PRNT, OUTPUT AN ASCIZ STRING OF CHARACTERS ; FCO, F FORMAT CONVERSION FOR OUTPUT ; ICO, I FORMAT CONVERSION FOR OUTPUT ; R1,R2,R3 PRESERVED .GLOBL RECLAIM,ZRECLAIM,ASTART .GLOBL $ALIST,ENDLSP,FSTART,SSTART,FLIST .GLOBL GSW,STIME,APVAL,QTIMER,QPRNT .GLOBL QFCO,QICO,QGET RECLAIM:MOV R3,-(SP) ;SAVE REGISTERS MOV R2,-(SP) MOV R1,-(SP) MOV R5,R2 ;INIT DEQUE (SPACE BETWEEN R5,R4 STACK TOPS MOV R5,R3 ;GUARANTEED AT LEAST 1 WD) R2,R3 POINTERS ;R4,R5 DEQUE LIMITS MOV SSTART,(PC)+ ;LOWEST MEMORY LOCATION WHERE K1: .WORD 0 ;MARK SWEEP MUST START CLR R1 ;HANDLE NIL SPECIALLY MOV (R1)+,R0;MARK ITS CAR JSR PC,MARKI MOV @R1,R0 ;AND ITS CDR JSR PC,MARKI;BUT NOT ITS SPECIAL HEADER CELL MOV $ALIST,R0 JSR PC,MARKI;MARK THE ASSOCIATION LIST MOV ENDLSP,R1 ;MARK ALL ITEMS ON THE ARG STACK GC01: CMP R1,R5 BLOS GC02 ;JUMP WHEN ALL STACK ITEMS MARKED MOV -(R1),R0 JSR PC,MARKI BR GC01 GC02: MOV ASTART,R1 ;MARK ALL ARRAY ELEMENTS CLR -(SP) ;ARRAY SIZE COUNTER GC03: CMP FSTART,R1 BLOS 2$ ;JUMP WHEN ALL ARRAYS MARKED MOV (R1)+,@SP ;SAVE SIZE OF NEXT ARRAY ROR @SP 1$: DEC @SP ;NUMBER OF ELEMENTS TO MARK BEQ GC03 ;JUMP IF DONE WITH THIS ARRAY MOV (R1)+,R0;MARK NEXT ELEMENT JSR PC,MARKI BR 1$ 2$: TST (SP)+ ; AT THIS POINT ALL IMMEDIATELY ACCESSIBLE CELLS ARE MARKED ; THE REST ARE DEQUED. NOW CLEAN OUT THE DEQUE. GC04: CMP R2,R3 BEQ GC06 ;JUMP WHEN DEQUE IS EMPTY CMP R2,R5 ;POP NEXT CELL BLO .+4 MOV R4,R2 ;WRAP AROUND MOV (R2)+,R1 GC05: MOV (R1)+,R0;MARK ITS CAR JSR PC,MARKI MOV @R1,R0 ;AND ITS CDR JSR PC,MARKI BR GC04 ; AT THIS POINT THE DEQUE IS EMPTY, K1 POINTS TO THE LOWEST ; CELL WHERE THERE MIGHT BE A LEAD TO AN UNMARKED CELL GC06: MOV K1,R1 ;START SWEEPING ADD #4,K1 ;BUMP THE SWEEP POINTER 1$: CMP R1,SSTART BHIS 2$ ;JUMP IF SWEEPING COMPLETED BIT #1,@R1 BEQ GC06 ;IF CELL IS MARKED, SKIP IT BIT #2,@R1 ;IF ITS A FULL WORD DATA STRING (I.E. BNE GC06 ;STRING OR NUMBER) SKIP IT SINCE IT IS ;COMPLETELY MARKED BR GC05 ;ELSE RETURN TO MARK THE CAR AND CDR 2$: ; AT THIS POINT ALL CELLS TO BE SAVED HAVE BEEN MARKED (EXCEPT ; THE SPECIAL NIL HEADER) MOV FSTART,R0 ;POINT TO START OF FREE SPACE MOV #FLIST,R1 ;POINT TO FREE LIST CLR -(SP) ;RECLAIMED CELL COUNTER GC07: ASR @R0 ;IS CELL MARKED? BCC 1$ ;JUMP IF NOT ASL (R0)+ ;YES: UNMARK IT BR 2$ 1$: MOV R0,@R1 ;CHAIN UNMARKED CELLS TO FREE LIST CLR (R0)+ ;CLEAR CARS OF FREE LIST CELLS MOV R0,R1 ;POINT TO CDR OF CELL INC @SP ;ONE MORE CELL RECLAIMED 2$: TST (R0)+ ; BUMP TO CAR OF NEXT CELL CMP R0,SSTART ;ANY CELLS LEFT? BLO GC07 ;LOOP BACK IF SO CLR @R1 ;OTHERWISE TERMINATE FREE LIST MOV (SP)+,(PC)+ ;SAVE NUMBER OF CELLS RECLAIMED FREE: .WORD 0 INC (PC)+ ;INCREMENT GARBAGE COLLECTION COUNT GCCNT: .WORD 0 MOV SSTART,R1 SUB FSTART,R1 CLRB R1 SWAB R1 ;NUMBER OF FREE CELLS / 64. CMP FREE,R1 BGE GC08 MOV #WARN,R3;PRINT WARNING MESSAGE IF LESS THAN QPRNT ;1.5% SPACE RECOVERED GC08: MOV APVAL,-(R5) ;PRINT GC MESSAGE? MOV GSW,-(R5) QGET TST (R5)+ BEQ GC09 ;NO: JUST RETURN MOV #GCBUF2,-(SP) MOV #10.,-(SP) MOV #3,-(SP) CLR -(SP) MOV #STIME+4,R0 MOV -(R0),-(SP) MOV -(R0),-(SP) QTIMER ;GET ELAPSED TIME IN SECONDS QFCO ;CONVERT TO F10.3 MOV #GCBUF1,-(SP) MOV #6,-(SP) MOV GCCNT,-(SP) QICO ;COLLECTION NUMBER IN I6 FORMAT MOV #GCBUF3,-(SP) MOV #6,-(SP) MOV FREE,-(SP) QICO ;NUMBER OF FREE CELLS IN I6 MOV #GCBUF,R3 QPRNT ;PRINT THE MESSAGE GC09: MOV (SP)+,R1 ;RESTORE REGISTERS MOV (SP)+,R2 MOV (SP)+,R3 CLR -(R5) ;RETURN NIL JMP @-(R4) ; MARK ALL IMMEDIATELY ACCESSIBLE CELLS STARTING WITH CELL @R0 MOV @R0,R0 MARKI: BIC #3,R0 ;FORCE R0 TO CELL BOUNDARY BEQ MARKED ;NIL IS MARKED BY DEFINITION CMP R0,FSTART ;DON'T TRY TO MARK ANYTHING BLO MARKED ;OUTSIDE THE FREE SPACE AREA CMP R0,SSTART ;(PROTECTION FROM NON-LISP BHIS MARKED ;ARGUMENTS ON THE STACK) BIT #1,@R0 BNE MARKED ;DONE IF CELL IS MARKED ALREADY INC @R0 ;OTHERWISE MARK IT BIT #2,@R0 ;IF THIS IS A FULL WORD DATA STRING BNE MARKI-2 ;MARK THE WHOLE THING MOV R0,-(R2) ;ELSE DEQUE THE CELL TO HAVE CMP R2,R4 ;ITS CAR AND CDR MARKED LATER BHI .+4 MOV R5,R2 ;WRAP AROUND CMP R2,R3 BNE MARKED CMP K1,-(R3);IF DEQUE FILLS SAVE THE NEW SWEEP POINTER BLO 1$ MOV @R3,K1 1$: CMP R3,R4 BHI .+4 MOV R5,R3 ;WRAP AROUND MARKED: RTS PC .NLIST BEX GCBUF: .BYTE 15,12 .ASCII /GARBAGE COLLECTION NUMBER / GCBUF1: .BLKB 6 .ASCII / AT / GCBUF2: .BLKB 10. .ASCII / FREED / GCBUF3: .BLKB 6 .ASCII / CELLS/ .BYTE 15,12,0 WARN: .ASCIZ <15><12>/FREE SPACE IS CROWDED/<15><12> .EVEN .LIST BEX ZRECLAIM=.-RECLAIM .END .TITLE RECLAIM ; JEFFREY KODOSKY ARL NOV75 ; ; SUBR: GARBAGE COLLECTOR ; ENTRY: NO ARGS ; EXIT: 1 ARG NIL ; ERRORS: NONE .GLOBL RECLAIM,ZRECLAIM ; CALLS: GET, SEARCH PROPERTY LIST ; TIMER, COMPUTE ELAPSED TIME ; PRNT, OUTPUT AN ASCIZ STRING OF CHARACTERS ; FCO, F FORMAT CONVERSION FOR OUTPUT ; ICO, I FORMAT CONVERSION FOR OUTPUT ; R1,R2,R3 PRESERVED .GLOBL $ALIST,ENDLSP,FSTART,SSTART,FLIST .GLOBL GSW,STIME,APVAL,QTIMER,QPRNT .GLOBL QFCO,QICO,QGET RECLAIM:MOV R3,-(SP) ;SAVE REGISTERS MOV R2,-(SP) MOV R1,-(SP) MOV R5,R2 ;INIT DEQUE (SPACE BETWEEN R5,R4 STACK TOPS MOV R5,R3 ;GUARANTEED AT LEAST 1 WD) R2,R3 POINTERS ;R4,R5 DEQUE LIMITS MOV SSTART,(PC)+ ;LOWEST MEMORY LOCATION WHERE K1: .WORD 0 ;MARK SWEEP MUST START CLR R1 ;HANDLE NIL SPECIALLY MOV (R1)+,R0;MARK ITS CAR JSR PC,MARKI MOV @R1,R0 ;AND ITS CDR JSR PC,MARKI;BUT NOT ITS SPECIAL HEADER CELL MOV $ALIST,R0 JSR PC,MARKI;MARK THE ASSOCIATION LIST MOV ENDLSP,R1 ;MARK ALL ITEMS ON THE ARG STACK GC01: CMP R1,R5 BLOS GC02 ;JUMP WHEN ALL STACK ITEMS MARKED MOV -(R1),R0 JSR PC,MARKI BR GC01 GC02: MOV ASTART,R1 ;MARK ALL ARRAY ELEMENTS CLR -(SP) ;ARRAY SIZE COUNTER GC03: CMP FSTART,R1 BLOS 2$ ;JUMP WHEN ALL ARRAYS MARKED MOV (R1)+,@SP ;SAVE SIZE OF NEXT ARRAY ROR @SP 1$: DEC @SP ;NUMBER OF ELEMENTS TO MARK BEQ GC03 ;JUMP IF DONE WITH THIS ARRAY MOV (R1)+,R0;MARK NEXT ELEMENT JSR PC,MARKI BR 1$ 2$: TST (SP)+ ; AT THIS POINT ALL IMMEDIATELY ACCESSIBLE CELLS ARE MARKED ; THE REST ARE DEQUED. NOW CLEAN OUT THE DEQUE. GC04: CMP R2,R3 BEQ GC06 ;JUMP WHEN DEQUE IS EMPTY CMP R2,R5 ;POP NEXT CELL BLO .+4 MOV R4,R2 ;WRAP AROUND MOV (R2)+,R1 GC05: MOV (R1)+,R0;MARK ITS CAR JSR PC,MARKI MOV @R1,R0 ;AND ITS CDR JSR PC,MARKI BC GC04 ; AT THIS POINT THE DEQUE IS EMPTY, K1 POINTS TO THE LOWEST ; CELL WHERE THERE MIGHT BE A LEAD TO AN UNMARKED CELL GC06: MOV K1,R1 ;START SWEEPING ADD #4,K1 ;BUMP THE SWEEP POINTER 1$: CMP R1,SSTART BHIS 2$ ;JUMP IF SWEEPING COMPLETED BIT #1,@R1 BEQ GC06 ;IF CELL IS MARKED, SKIP IT BIT #2,@R1 ;IF ITS A FULL WORD DATA STRING (I.E. BNE GC06 ;STRING OR NUMBER) SKIP IT SINCE IT IS ;COMPLETELY MARKED BR GC05 ;ELSE RETURN TO MARK THE CAR AND CDR 2$: ; AT THIS POINT ALL CELLS TO BE SAVED HAVE BEEN MARKED (EXCEPT ; THE SPECIAL NIL HEADER) MOV FSTART,R0 ;POINT TO START OF FREE SPACE MOV #FLIST,R1 ;POINT TO FREE LIST CLR -(SP) ;RECLAIMED CELL COUNTER GC07: ASR @R0 ;IS CELL MARKED? BCC 1$ ;JUMP IF NOT ASL (R0)+ ;YES: UNMARK IT BR 2$ 1$: MOV R0,@R1 ;CHAIN UNMARKED CELLS TO FREE LIST CLR (R0)+ ;CLEAR CARS OF FREE LIST CELLS MOV R0,R1 ;POINT TO CDR OF CELL INC @SP ;ONE MORE CELL RECLAIMED 2$: TST (R0)+ ; BUMP TO CAR OF NEXT CELL CMP R0,SSTART ;ANY CELLS LEFT? BLO GC07 ;LOOP BACK IF SO CLR @R1 ;OTHERWISE TERMINATE FREE LIST MOV (SP)+,(PC)+ ;SAVE NUMBER OF CELLS RECLAIMED FREE: .WORD 0 INC (PC)+ ;INCREMENT GARBAGE COLLECTION COUNT GCCNT: .WORD 0 MOV SSTART,R1 SUB FSTART,R1 CLRB R1 SWAB R1 ;NUMBER OF FREE CELLS / 64. CMP FREE,R1 BGE GC08 MOV #WARN,R3;PRINT WARNING MESSAGE IF LESS THAN QPRNT ;1.5% SPACE RECOVERED GC08: MOV APVAL,-(R5) ;PRINT GC MESSAGE? MOV GSW,-(R5) QGET TST (R5)+ BEQ GC09 ;NO: JUST RETURN MOV #GCBUF2,-(SP) MOV #10.,-(SP) MOV #3,-(SP) CLR -(SP) MOV #STIME+4,R0 MOV -(R0),-(SP) MOV -(R0),-(SP) QTIMER ;GET ELAPSED TIME IN SECONDS QFCO ;CONVERT TO F10.3 MOV #GCBUF1,-(SP) MOV #6,-(SP) MOV GCCNT,-(SP) QICO ;COLLECTION NUMBER IN I6 FORMAT MOV #GCBUF3,-(SP) MOV #6,-(SP) MOV FREE,-(SP) QICO ;NUMBER OF FREE CELLS IN I6 MOV #GCBUF,R3 QPRNT ;PRINT THE MESSAGE GC09: MOV (SP)+,R1 ;RESTORE REGISTERS MOV (SP)+,R2 MOV (SP)+,R3 CLR -(R5) ;RETURN NIL JMP @-(R4) ; MARK ALL IMMEDIATELY ACCESSIBLE CELLS STARTING WITH CELL @R0 MOV @R0,R0 MARKI: BIC #3,R0 ;FORCE R0 TO CELL BOUNDARY BEQ MARKED ;NIL IS MARKED BY DEFINITION CMP R0,FSTART ;DON'T TRY TO MARK ANYTHING BLO MARKED ;OUTSIDE THE FREE SPACE AREA CMP R0,SSTART ;(PROTECTION FROM NON-LISP BHIS MARKED ;ARGUMENTS ON THE STACK) BIT #1,@R0 BNE MARKED ;DONE IF CELL IS MARKED ALREADY INC @R0 ;OTHERWISE MARK IT BIT #2,@R0 ;IF THIS IS A FULL WORD DATA STRING BNE MARKI-2 ;MARK THE WHOLE THING MOV R0,-(R2) ;ELSE DEQUE THE CELL TO HAVE CMP R2,R4 ;ITS CAR AND CDR MARKED LATER BHI .+4 MOV R5,R2 ;WRAP AROUND CMP R2,R3 BNE MARKED CMP K1,-(R3);IF DEQUE FILLS SAVE THE NEW SWEEP POINTER BLO 1$ MOV @R3,K1 1$: CMP R3,R4 BHI .+4 MOV R5,R3 ;WRAP AROUND MARKED: RTS PC .NLIST BEX GCBUF: .BYTE 15,12 .ASCII /GARBAGE COLLECTION NUMBER / GCBUF1: .BLKB 6 .ASCII / AT / GCBUF2: .BLKB 10. .ASCII / FREED / GCBUF3: .BLKB 6 .ASCII / CELLS/ .BYTE 15,12,0 WARN: .ASCIZ <15><12>/FREE SPACE IS CROWDED/<15><12> .EVEN .LIST BEX ZRECLAIM=.-RECLAIM .END