Asm memory allocator

Take a look at the source code of ObsoFTP. It's in C but you will find a malloc/mfree pair in assembler. By the way it's the same code used by MSX-DOS 2 and Nextor to allocate memory in the data segment.

The entire c library in z88dk is written in assembly language. The heap is here:
http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_...

There's a mutex in there which can be ignored (C11 requires it) and you are able to create and allocate from multiple heaps in memory. The allocated blocks are doubly linked for fast realloc() (and free as side-effect; realloc is important in the c library). The malloc function boils down to "asm_heap_alloc_unlocked" ( http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_... ) which is entered with registers equal to the allocation size request and the address of the heap. A short description of the heap data structure is here: http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_...

Nearby you can also find code for an obstack and block memory allocator.

This is hard and only it was 253 lines of code. I'm sure my code it's wrong but it seems to work.

  module allocator


heap_start: equ ram.end


  struct block
next dw 0                       ; next free block
size dw 0                       ; size of block including header
  endstruct


  ;;
  ;; init
  ;;
init:
  ld ix,heap_start              ; first block
  ld hl,heap_start+block        ; second block

  ;; first block NEXT=secondblock SIZE=0
  ;;   with this block we have a fixed start location
  ;;   because never will be allocated
  ld (ix+block.next),l
  ld (ix+block.next+1),h
  ld (ix+block.size),0
 	ld (ix+block.size+1),0

  ;; second block NEXT=0 SIZE=all
  ;;   the first and only free block have all available memory
  ld (ix+block.next+block),0
  ld (ix+block.next+block+1),0

  ld hl,(sysvar.himem)          ; size=(himem)-heap_start-block_header*2
  ld de,heap_start
  or a
  sbc hl,de
  ld de,-block*2
  add hl,de
  ld (ix+block.size+block),l
  ld (ix+block.size+block+1),h
  ret


  ;;
  ;; round_bc
  ;;
round_bc:
	ld a,c
	dec bc
	ld a,c
	or 3
	ld c,a
	inc bc
  ret


  ;; get_free
  ;; OUT BC=freespace
get_free:
  ld ix,heap_start
  ld bc,0
.count:
  ld a,c
  add a,(ix+block.size)
  ld c,a
  ld a,b
  adc a,(ix+block.size+1)
  ld b,a

  ld l,(ix+block.next)
  ld h,(ix+block.next+1)
  ld a,h
  or l
  ret z

  push hl
  pop ix
  jr .count


  ;;
  ;; alloc
  ;; IN BC=size OUT IX=memptr NZ=ok
  ;;
alloc:
  ;; bc=round(bc+block_header_size)
  ld hl,block
  add hl,bc
  push hl
  pop bc
  call round_bc

  ld ix,heap_start              ; this
  ld iy,0                       ; prev

.find:
  ld l,(ix+block.size)
  ld h,(ix+block.size+1)

  or a
  sbc hl,bc
  jr c,.nextblock
  jr z,.exactfit

  ;; split found block
.splitfit:
  ;; newfreeblock=this+BC
  push ix
  pop hl
  add hl,bc
  ;; prevblock->next=newfreeblock
  ld (iy+block.next),l
 	ld (iy+block.next+1),h
  ;; newfreeblock->next=this->next
  push hl
  pop iy                        ; iy=newfreeblock
  ld l,(ix+block.next)
  ld h,(ix+block.next+1)
  ld (iy+block.next),l
  ld (iy+block.next+1),h
  ;; newfreeblock->size=this->size-BC
 	ld l,(ix+block.size)
  ld h,(ix+block.size+1)
  or a
  sbc hl,bc
  ld (iy+block.size),l
 	ld (iy+block.size+1),h
  ;; this->size=BC
  ld (ix+block.size),c
  ld (ix+block.size+1),b

  jr .ok

  ;; use whole found block
.exactfit:
  ;; prevblock->next=this->next - remove block from free list
  ld l,(ix+block.next)
  ld h,(ix+block.next+1)
  ld (iy+block.next),l
  ld (iy+block.next+1),h

.ok:
  ;; ix=first byte
  ld de,block
  add ix,de

  ;; enable z-flag
  ld a,1
  or a
  ret

.nextblock:
  ld l,(ix+block.next)
  ld h,(ix+block.next+1)
  ld a,l
  cp h
  ret z
  ;; prevblock=this
 	push ix
  pop iy
  ;; this=this->next
  push hl
  pop ix
  jr .find


  ;;
  ;; free
  ;; IN IX=memptr
  ;;
free:
  ;; this=HL-block_header_size
  push ix
  pop hl
  ld de,-block
  add hl,de

  ;; find prevblock
 	ld ix,heap_start
.find:
  ld e,(ix+block.next)
  ld d,(ix+block.next+1)

  ld a,d
  or e
  jp z,.passedend

  sbc hl,de
  jp c,.found

  add hl,de                     ; restore hl value
  ld ixl,e
  ld ixh,d
  jp .find

.found:
  add hl,de                     ; restore hl value
  ;; HL->next = this->next
  push hl
  pop iy
  ld e,(ix+block.next)
  ld d,(ix+block.next+1)
  ld (iy+block.next),e
  ld (iy+block.next+1),d
  ;; this->next=HL
  ld (ix+block.next),l
 	ld (ix+block.next+1),h
  ;; try coalesce prev&prev->next prev->next&prev->next->next
  call .coalesce
  jr .coalesce

.passedend:
  ;; append block at the end of the free list
  ld (ix+block.next),l
  ld (ix+block.next+1),h
  push hl
  pop iy
  ld (iy+block.next),0
 	ld (iy+block.next+1),0
  jr .coalesce


.coalesce:
  ;; if prevblock+prevblock->size==prevblock->next
  push ix
  pop hl
 	ld e,(ix+block.size)
  ld d,(ix+block.size+1)
  add hl,de
 	ld e,(ix+block.next)
	ld d,(ix+block.next+1)
  or a
  sbc hl,de
  ret nz

  ;; prevblock->size+=prevblock->next->size
  ld l,(ix+block.next)
  ld h,(ix+block.next+1)
  push hl
  pop iy
  ld l,(iy+block.size)
  ld h,(iy+block.size+1)
 	ld e,(ix+block.size)
  ld d,(ix+block.size+1)
  add hl,de
	ld (ix+block.size),l
  ld (ix+block.size+1),h
  ;; prevblock->next=prevblock->next->next
 	ld l,(iy+block.next)
  ld h,(iy+block.next+1)
  ld (ix+block.next),l
  ld (ix+block.next+1),h
  ret