Rewrite garbage collector and memory allocator

[ffwff]

The current incremental garbage collector/memory allocator is great and all but leaves a lot to be desired. I'm thinking of rewriting a new one.

GC

• [x] Make it work
• [x] Don't scan the stack/data segments in order to get the root objects
  • Time to hack the compiler again
  • LLVM provides some intrinsic functions for getting GC stack variables, might wanna use that!
• [ ] Scale well with big number of nodes
  • The newly rewritten GC does 1 cycle per allocation which doesn't scale
• [x] Use something other than linked lists
  • The current GC stores nodes in 3 singly-linked lists for each color. This isn't great when we want to realloc or change a node's color individually.
  • Might wanna have an allocation bitmap and mark bitmap for each memory pool
• [x] Needs integration with the scheduler so that it can be run when processor is halted

Ideas

• [x] Store marked items in a bitmap, each bitmap associated with a pool, and each bit associated with a slot in that pool
  • Also store mark bits within another bitmap instead of a Gc header
• [x] Store grayed objects in something else
  • a linked-list-based stack? (the current gc does this)
  • a flat fixed-size stack? (maybe we could limit the amount of gray objects being processed per cycle)

Memory allocator

• [x] Make it work
• [x] Allow page size allocations (>1024 bytes and < 4096 bytes - header)
• [x] Use the allocator for userspace malloc

[jkthorne]

Is this for the main Crystal Lang or for Lilith specifically?

[ffwff]

Both? The compiler will be patched to output additional garbage collector data which can then be used by the new GC. The new GC will hopefully be more portable so it can be reused in userspace's libcrystal

[jkthorne]

That is awesome I cannot wait to see what you end up doing :)

[dscottboggs]

What's the status of this feature, and where can it be found? I'm curious about the possibility of merging your GC into the stdlib

[ffwff]

@dscottboggs It's pretty complete on the OS so far, I haven't had crashes. I tried porting it to crystal proper, but I couldn't get it working (I think this is because the actual stdlib uses much more complex data structures than mine does).

But feel free to port it I guess, all of it lies under the src/alloc directory.