.title malloc Allocate and free memory .ident /000005/ ;;***************************** ;;***PL/I-COMPATIBLE VERSION*** ;;***************************** ; ;+ ; ; Index Allocate and free memory ; ; Usage ; ; char * ; malloc(size); /* NULL if no space */ ; unsigned size; /* Number of bytes */ ; ; mfree(p); ; free(p); ; char *p; /* Was allocated */ ; ; Internal ; ; mov size,r0 ; Internal call ; call $$aloc ; to malloc() ; ; Return: r0 -> space (or 0), other registers preserved ; ; mov pointer,r0 ; Internal call ; call $$free ; to free() ; ; Return: r0 random, other registers preserved ; ; $$link(); /* Print memory list */ ; ; Return: all registers preserved ; ; Description ; ; malloc() allocates the indicated number of bytes, ; returning a pointer to the first. If the allocation request ; cannot be satisfied, malloc returns NULL. ; The program image is expanded as needed. ; ; free() and mfree() return a buffer to free space. ; Nothing is returned. ; ; See also the description of realloc() and sbrk(). ; ; Internal ; ; All free memory is allocated in linked lists which are ; stored in monotonically linked, noncontiguous areas. ; Each block has is preceeded by a one word header: ; ; pointer to next block + "busy bit" ; ; The pointer is to the next following block. The last block ; points to the first. The "busy bit" will be set if the ; data in the block is in use. ; ; Note that a block need not contain any data. Free space is ; coalesced during the allocation search. ; ; Subroutine $$link() writes the allocation list onto stderr. ; It was written to debug malloc() and is conditionally compiled. ; Note that it preserves all registers. ; ; Diagnostics ; ; The program may abort if free() is passed a random pointer ; or if the program writes outside of an area reserved by malloc(). ; Note that only certain cases are trapped by this test. ; ; Bugs ; ;- ; ; Edit history ; 000001 28-Jul-80 MM (Complete rewrite of alloc()) ; 000002 04-Aug-80 MM Remove guard word, bummed code, fixed subtle bug. ; Extensive changes, no edit codes ; 000003 13-Aug-80 MM Added $$alox for realloc() communication ; 000004 22-Sep-80 MM Fixed .psect name ; 000005 28-May-81 MM Renamed sbreak as sbrk. ; 000006 08-Oct-81 MM Header is really only one word ;;***000007 01-OCT-82 WE PL/I-COMPATIBLE VERSION ; ;;*** .psect .data. ;;***currp: .word last ;Current start of scan (last free'd) ;;***lastp: .word last ;End of scan (top of memory) ;;***first: .word last+1 ;Initial memory allocation ;;***last: .word first+1 ;Initial memory allocation ;;***$$alox:: ;;*** .word 0 ;Contains value for realloc() ;03 ;;***HDRSIZ = .-$$alox ;Size of a pointer ;06 ;;***BLOCK = 512. ;Bytes to allocate from sbrk() ;;*** ;;***.iif ndf DEBUG DEBUG = 0 ;Default: disable debug code .psect .prog. .GLOBL .ALLOT,.FREE,PLIFP ;;*** malloc:: mov 2(sp),r0 ; Grab size. ; ; $$aloc. ; Internal allocate routine. ; Input: r0=size (bytes). ; Output: r0=ptr to space or NULL. ; $$aloc:: jsr r5,$$svr1 ; Save r5-r1 ;;***PL/I-COMPATIBLE VERSION************** ;;*** ADD #2,R0 ;#BYTES INCLUDING SAVED BYTE CNT;;*** MOV R0,R1 ;;*** JSR PC,PLIFP ;GET PL/I FRAME POINTER ;;*** JSR R5,.ALLOT ;;*** MOV R0,(R1)+ ;SAVE # BYTES FOR FREE ;;*** MOV R1,R0 ;;*** RETURN ;;*** ;;**************************************** ;;*** ;;*** mov r0,r4 ; R4 := number of bytes to get ;;*** add #HDRSIZ+1,r4 ; Including the list header ;;*** bic #1,r4 ; Rounded up to a word boundary ;;*** mov currp,r0 ; Current free list start ;;*** ;;***10$: ;;*** bit #1,(r0) ; Busy? ;;*** bne 50$ ; Br if so, go look for next ;;***; ;;***; Coalesce free blocks together and see if there's enough space ;;***; ;;***20$: ;;*** mov (r0),r2 ; If current -> a busy block ;;*** bit #1,(r2) ; (it's busy bit will be set) ;;*** bne 30$ ; so exit this loop ;;*** mov (r2),(r0) ; Update "first free" to enhance free space ;;*** br 20$ ; Loop to get another ;;***; ;;***; r0 -> the current free space (extended as much as possible) ;;***; r2 -> the first busy block ;;***; ;;***30$: ;;*** mov r0,r3 ; r3 -> ;;*** add r4,r3 ; "current free" + number of bytes needed ;;*** cmp r2,r3 ; is first busy block < end of new block? ;;*** blo 50$ ; Br if so, (gotta scan somewhere else) ;;*** cmp r3,r0 ; Is end of new block > start of free ;;*** blos 50$ ; No (wrap around test) ;;***; ;;***; We've found enough for our needs. Note: the following code requires ;;***; a one-word header. Thus, the link word can always be stored (and ;;***; freed) ;;***; ;;*** mov r3,currp ; currp -> "after new block" ;;*** cmp r2,r3 ; First busy <= "after new block" ;;*** blos 40$ ; Br if so ;;*** mov (r3),$$alox ; Remember old contents for realloc() ;03 ;;*** mov (r0),(r3) ; First busy is later, setup linkage ;;***40$: ;;*** mov r3,(r0) ; New block -> end of new block ;;*** inc (r0)+ ; bis #1,(r0)+, mark it busy ;;*** return ; Exit, r0 -> user's requested block ;;***; ;;***; No free space here ;;***; ;;***50$: ;;*** mov r0,r2 ; Here's a new ending point ;;*** mov (r0),r0 ; Here's a new place to start ;;*** bic #1,r0 ; Clear flag bit ;;*** cmp r2,currp ; Did we wrap around? ;;*** bhis 10$ ; Not yet ;;*** cmp r0,currp ; Did we really wrap around? ;;*** blo 10$ ; Keep on trying ;;***; ;;***; Gotta extend memory ;;***; ;;*** mov r0,-(sp) ; sbrk() kills r1 ;;*** mov #BLOCK,-(sp) ; How much to allocate each time ;;*** call sbrk ; Go for it ;05 ;;*** mov r0,r2 ; New allocation ;;*** beq 70$ ; Exit if nothing left ;;*** mov lastp,r1 ; Here's where it all ends ;;*** mov r2,(r1)+ ; lastp->pointer = new block ;;*** cmp r1,r2 ; Is new space continuous with old? ;;*** beq 60$ ; Br if so ;;*** inc -(r1) ; bis #1,-(r1), make rest busy ;;***60$: ;;*** mov r2,r1 ; Here's the new space ;;*** add (sp)+,r1 ; r1 -> after what we asked for ;;*** mov (sp)+,r0 ; Restore current scan pointer ;;*** tst -(r1) ; r1 -> a dummy block at the end ;;*** mov r1,(r2) ; New space -> the dummy block ;;*** mov r1,lastp ; The end -> the dummy block ;;*** mov #first+1,(r1) ; Wrap the scan around ;;*** br 10$ ; And here we go again ;;***; ;;***; Out of memory (r0 == 0) ;;***; ;;***70$: ;;*** cmp (sp)+,(sp)+ ; Clean the stack ;;*** return ; and return ; ; ; Free (and friends) ; mfree:: free:: mov 2(sp),r0 ; Here's what to free $$free:: ; Internal free call tst r0 ; How can I free nothing beq 10$ ; Urk ;;***PL/I-COMPATIBLE VERSION****************** ;;*** MOV R1,-(SP) ;SAVE ALL REGS BUT R0 ;;*** MOV R2,-(SP) ;;*** MOV R4,-(SP) ;;*** MOV R0,R1 ;;*** MOV -(R1),R2 ;FREE NEEDS #BYTES ;;*** JSR PC,PLIFP ;GET PL/I FRAME POINTER ;;*** JSR R5,.FREE ;;*** MOV (SP)+,R4 ;RESTORE REGS ;;*** MOV (SP)+,R2 ;;*** MOV (SP)+,R1 ;;*** RETURN ;;*** ;;*********************************************** ;;*** ;;*** cmp -(r0),r0 ; Are pointers ascending? ;;*** blos 10$ ; Trouble if not. ;;*** mov r0,currp ; Free scan starts here ;;*** bic #1,(r0) ; Clear busy bit ;;*** clr r0 ; Return null (just in case) ;;*** return ; So simple 10$: CRASH ; Die ;;***; ;;***.if ne DEBUG ;;***; ;;***; ;;***; $$link ;;***; ;;***; Print allocation linkage ;;***; ;;***; Note: all registers are preserved. ;;***; ;;*** ;;***$$link:: ;;*** mov r4,-(sp) ; Save all ;;*** mov r3,-(sp) ; registers ;;*** mov r2,-(sp) ; ;;*** mov r1,-(sp) ; ;;*** mov r0,-(sp) ; ;;*** mov #first,r4 ; R4 -> next linkage ;;*** clr r2 ; R2 == newline count ;;***; ;;***; Output format: ;;***; nnnnnn len free block start, length ;;***; nnnnnn+len busy block start, length ;;***; ;;***; Four entries will be printed on each line ;;***; ;;***10$: ;;*** mov (r4),r3 ; Link + busy bit ;;*** inc r2 ; Step counter ;;*** bic #^C<3>,r2 ; Mod 4, zero means newline ;;*** mov stderr,-(sp) ; To the console ;;*** clr -(sp) ; Clean the stack ;;*** movb link1(r2),(sp) ; Stuff the appropriate byte ;;*** call putc ; Print it ;;*** cmp (sp)+,(sp)+ ; Clear the stack ;;*** mov r3,r0 ; Save it ;;*** bic #1,r3 ; Clear busy bit ;;*** mov r3,-(sp) ; Next ;;*** sub r4,(sp) ; - this = true size ;;*** bic r3,r0 ; Just want busy bit ;;*** movb link2(r0),-(sp) ; Stuff flag ;;*** mov r4,-(sp) ; Current pointer ;;*** mov #link3,-(sp) ; Format ;;*** mov stderr,-(sp) ; To the console ;;*** call fprintf ;;*** add #<5*2>,sp ; Clear the stack ;;*** cmp r3,#first ; At the end? ;;*** beq 30$ ; Exit if so ;;*** cmp r3,r4 ; Screwed up? ;;*** blo 20$ ; Urk ;;*** mov r3,r4 ; Get the next and ;;*** br 10$ ; around we go ;;***; ;;***20$: ;;*** mov r3,-(sp) ; Bad pointer ;;*** mov r4,-(sp) ; pointed from ;;*** mov #link4,-(sp) ; format ;;*** mov stderr,-(sp) ; To the console ;;*** call fprintf ;;*** add #<4*2>,sp ; clear the stack ;;***; ;;***30$: ;;*** mov stderr,-(sp) ; You know where by now ;;*** mov #12,-(sp) ; terminate with a newline ;;*** call putc ; ;;*** cmp (sp)+,(sp)+ ; clear stack ;;*** mov (sp)+,r0 ; restore ;;*** mov (sp)+,r1 ; registers ;;*** mov (sp)+,r2 ;;*** mov (sp)+,r3 ;;*** mov (sp)+,r4 ;;***40$: ;;*** return ;;*** ;;*** .psect .data ;;***temp: .word 0 ;;*** ;;*** .psect .strn. ;;***link1: .byte 11,12,11,11 ;;***link2: .ascii / +/ ;;***link3: .asciz /%06o%c%d/ ;;***link4: .asciz /?%06o->%06o/ ;;*** .even ;;***.endc ;;*** .end