gc attempt 1 (to be cont'd)

3 files changed, 123 insertions, 31 deletions

diff --git a/include/data.s b/include/data.s
index 2c512d4..43d2ba8 100644
--- a/include/data.s
+++ b/include/data.s
@@ -7,7 +7,6 @@ _data_s_file:
 CON_evacuate1:
 	retq # TODO
 CON_scavenge1:
-	add $020, %rsi
 	retq
 
 # Format of the info tables:
diff --git a/include/gc.s b/include/gc.s
new file mode 100644
index 0000000..bb32240
--- /dev/null
+++ b/include/gc.s
@@ -0,0 +1,74 @@
+
+.ifndef _gc_s_file
+_gc_s_file:
+
+.macro prealloc name amount
+	mov %rsp,%rax
+	sub _write_region_start, %rax
+	cmp $amount, %rax #TODO check direction
+	jb _uskel_gc
+.endm
+
+_uskel_alloc:
+	mov %rsi, %r15 # %rsi is the return address; back it up
+
+	# calculate the desired size to %r14
+	mov _gc_min_alloc, %r14
+
+	# check if the desired size isn't greater because of the last gc use
+	mov _gc_last_size, %rax
+	mul _gc_min_expect_ratio, %rax
+	shr 8, %rax
+	cmp %r14, %rax #TODO check direction
+	cmova %rax, %r14
+
+	# check if we don't need even more space because we need to evacuate stuff
+	mov _gc_region_end, %rax
+	sub %rsp, %rax # trick -- if we counted from gc region start, allocated memory could never shrink
+	cmp %r14, %rax #TODO direction
+	cmova %rax, %r14
+	#TODO add functionality to trigger the gc's a bit earlier than when
+	# they hit _write_region_start, to allow for faster compaction.
+	# maybe _write_region_trigger = 25%ish between _write_region_start and %rsp ?
+
+	mov $9, %rax # mmap
+	mov $0, %rdi # addr = NULL
+	mov %r14, %rsi # len = %r14
+	mov $0b11, %rdx # prot = PROT_READ 0b1 | PROT_WRITE 0b10
+	mov $0x22, %r10 # flags = MAP_PRIVATE 0x2 | MAP_ANONYMOUS 0x20
+	mov $-1, %r8 # fd = -1
+	mov $0, %r9 # off = 0
+	syscall
+
+	# store the results
+	mov %rax, _write_region_start
+	add %r14, %rax
+	mov %rax, _write_region_end
+	mov %rax, %rsp # initialize writing into the new region
+
+	jmp *%r15
+
+_uskel_gc:
+	mov %rbp, _gc_backup_thunk
+	mov %rsi, _gc_backup_cont
+	# first we need a new memory area
+	mov _write_region_start, _gc_region_start
+	mov _write_region_end, _gc_region_end
+	mov $_uskel_gc_evacuate, %r15
+	jmp _uskel_alloc
+	_uskel_gc_evacuate:
+	# we may also need a scavenging queue! Or can that be solved by walking the write region?
+	# plan:
+	# evacuate thunk and cont, save them right away in _gc_backup_thunk and _cont
+	# scavenge from the top of the gc region, evacuating stuff en route
+	# (this is a little more complex because we grow down, so we have to
+	# scavenge up from %rsp to the last known scavenged position)
+	# finish when scavenge doesn't have anything more to scavenge
+
+	# save how much data we actually had at this point
+	mov _write_region_end, _gc_last_size
+	sub %rsp, _gc_last_size
+
+	enter_rbp # restart the thunk for simplicity
+
+.endif #_gc_s_file
diff --git a/include/uskel.s b/include/uskel.s
index 34ee63a..bca33c9 100644
--- a/include/uskel.s
+++ b/include/uskel.s
@@ -8,41 +8,57 @@ _start:
 
 .include "include/macros.s"
 
+# this has globals
 .section .bss
-_memory_state:
-	cell 0 # bottom of allocation (grows down)
-	cell 0 # region start
-	cell 0 # region end
-	cell 0 # program entry rsp (aka the actual stack)
+_unix_rsp:
+	# back-up of program entry rsp (aka the actual stack given by the
+	# actual OS; we might like to use it at some point, maybe)
+	cell 0
+_write_region_start:
+	# begin of the active memory area
+	cell 0
+_write_region_end:
+	# end of the active memory area (%rsp kinda starts here and goes down
+	# towars the start)
+	cell 0
+_gc_last_size:
+	# how much data we evacuated last time
+	cell 0
+_gc_min_alloc:
+	# minimum possible allocation
+	cell 0x100000 # tunable constant
+_gc_min_expect_ratio:
+	# 256th's of the minimal amount of memory increment compared to the
+	# last time. New minimal amount is compared as:
+	# (ratio * last size) >> 8
+	cell 0x200 # tunable constant
+_gc_region_start:
+	# in GC, this region is being evacuated and will eventually disappear
+	cell 0
+_gc_region_end:
+	# end of the disappear region
+	cell 0
+_gc_backup_thunk:
+	# backup of %rsi so that we can use the register for other nonsense
+	cell 0
+_gc_backup_cont:
+	# backup of %rbp for same reason
+	cell 0
 
 .section .text
 
-_uskel_alloc_basic_mem:
-	mov $0x100000, %r15 # desired size
-
-	mov $9, %rax # mmap
-	mov $0, %rdi # addr = NULL
-	mov %r15, %rsi # len = %rcx
-	mov $0b11, %rdx # prot = PROT_READ 0b1 | PROT_WRITE 0b10
-	mov $0x22, %r10 # flags = MAP_PRIVATE 0x2 | MAP_ANONYMOUS 0x20
-	mov $-1, %r8 # fd = -1
-	mov $0, %r9 # off = 0
-	syscall
-	mov $_memory_state, %rdi
-	mov %rax, 010(%rdi)
-	add %r15, %rax
-	mov %rax, (%rdi)
-	mov %rax, 020(%rdi)
-	retq
+.include "include/gc.s"
 
 _uskel_start:
-	call _uskel_alloc_basic_mem
-	# use the stack pointer for easy writing to the heap,
-	# but back it up to memory state
-	mov $_memory_state, %rdi
-	mov %rsp, 030(%rdi)
-	mov 0(%rdi), %rsp
+	# we use the stack pointer for easy writing to the heap;
+	# back it up to memory state just if we ever needed it again.
+	mov %rsp, _unix_rsp
 
+	# allocate the initial chunk of memory
+	mov $_uskel_start_main, %rsi
+	jmp _uskel_alloc
+
+	_uskel_start_main:
 	# push a thunk for main
 	pushq $0
 	pushq $main
@@ -50,5 +66,8 @@ _uskel_start:
 	mov $0, %rsi # set continuation to exit
 	enter %rsp # run the program
 	# Q: are there gonna be functions that have both the argument AND the cont?
-	# A: No, stuff is either entered as return-continuation (takes res, cont has to be saved) or as forward call (takes cont)
-	# (needs validation)
+	# 
+	# A: No, stuff is either entered as return-continuation (takes res,
+	# cont has to be saved) or as forward call (takes cont)
+	#
+	# (A needs validation)