ASMB,Q,C NAM GETBF,7 92060-16102 REV. 1913 781006 * * ****************************************************************** * (C) COPYRIGHT HEWLETT-PACKARD COMPANY 1978. ALL RIGHTS RESERVED * NO PART OF THIS PROGRAM MAY BE PHOTOCOPIED, REPRODUCED, OR * TRANSLATED TO ANOTHER PROGRAM LANGUAGE WIOTH OUT THE PRIOR * WRITTEN CONSENT OF HEWLETT-PACKARD COMPANY. ******************************************************************* * * * SOURCE: 92067-18084 * RELOC: 92067-16084 * * *****************************************************************: EXT .ENTR,LIMEM,.MVW,UNMEM,UNM2,AVLM,ENDM ENT GETBF,CMPK SKP * * * ABSTRACT: * * THE MEMORY MANAGER USES A GARBAGE COLLECTION ALGORITH. THE * ALGORITHM ALLOCATES FROM THE TOP OF FREE MEMORY TO THE BOTTOM. * (TOP OF MEMORY IS CONSIDERED TO BE LOW MEMORY.) MEMORY IS * ONLY RETURNED TO THE HEAP ON TWO OCCASIONS. THE FIRST * OCCASION IS WHEN MEMORY IS COMPACTED AND ALL THE UNUSED BLOCKS ARE * SQUEEZED TO THE BOTTOM OF MEMORY. THE SECOND OCCASION IS WHEN A * BLOCK OF MEMORY CONTIGUOUS TO THE TOP OF THE HEAP IS RELEASED. * THIS CONTIGUOUS MEMORY IS GATHERED INTO THE HEAP. NOTE THAT WHEN * A MEMORY BLOCK IS RELEASED WHICH IS SANDWICHED BETWEEN TWO USED * BLOCKS, THE BLOCK IS LEFT UNUSED UNTIL MEMORY IS COMPACTED. * * SINCE BLOCKS OF MEMORY ARE MOVED ABOUT IN PHYSICAL MEMORY, POINTERS * TO THE MEMORY MUST BE TREATED IN A SPECIAL WAY. WHEN MEMORY IS * ALLOCATED, THE CALLER DEDICATEDS A WORD OF MEMORY AS A PRIMARY * BUFFER POINTER. THIS PRIMARY BUFFER POINTER IS THE ONLY POINTER * THAT IS UPDATED BY THE BUFFER MANAGER WHEN MEMORY IS COMPACTED. * THEREFORE, SINCE THE VALUE OF THE PRIMARY BUFFER POINTER MAY THE * BE MODIFIED AFTER A CALL TO GETBF, IT IS WISE TO HAVE ONLY * ONE COPY OF THE PRIMARY POINTER. THEREFORE ALL OTHER POINTERS * INTO THE BUFFER MUST BE RELATIVE TO THE PRIMARY POINTER. * * * * DESCRIPTION OF THE BUFFER * * * EACH BUFFER HAS TWO WORDS OF OVERHEAD. * * WORD 1 = THE SIZE OF THE BUFFER EXCLUDING THE OVERHEAD WORDS * WORD 2 = BACK POINTER TO THE PRIMARY POINTER * THIS WORD IS SOMETIMES REFERED TO AS THE BUFFER'S * PRIMARY POINTER. WHEN THE WORD IS ZERO THE BUFFER * HAS NO OWNER AND IS CONSIDERED UNUSED. * WORD 3-N = THE USER'S BUFFER * * * THIS MODULE CONTAINS THE SUBROUTINES TO GET MEMORY, AND TO * COMPACT MEMORY. MORE DETAILED DESCRIPTIONS PRECEED EACH MODULE. * * * * SKP * * * TITLE: GETBF * GET BUFFER * * ABSTRACT: * * GETBF VERIFIES THAT THE REQUEST FOR MEMORY IS LEGAL AND THAT * ENOUGH MEMORY EXISTS FOR THE NEW BUFFER. WHEN THERE IS NOT * ENOUGH MEMORY IN THE UNUSED-MEMORY BUFFER, GETBF CALLS THE * GARGAGE COLLECTION ROUTINE CALLED CMPK. WHEN THERE IS * NOT ENOUGH MEMORY AFTER CALLING CMPK, GETBF GENERATES AN ERROR. * OTHERWISE IT CALLS THE ROUTINE THAT SETS UP THE OVERHEAD FOR * THE BUFFER. THIS ROUTINE IS CALLED ALLOC. * * THERE MUST ALWAYS BE AN UNUSED-MEMORY BUFFER, EVEN IF THE * BUFFER CONTAINS NO USER BUFFER, (IE. WHEN THE SIZE OF THE * BUFFER IS ZERO). GETBF WILL NOT ALLOCATE A BUFFER WHEN THERE * IS NOT ALSO ROOM TO CREATE A NEW OVERHEAD BLOCK FOR THE UNUSED-MEMORY * BUFFER. * * GETBF MAINTAINS FOUR POINTERS: AVLM WHICH POINTS TO THE FIRST * WORD OF AVAILAVBLE MEMORY, ENDM WHICH POINTS TO THE LAST WORD * OF AVAILABLE MEMORY, AND UNMEM AND UNM2 WHICH POINT TO THE FIRST, * AND SECOND WORD OF THE UNUSED-MEMORY BUFFER'S OVERHEAD. * * GETBF AUTOMATICALLY GETS ALL THE MEMORY BETWEEN THE USER'S * PROGRAM AND THE END OF THE PARTITIAN WHENEVER UNMEM IS ZERO, * THUS ALLOWING AN ITELLIGENT USER TO SHARE MEMORY WITH THE BUFFER * MANAGER BY INTIALIZING THE FOUR RESERVED WORDS DESCRIBED ABOVE. * OTHERWISE, GETBF WILL INITIALIZE THEM. * * CALLING SEQUENCE: * * JSB GETBF * DEF *+4 * DEF (SIZE OF REQUESTED BUFFER) * DEF (WORD WHICH WILL BECOME THE PRIMARY POINTER) * DEF (ERROR RETURN WORD) * * EXIT: * * THE PRIMARY POINTER WILL CONTAIN THE ADDRESS OF THE USER * BUFFER. THE ADDRESS TO THIS DATA WORD IS STORED IN * THE SRECOND OVERHEAD WORD OF THE BUFFER. THIS WORD * WILL BE UPDATED WHENEVER MEMORY IS COMPACTED. * ALTHOUGH, THE USER IS UNAWARE OF THE OVERHEAD WORDS, * THE USER IS RESPONSIBLE FOR STAYING WITHIN THE * SIZE LIMITATIONS THAT WAS SPECIFIED. * * THE ERROR WORD WILL CONTAIN THE NEGETIVE VALUE OF THE * LARGEST AVAILABLE BUFFER WHEN THE USER'S REQUEST CAN * NOT BE SATISFIED. WHEN THE REQUEST CAN BE SATISFIED * THE ERROR WORD WILL CONTAIN A ZERO. NOTE THAT THE * ERROR WORD MAY CONTAIN A ZERO WHEN THERE IS ZERO MEMORY * AVAILABLE, AS WELL. THE ERROR CONDITION IS DETERMINED * BY EXAMINING THE A-REGISTER. * * A-REGISTER CONTAINS THE ADDRESS OF THE USER BUFFER WHEN * A BUFFER WAS ALLOCATED, OTHERWISE IT CONTAINS A NEGITIVE * ONE. ****************************************************************** BUFSZ BSS 1 SIZE OF REQUESTED BUFFER PRIM BSS 1 USER'S PRIMARY BUFFER POINTER ERR BSS 1 ERROR RETURN WORD GETBF NOP JSB .ENTR GET PARAMETERS DEF BUFSZ * CLA INITIALIZE USER'S PRIMARY POINTER STA PRIM,I TO ZERO * STA ERR,I INITIALIZE ERROR TO ZERO * LDA BUFSZ,I IS REQUEST LEGAL? SSA JMP ILLRQ SZA,RSS JMP ILLRQ NO,ERROR-EXIT * LDA UNMEM HAS MEMORY BEEN INITIALIZED? SZA JMP GETB1 YES, THEN GO GET BUFFER * JSB LIMEM NO, GET THE MEMORY BOUNDS DEF *+4 DEF .0 DEF AVLM DEF ROTMX * LDA AVLM AVLM = FIRST WORD OF AVAILABLE MEMORY STA UNMEM UNMEM = FIRST WORD OF UNUSED MEMORY'S INA OVERHEAD STA UNM2 UNM2 = SECOND OVERHEAD WORD LDB ROTMX SET B-REG TO SIZE OF UNUSED-MEMORY BUFFER ADB MOVRZ ACCOUNT FOR OVERHEAD ADA B GET ADDRESS TO LAST WORD OF MEMORY STA ENDM ENDM = LAST WORD OF AVAILABLE MEMORY * STB UNMEM,I INITIALIZE OVERHEAD WORDS OF CLA UNUSED MEMORY STA UNM2,I * GETB1 LDA BUFSZ,I IS UNUSED MEMORY'S BUFFER LARGE ENOUGH? ADA OVRSZ ALLOW FOR NEW UNUSED-MEMORY OVERHEAD CMA,INA STA T1 SAVE NEGETIVE SIZE OF REQUESTED BUFFER ADA UNMEM,I SSA,RSS JMP GETB2 * * * * UNUSED MEMORY BUFFER IS NOT LARGE ENOUGH * COMPACT MEMORY * * * JSB CMPK MOVE USED BUFFERS TO LOW MEMORY DEF *+1 * * * CMPK RETURNS: * B-REG = SIZE OF UNMEM'S BLOCK * ADB T1 NOW IS THERE ENOUGH UNUSED MEMORY? SSB JMP NOMEM NO, GO PROCESS ERROR * GETB2 JSB ALLOC YES, ALLOCATE MEMORY DEF *+3 DEF BUFSZ,I DEF PRIM,I * LDA PRIM,I RETURN A-REG = ADDRESS OF BUFFER GETBX JMP GETBF,I * * * * ERROR PROCESSORS * * NOMEM LDA UNMEM,I RETURN LARGEST MEMORY BLOCK ADA MOVRZ AVAILABLE TO CALLER SSA ACCOUNT FOR OVERHEAD OF NEW UNUSED-MEMORY CLA BUFFER CMA,INA STA ERR,I ILLRQ CCA RETURN -1 IN A-REG JMP GETBX * * * DATA * * .0 DEC 0 CONSTANT ZERO - USED IN THE LIMEM CALL ROTMX BSS 1 SIZE OF MEMORY FROM THE END OF THE USER'S * PARTITIAN TO THE END OF THE USER'S * PROGRAM. SKP * * TITLE: CMPK * COMPACT MEMORY * * ABSTRACT: * * CMPK MOVES ALL USED BLOCKS TO LOW MEMORY AND CONSOLIDATES * ALL THE UNUSED BLOCKS IN HIGH MEMORY UPDATING UNMEM, AND * UNM2 ACCORDINGLY. CMPK STARTS AT THE BEGINNING OF AVAILABLE * MEMORY, SEARCHING FOR AN UNUSED BLOCK OF MEMORY, MAKING USE OF * THE CURRENT BUFFER'S SIZE TO LOCATE THE NEXT BUFFER. WHEN AN * UNUSED BUFFER IS FOUND, SUBSEQUENT UNUSED BUFFERS ARE GATHERED * TOGETHER TO FORM A BLOCK OF UNUSED MEMORY. WHEN A USED BUFFER * IS DISCOVERED, IT IS PHYSICALLY MOVED ABOVE THE BLOCK OF UNUSED * MEMORY, UNTIL ALL USED MEMORY PHYSICALLY RESIDES ABOVE THE * BLOCK OF UNUSED MEMORY. WHEN ALL OF MEMORY IS SEARCHED THE * BLOCK OF UNUSED MEMORY BECOMES THE HEAP, OR THE UNUSED-MEMORY * BUFFER, AND UNMEM, AND UNM2 ARE UPDATED TO REFLECT THE CHANGE. * * CMPK DEPENDS ON THE FACT THAT GETBF HAS ALWAYS PROVIDED FOR * ONE UNUSED-MEMORY BUFFER. THIS ASSUMPTION IS CAREFULLY NOTED * IN THE COMMENTS. * * CALLING SEQUENCE: * * JSB CMPK * DEF *+1 * * UNMEM, UNM2, ENDM, AND AVLM ARE EXPECTED TO BE * SET UP. * * EXIT: * * UNMEM POINTS TO THE FIRST OVERHEAD WORD * THE NEW UNUSED-MEMORY BUFFER. * UNM2 POINTS TO THE SECOND OVERHEAD WORD OF THE * UNUSED-MEMORY BUFFER. * * B-REGISTER CONTAINS THE POSITIVE SIZE OF THE UNUSED-MEMORY * BUFFER. * * MEMORY IS COMPACTED * * ******************************************************************* * * CMPK NOP JSB .ENTR GET THE RETURN ADDRESS DEF CMPK * LDA AVLM BEGIN AT THE FIRST WORD OF MEMORY. STA UNMEM INA STA UNM2 * CLA INITIALIZE SIZE OF UNUSED MEMORY TO ZERO STA SIZE * * * * SEARCH FOR FIRST UNUSED BUFFER * NOTE: ON EXIT FROM LOOP, UNMEM IS POINTING TO THE AREA BELOW THE * LAST USED BUFFER. WHEN OTHER USED BUFFERS ARE FOUND * THEY WILL BE PLACED THERE. * * CMP1 LDA UNMEM ARE THERE ANY MORE BUFFERS STA B INB CMB,INB IS UNMEM .LT. ENDM? ADB ENDM SSB JMP CMPX * LDB UNM2,I DOES THIS BUFFER HAVE A PRIMARY SZB,RSS POINTER? JMP CMP10 NO, THEN HAVE FOUND FIRST UNUSED BUFFER * * ADA UNMEM,I YES, GET NEXT BUFFER ADA OVRSZ STA UNMEM INA STA UNM2 JMP CMP1 * * GATHER UP UNUSED BLOCKS * CMP10 LDA UNMEM INITIALIZE TEMPORARY MEMORY POINTER STA TM INA STA TM2 * CMP12 CLA INITIALIZE SIZE OF UNUSED BLOCK STA BLKSZ * CMP15 LDA TM ARE THERE ANY MORE BUFFERS? STA B INB IS TM .LT. ENDM CMB,INB ADB ENDM SSB JMP CMP30 * * * * YES, THEN GATHER UP THE UNUSED BLOCKS * * * LDB TM2,I DOES THIS BUFFER HAVE A PRIMARY POINTER? SZB JMP CMP20 * LDB TM,I ADB OVRSZ NO, THEN GATHER IT INTO * THE UNUSED BLOCK ADB BLKSZ PUT SIZE OF UNUSED BLOCK IN MEMORY STB BLKSZ * ADA TM,I ADA OVRSZ STA TM UPDATE TEMPORARY POINTER TO POINT INA TO NEXT BLOCK STA TM2 JMP CMP15 KEEP LOOPING  * * * * * INCREASE SIZE OF UNUSED MEMORY BY SIZE OF CURRENT * UNUSED BLOCK OF MEMORY * * * * CMP20 LDA SIZE ADA BLKSZ STA SIZE * * * * MOVE USED BLOCK UP, BENEATH LAST USED BLOCK * * * * A-REG = SIZE OF BLOCK * B-REG = POINTER TO USER'S PRIMARY POINTER * * * SZA,RSS DOES THE BLOCK NEED TO BE MOVED? JMP CMP25 * LDA UNMEM UPDATE THE USER'S PRIMARY POINTER ADA OVRSZ BY THE SIZE OF THE BUFFER STA B,I * * * MOVE BLOCK POINTED TO BY TM TO SPACE POINTED TO BY * UNMEM * * * * LDA TM,I GET SIZE OF BLOCK TO BE MOVED ADA OVRSZ STA MOVZ * LDA TM SET A-REG TO ADDRESS OF SOURCE LDB UNMEM SET B-REG TO ADDRESS OF DESTINATION JSB .MVW DEF MOVZ DEF 0 * STA TM PUT NEW ADDRESS OF SOURCE IN TM INA  STA TM2 * STB UNMEM PUT NEW ADDRESS OF DESTINATION IN UNMEM INB STB UNM2 * CMP25 JMP CMP12 * * * CMP30 LDA SIZE ADA BLKSZ STA SIZE * * INITIAIZE HEAPS OVERHEAD * CMPX CLB INITIALIZE SIZE OF UNUSED MEMORY * BUFFER TO ZERO LDA SIZE IS THERE ROOM FOR OVERHEAD ADA MOVRZ SSA JMP CMPXX * STA UNMEM,I INITIALIZE UNUSED BUFFER TO SIZE OF * STB UNM2,I SET PRIMARY POINTER TO ZERO * LDB UNMEM,I RETURN SIZE OF UNUSED MEMORY IN B-REG CMPXX JMP CMPK,I * * * DATA * * BLKSZ BSS 1 ACCUMALATOR FOR THE UNUSED-MEMORY BLOCK * WHILE GATHERING THE UNUSED MEMORY * TOGETHER. MOVZ BSS 1 * HOLDS THE SIZE OF THE USED BUFFER BEING MOVED * TO LOW MWMORY. SIZE BSS 1 ACCUMULATOR FOR SIZE OF THE UNUSED-MEMORY BUFFER SKP * * * TITLE: ALLOC * ALLOCATE A MEMORY BUFFER * * ABSTRACT: * * ALLOC ALLOCATES BUFFERS. IT ASSUMES THAT THE UNUSED * BLOCK OF MEMORY IS LARGE ENOUGH TO CONTAIN THE NEW BUFFER * PLUS THE OVERHEAD FOR THE NEW UNUSED-MEMORY BUFFER. * IT PUTS THE ADDRESS OF THE USER'S PRIMARY POINTER OF * SECOND WORD OF THE OVERHEAD, AND PLACED THE ADDRESS TO THE * USER'S BUFFER IN THE USER'S PRIMARY POINTER. * * CALLING SEQUENCE: * * JSB ALLOC * DEF *+3 * DEF (SIZE OF USER'S BUFFER) * DEF (USER'S PRIMARY POINTER) * * * EXIT: * * THE NEW USER'S BUFFER AND THE NEW UNUSED-MEMORY BUFFER * ARE CREATED. * * NO ERRORS ARE RETURNED BECAUSE ALL ERROR CHECKING * TAKES PLACE IN GETBF. * * BUFZ BSS 1 REQUESTED BUFFER SIZE PTR BSS 1 ADDRESS TO PRIMARY POINTER ALLOC NOP JSB .ENTR DEF BUFZ * LDA UNMEM STA TM SAVE POINTER TO BUFFER INA STA TM2 INA * ADA BUFZ,I UPDATE UNMEM STA UNMEM INA STA UNM2 * LDA BUFZ,I UPDATE UNMEM'S BUFFER SIZE ADA OVRSZ TO OLD SIZE - REQUESTED BUFFER SIZE CMA,INA - OVERHEAD SIZE ADA TM,I STA UNMEM,I * CLA UPDATE UNMEM'S PRIMARY POINTER STA UNM2,I * LDA BUFZ,I INITIALIZE OVERHEAD ON USER'S BUFFER STA TM,I * LDA PTR INITIALIZE USER'S PRIMARY POINTER LDB TM ADB OVRSZ STB A,I * STA TM2,I INITIALIZE BUFFER'S PRIMARY POINTER JMP ALLOC,I * * * * DATA * * TM BSS 1 TEMPORARY MEMORY POINTER FOR OVERHEAD WORD 1 TM2 BSS 1 TEMPORARY MEMORY POINTER FOR OVERHEAD WORD 2 * T1 BSS 1 THIS IS A TEMPORARY STORAGE USED IN GETBF * A EQU 0 THIS REFERS TO THE A-REGISTER B EQU 1 THIS REFERS TO THE B-REGISTER * OVRSZ DEC 2 SIZE OF THE OVERHEAD BLOCK MOVRZ DEC -2 MINUS THE SIZE OF THE OVERHEAD BLOCK END