gc kinda almost there

1 files changed, 150 insertions, 23 deletions

diff --git a/include/gc.s b/include/gc.s
index bb32240..636a6a2 100644
--- a/include/gc.s
+++ b/include/gc.s
@@ -2,10 +2,53 @@
 .ifndef _gc_s_file
 _gc_s_file:
 
-.macro prealloc name amount
-	mov %rsp,%rax
+.section .bss
+_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_trigger:
+	# point in memory where the gc will trigger (we don't necessarily wait for the write region to fill up!)
+	cell 0
+
+_gc_last_size:
+	# how much data we evacuated last time
+	cell 0
+_gc_min_alloc:
+	# minimum possible allocation
+	cell 0 # tunable constant
+_gc_grow_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 0 # tunable constant
+_gc_shrink_ratio:
+	# 256th's of the ratio of post-gc still-free to-space that should be considered for discarding
+	cell 0
+
+_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
+
+.macro needs_alloc amount
+	mov %rsp, %rax
 	sub _write_region_start, %rax
-	cmp $amount, %rax #TODO check direction
+	cmp \amount, %rax
 	jb _uskel_gc
 .endm
 
@@ -14,23 +57,24 @@ _uskel_alloc:
 
 	# calculate the desired size to %r14
 	mov _gc_min_alloc, %r14
+	#add _gc_region_end, %r14
+	#sub _gc_region_start, %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
+	mulq _gc_grow_ratio
+	shr $8, %rax
+	add _gc_min_alloc, %rax
+	cmp %r14, %rax
 	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
+	cmp %r14, %rax
 	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 ?
 
+	alloc_goes_mmap:
 	mov $9, %rax # mmap
 	mov $0, %rdi # addr = NULL
 	mov %r14, %rsi # len = %r14
@@ -48,27 +92,110 @@ _uskel_alloc:
 
 	jmp *%r15
 
+_uskel_gc_init:
+	mov %rsi, %r13
+	movq $0x100, _gc_min_alloc
+	movq $0x180, _gc_grow_ratio
+	movq $0x40, _gc_shrink_ratio
+	mov $0, %rsp # fake original rsp for first alloc run
+	mov $_uskel_gc_init_cont, %rsi
+	jmp _uskel_alloc
+	_uskel_gc_init_cont:
+	mov _write_region_start, %rax
+	mov %rax, _gc_trigger
+	jmp *%r13
+
 _uskel_gc:
+	# save what we did before ending up here
 	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
+	mov _write_region_start, %rbx
+	mov _write_region_end, %rcx
+	mov %rbx, _gc_region_start
+	mov %rcx, _gc_region_end
+	mov $_uskel_gc_evacuate, %rsi
 	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
+
+	# point the writer to the new memory area
+	mov _write_region_end, %rsp
+	mov %rsp, %rdi # %rdi is "the last scavenged thing"
+	
+	# start by evacuating the thunk and cont
+	mov _gc_backup_thunk, %rbp
+	mov $_uskel_gc_evacuate_cont_thunk, %rsi
+	jmp _gc_evacuate
+	_uskel_gc_evacuate_cont_thunk:
+	mov %rbp, _gc_backup_thunk
+
+	mov _gc_backup_cont, %rbp
+	mov $_uskel_gc_evacuate_cont_cont, %rsi
+	jmp _gc_evacuate
+	_uskel_gc_evacuate_cont_cont:
+	mov %rbp, _gc_backup_cont
+
+	# scavenge everything
+	_uskel_gc_scavenge:
+	# start at what we wrote last
+	mov %rsp, %rbp
+
+	# if the thing is already scavenged, we didn't write anything, mark done.
+	cmp %rbp, %rdi
+	jbe _uskel_gc_scavenge_end
+
+	_uskel_gc_scavenge1:
+	# if all ok, scavenge one thing (moving %rbp) and recheck
+	mov $_uskel_gc_scavenge1_ret, %rsi
+	mov (%rbp), %rax
+	jmp *-020(%rax) # scavenge position in infotable
+	_uskel_gc_scavenge1_ret:
+	cmp %rbp, %rdi
+	ja _uskel_gc_scavenge1
+
+	# everything above rsp is now scavenged, continue with next round
+	mov %rsp, %rdi
+	jmp _uskel_gc_scavenge
+
+	_uskel_gc_scavenge_end:
+
+	# deallocate the old memory region
+	mov $11, %rax # munmap
+	mov _gc_region_end, %rsi
+	mov _gc_region_start, %rdi # addr = gc start
+	sub %rdi, %rsi # len = gc end - gc start
+	syscall
+	
+	# recalculate the gc trigger point
+	mov %rsp, %rax
+	sub _write_region_start, %rax
+	mulq _gc_shrink_ratio
+	shr $8, %rax
+	add _write_region_start, %rax
+	mov %rax, _gc_trigger
 
 	# save how much data we actually had at this point
-	mov _write_region_end, _gc_last_size
-	sub %rsp, _gc_last_size
+	mov _write_region_end, %rax
+	sub %rsp, %rax
+	mov %rax, _gc_last_size
+
+	# restore what we were doing
+	mov _gc_backup_thunk, %rbp
+	mov _gc_backup_cont, %rsi
+	enter_rbp # for simplicity just restart the thunk
 
-	enter_rbp # restart the thunk for simplicity
+_gc_evacuate:
+	# check if we are really out of the target region
+	cmp _write_region_start, %rbp
+	jb _gc_evacuate_ok
+	cmp _write_region_end, %rbp
+	jae _gc_evacuate_ok
+	# if not, let's just jump to cont and leave %rbp as result
+	jmp *%rsi
+	_gc_evacuate_ok:
+	# if we should evacuate, jump to the evac routine
+	mov (%rbp), %rax
+	jmp *-030(%rax)
 
 .endif #_gc_s_file