Add bump allocator

7 files changed, 135 insertions, 0 deletions

diff --git a/atk16_asm/builtin_asm/bootstrap.atk16 b/atk16_asm/builtin_asm/bootstrap.atk16
index e0fddfa..28d8aa1 100644
--- a/atk16_asm/builtin_asm/bootstrap.atk16
+++ b/atk16_asm/builtin_asm/bootstrap.atk16
@@ -2,6 +2,7 @@
 
 ; memory segments
 @let stack_segment   0x8000
+@let heap_segment    0xE7EF ; grows down from 0xE7EF until SP
 @let mmio_segment    0xE7F0
 @let terminal_addr   0xE7F0
 @let keyboard_addr   0xE7F1
diff --git a/atk16_asm/builtin_asm/std_alloc.atk16 b/atk16_asm/builtin_asm/std_alloc.atk16
deleted file mode 100644
index e69de29..0000000
--- a/atk16_asm/builtin_asm/std_alloc.atk16
+++ /dev/null
diff --git a/atk16_asm/builtin_asm/std_bump_alloc.atk16 b/atk16_asm/builtin_asm/std_bump_alloc.atk16
new file mode 100644
index 0000000..3e91800
--- /dev/null
+++ b/atk16_asm/builtin_asm/std_bump_alloc.atk16
@@ -0,0 +1,77 @@
+; Heap bump allocator implementation
+;
+; Just below the MMIO segment, which starts at 0xE7F0, is the heap segment. The heap area
+; grows down from 0xE7EF until it overlaps with the stack, which grows up from 0x8000.
+;
+; The stack pointer is stored in register SP, which is the general use register RH by spec.
+;
+; The interface consists of two functions, bump_alloc and bump_reset.
+; The bump_alloc function allocates a block of memory from the heap,
+;   returning the lowest address of the allocated block.
+; The bump_reset function resets the heap to its initial state, freeing all allocated blocks.
+;
+; To initialize the bump allocator, call bump_reset.
+;
+; The arena allocator cannot free individual blocks, only reset the entire heap.
+;
+; The memory layout is as follows:
+; 0xE7EF (heap_segment)       alloc_next value
+; 0xE7EE downwards            allocated blocks
+;
+; The alloc_next value is a pointer to the next free word in the heap.
+; The alloc_next value is stored in the first word of the heap.
+
+@label bump_next_p
+  heap_segment
+@label bump_arena_start
+  ${heap_segment - 1}
+
+@label bump_reset
+  ; reset the heap to its initial state (zero allocated blocks)
+  ; can be used to initialize the bump allocator
+  ; parameters:         none
+  ; return:             void
+  stack_stash RA RB
+
+  ldi bump_arena_start RA     ; RA := bump_arena_start pointer
+  ldr RA RA                   ; RA := bump_arena_start
+
+  ldi bump_next_p RB          ; RB := bump_next_p pointer
+  ldr RB RB                   ; RB := bump_next_p
+
+  str RA RB                   ; *bump_next_p = bump_arena_start
+
+  stack_restore RA RB
+  return
+
+@label bump_alloc
+  ; allocate a block of memory from the heap, checking for overlap with the stack
+  ; parameters:               RA = n of words to allocate
+  ; return:                   RG = address of allocated block or 0 if allocation failed
+  stack_stash RB RC
+
+  ldi bump_next_p RB          ; RB := bump_next_p pointer
+  ldr RB RB                   ; RB := bump_next_p
+  ldr RB RG                   ; RG := *bump_next_p (address of next free word)
+
+  sub RG RA RG                ; RG := RG - RA (new alloc_next value)
+
+  ; check that the new alloc_next value does not overlap with the stack
+  sub RG SP RC                ; RC := RG - SP
+  bri sign bump_alloc_overlap ; if RC < 0, bump_alloc_overlap
+                              ; otherwise allocation ok
+
+@label bump_alloc_ok
+  str RG RB                   ; *bump_next_p = RG
+
+  inc RG                      ; RG := RG + 1 (lowest address of allocated block)
+
+  jpi bump_alloc_return
+
+@label bump_alloc_overlap
+  ; allocation failed, return 0
+  ldi 0 RG
+
+@label bump_alloc_return
+  stack_restore RB RC
+  return
diff --git a/test/e2e/std_bump_alloc/run_bump_alloc.atk16 b/test/e2e/std_bump_alloc/run_bump_alloc.atk16
new file mode 100644
index 0000000..b9a8411
--- /dev/null
+++ b/test/e2e/std_bump_alloc/run_bump_alloc.atk16
@@ -0,0 +1,10 @@
+@include %bootstrap
+@include %std_bump_alloc
+
+@label main
+  calli bump_reset
+
+  ldi 5 RA          ; allocate 5 words
+  calli bump_alloc
+
+  hlt
diff --git a/test/e2e/std_bump_alloc/run_bump_reset.atk16 b/test/e2e/std_bump_alloc/run_bump_reset.atk16
new file mode 100644
index 0000000..6e14bb7
--- /dev/null
+++ b/test/e2e/std_bump_alloc/run_bump_reset.atk16
@@ -0,0 +1,6 @@
+@include %bootstrap
+@include %std_bump_alloc
+
+@label main
+  calli bump_reset
+  hlt
diff --git a/test/e2e/std_bump_alloc/test_bump_alloc.py b/test/e2e/std_bump_alloc/test_bump_alloc.py
new file mode 100644
index 0000000..9e64b8c
--- /dev/null
+++ b/test/e2e/std_bump_alloc/test_bump_alloc.py
@@ -0,0 +1,24 @@
+from atk16_asm import assemble
+from atk16_emu import Machine
+from test.utils import pad_bytearray, assemble_and_run_until_halted
+
+def test_bump_reset():
+  machine = assemble_and_run_until_halted(
+    "test/e2e/std_bump_alloc/run_bump_reset.atk16"
+  )
+
+  heap_next_p = 0xE7EF
+  heap_next = machine.mem_read(heap_next_p)
+  assert heap_next == heap_next_p - 1
+
+def test_bump_alloc():
+  machine = assemble_and_run_until_halted(
+    "test/e2e/std_bump_alloc/run_bump_alloc.atk16"
+  )
+
+  heap_next_p = 0xE7EF
+  heap_next = machine.mem_read(heap_next_p)
+  assert heap_next == heap_next_p - 1 - 5
+
+  returned_value = machine.rg.value
+  assert returned_value == heap_next + 1
diff --git a/test/utils.py b/test/utils.py
index 873aa64..f7cd8a0 100644
--- a/test/utils.py
+++ b/test/utils.py
@@ -1,3 +1,6 @@
+from atk16_asm import assemble
+from atk16_emu import Machine
+
 def pad_bytearray(ba: bytearray, to_length: int = 64 * 1024) -> bytearray:
   """
   Pads a bytearray with zeros until it reaches a specified length.
@@ -23,3 +26,17 @@ def make_rom(words: list[int]) -> bytearray:
     bytes.append((word >> 8) & 0xFF)
     bytes.append(word & 0xFF)
   return pad_bytearray(bytearray(bytes))
+
+def assemble_and_run_until_halted(filename: str) -> Machine:
+  with open(filename, "r") as f:
+    source = f.read()
+
+  obj = assemble(source, filename)
+  rom_image = pad_bytearray(obj.program)
+
+  machine = Machine()
+  machine.load_rom_image(rom_image)
+  machine.reset()
+  machine.run_until_halted()
+
+  return machine
\ No newline at end of file