.title malloc Allocate and free memory .ident "V02.00" ;+ ; ; 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 ; ; 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 from the routines. ; ; See also the description of sbreak(). ; ; 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 of ; if the program writes outside of an area reserved by malloc(). ; Note that only certain cases are trapped by this test. ;- ; Edit history ; V02.00 19-Oct-82 TTC Rework of old CS library ; .psect c$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() HDRSIZ = .-last ;Size of a pointer BLOCK = 512. ;Bytes to allocate from sbreak() .even .psect c$code 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,$$svrg ; Save r5-r1 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) ; 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() 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) ; sbreak() kills r1 mov #BLOCK,-(sp) ; How much to allocate each time call sbreak ; Go for it 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 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 ; ; Save general registers r1-r5 on the stack and return to the ; caller. When the caller executes an return (rts pc), it ; will cause the original r1-r5 to be restored and the program ; will return to the original caller. ; $$svrg:: mov r4,-(sp) mov r3,-(sp) mov r2,-(sp) mov r1,-(sp) mov r5,-(sp) ; return to subroutine mov 12(sp),r5 ; get original r5 contents jsr pc,@(sp)+ ; co-routine call to subroutine mov (sp)+,r1 mov (sp)+,r2 mov (sp)+,r3 mov (sp)+,r4 mov (sp)+,r5 rts pc .end